13441번 - 마법의 나무

도현이는 인큐베이터를 하나 가지고 있다. 이 인큐베이터의 능력은 나무를 마법의 나무로 바꾸는 것이다.

도현이의 화단에는 나무가 N개가 있고, 1번부터 N번까지 번호가 매겨져 있다. 일부 나무는 다른 나무를 좋아하는데, 이 좋아함은 대칭이 아니다. 또, 자기 자신을 좋아할 수도 있다. 도현이는 어떤 나무가 어떤 나무를 좋아하는지에 대한 정보를 모두 알고 있다. 나무 i가 j를 좋아하는 경우에 L_i,j = 1이고, 아닌 경우에는 L_i,j = 0이다.

모든 나무는 두 가지 속성을 가지고 있다. 첫 번째는 isMagical(마법의 나무이면 True, 아니면 False)이며, 두 번째는 isProtected(다른 나무에 의해서 보호받고 있으면 True, 아니면 False) 이다. 처음에 모든 나무의 isMagical과 isProtected는 모두 False 이다.

도현이는 나무를 마법의 나무로 바꿀 수 있는 능력을 가지고 있다. 즉, i번 나무의 isMagical을 False에서 True로 바꿀 수 있다. 이렇게 한 나무를 마법의 나무로 바꾸면 아래와 같은 일들이 연속적으로 일어나게 된다.

• 모든 마법의 나무 i는 자신이 좋아하는 나무 j를 보호한다. 즉, i번 나무의 isMagical이 True이고, L_i,j가 1이면, j번 나무의 isProtected가 True로 변한다.
• 모든 보호 받는 나무 i는 자신이 좋아하는 나무 j를 보호한다. 즉, i번 나무의 isProtected가 True이고, L_i,j가 1이면, j번 나무의 isProtected가 True로 변한다.

위의 변화는 연쇄적으로 일어난다. 이러한 변화가 모두 끝나면, 다시 도현이는 나무 하나를 마법의 나무로 바꾼다.

도현이는 마법의 나무이면서 보호받지 못하는 나무의 수를 최대로 하려고 한다. 즉, isMagical의 값이 True이면서 isProtected의 값이 False인 나무의 수를 최대한 많게 하려고 한다.

마법의 나무이면서 보호받지 못하는 나무의 수를 최댓값을 구하는 프로그램을 작성하시오.

첫째 줄에 나무의 수 N (1 ≤ N ≤ 50)이 주어진다.

둘째 줄에는 L_i,j가 1번 나무부터 순서대로 주어진다.

마법의 나무이면서 보호받지 못하는 나무의 수를 최댓값을 출력한다.

예제 1의 경우에는 1번 나무를 마법의 나무로 바꾸면 된다. 이렇게 되면, 1번 나무는 마법의 나무이면서 보호받지 못하는 나무가 된다.

에제 2의 경우에 3번 나무를 마법의 나무로 바꾸고, 1번 나무를 마법의 나무로 바꾸면, 1번 나무가 2번 나무를 보호하고, 2번 나무가 3번 나무를 보호하게 된다. 1번 나무는 마법의 나무이면서 보호받지 못하는 나무가 될 것 이고, 2번 나무는 일반 나무이면서 보호받는 나무, 3번 나무는 마법의 나무이면서 보호받는 나무가 된다.