Thành phố có \(N\) địa điểm giao thông liên kết bởi M tuyến đường một chiều. Cần lập bảng kiểm tra tính liên thông để xem từ địa điểm i bất kỳ có thể đi tới địa điểm \(j\) bất kỳ hay không.

Định dạng đầu vào

• Dòng đầu chứa hai số nguyên \(N\) và M (\(1 \le N \le 400, 0 \le M \le 8000\)).
• \(M\) dòng tiếp theo, mỗi dòng chứa hai số nguyên u, v (\(1 \le u, v \le N\)), biểu thị tuyến đường một chiều từ u sang \(v\).

Định dạng đầu ra

• In ra ma trận liên thông kích thước \(N \times N\). Phần tử hàng i cột j bằng 1 nếu có đường đi từ i tới j, ngược lại bằng 0. Khoảng cách từ \(i\) tới chính nó luôn đi được (in 1).

Ví dụ

Input:

3 2
1 2
2 3

Output:

1 1 1
0 1 1
0 0 1

Giải thích: Ma trận tính liên thông khả đạt (Reachability Matrix).

Ràng buộc

• Subtask 1 (40% số điểm): \(N \le 50, M \le 200\).
• Subtask 2 (60% số điểm): Không có ràng buộc gì thêm.