Sau bao ngày tháng cày cuốc vất vả, cuối cùng Louis cũng trở thành chủ tịch của vương quốc ánh sáng. Vương quốc này bao gồm ~n~ thành phố ánh sáng, các thành phố có thể có những cây cầu để thần dân đi lại. Một bang của vương quốc là tập hợp những thành phố mà có thể di chuyển qua lại lẫn nhau.
Trước khi chuyển giao bộ máy chính quyền cho Louis, chủ tịch cũ đã kịp nhận vào rất nhiều thư kí để kiếm tiền. Điều này làm bộ máy nhân viên bị quá tải. Vì không thể sa thải nhân viên khi mới lên chức, Louis đành tìm cách tạo ra nhiều bang nhất có thể để chia việc cho nhân viên. Vương quốc hiện tại chỉ có 1 bang duy nhất.
Louis có thể cho đánh sập 1 cây cầu nối giữa hai thành phố nếu việc đó làm tăng số bang hiện tại của vương quốc lên.
Nhiệm vụ của bạn là xác định xem đó là những cây cầu nào.
Input
Dòng đầu tiên chứa một số nguyên ~n~ (~ 1 \le n \le 10^2 ~) - số lượng thành phố ánh sáng trong vương quốc.
~n~ dòng tiếp theo, mỗi dòng chứa ~n~ số nguyên 0 hoặc 1 biểu thị có hay không đường đi giữa 2 thành phố ~i, j~.
Output
In ra trên một dòng - số lượng cây cầu có thể phá đi để làm tăng số bang của vương quốc.
Sample
Input #1
4
0 1 0 0
1 0 1 0
0 1 0 1
0 0 1 0
Output #1
3
Input #2
4
0 1 1 1
1 0 1 1
1 1 0 1
1 1 1 0
Output #2
0
Problem source: CLB Lập Trình PTIT
Bình luận