Rikka와 게임

Rikka와 반 친구들이 온라인 게임을 하고 있다. 게임에는 $n$명의 플레이어가 있고, 플레이어 사이에 친구 관계인 쌍이 여러 개 있다. 친구 관계는 양방향이다.

게임 시작 시 한 명이 무작위로 "dragon"으로 정해지고, 나머지 플레이어는 "hero"로 표시된다.

게임은 턴 단위로 진행된다. 각 턴은 다음 세 단계로 이루어진다.

1. 각 "hero"는 "dragon"을 공격할지 결정한다. 이때 각 플레이어는 다른 플레이어의 결정을 알지 못한다. "hero"가 "dragon"의 친구라면 그 "hero"는 공격하지 않아야 한다.
2. 모든 "hero"가 공격하지 않기로 하면 게임이 즉시 끝난다. 그렇지 않으면 "hero"들이 "dragon"을 제거한다.
3. 공격한 "hero" 중 번호가 가장 작은 플레이어 $i$가 새로운 "dragon"이 되고, 새 턴이 시작된다.

게임이 끝나면 살아 있는 각 "hero"는 10점을 얻고, 마지막 "dragon"은 100점을 얻는다. 제거된 플레이어는 각각 1점만 얻는다.

모든 플레이어는 자신의 점수를 최대화하려 하며, 모두 충분히 영리하다고 가정한다.

각 플레이어에 대해, 그 플레이어를 처음 "dragon"으로 정했을 때 게임이 첫 턴에 바로 끝나는지 구하라.

첫 줄에 정수 $n$ ($1 \leq n \leq 500$)이 주어진다.

이어서 $n$개의 줄에 길이 $n$인 01 문자열 $s_i$가 주어진다. $s_{i,j}=1$은 플레이어 $i$와 $j$가 친구인 경우에만 성립한다.

입력은 $s_{i,j} = s_{j,i}$와 $s_{i,i}=0$을 보장한다.

길이 $n$인 01 문자열 $res$를 한 줄에 출력한다. 플레이어 $i$를 처음 "dragon"으로 정했을 때 게임이 첫 턴에 바로 끝나면 $res_i = 1$이고, 그렇지 않으면 $res_i = 0$이다.

첫 번째 예제에서는 어떤 플레이어가 선택되든 다른 플레이어가 공격을 선택한다. 공격하면 100점을 얻고, 공격하지 않으면 10점밖에 얻지 못하기 때문이다. 그래서 게임은 두 번째 턴으로 넘어간다.

두 번째 예제에서 세 번째 플레이어가 처음 "dragon"으로 선택되었다고 하자. 그러면 다음과 같다.

• 첫 번째 플레이어가 공격하면 두 번째 턴의 "dragon"이 된다. 첫 번째 예제에 따르면 그 플레이어는 이후 제거되어 1점만 얻는다. 따라서 첫 번째 플레이어는 공격하지 않고 10점을 얻는다.
• 두 번째 플레이어도 같은 이유로 공격하지 않는다.

그러므로 게임은 첫 턴에 끝난다.