게임

지안지아는 게임을 좋아하는 소년이다. 질문을 받으면 곧바로 답하기보다 게임으로 바꾸는 쪽을 좋아한다. 지안지아는 친구 메이유에게 타이완의 항공망 이야기를 꺼냈다. 도시는 $n$개이고 $0$번부터 $n-1$번까지 번호가 붙어 있다. 어떤 도시 쌍은 직항 노선으로 이어져 있으며, 노선은 양방향으로 오갈 수 있다.

메이유는 비행기만으로 임의의 두 도시 사이를 직항이나 경유로 오갈 수 있는지 알고 싶었다. 지안지아는 답을 바로 알려주는 대신 게임을 제안했다. 메이유는 "도시 $x$와 도시 $y$는 직항 노선으로 이어져 있는가?"라는 형태로 질문하고, 지안지아는 예 또는 아니오로 즉시 답한다. 메이유는 모든 도시 쌍을 정확히 한 번씩 물으므로 질문은 모두 $r = n(n-1)/2$개다.

$i < r$인 $i$가 하나라도 있어서 처음 $i$개의 답만으로 모든 도시 사이를 오갈 수 있는지 없는지 확정할 수 있다면 메이유가 이긴다. 그렇지 않고 $r$개의 답을 전부 들어야 한다면 지안지아가 이긴다.

게임을 더 재미있게 하려고 두 사람은 지안지아가 실제 항공망을 잊어도 된다는 데 합의했다. 지안지아는 메이유의 질문을 받아가며 항공망을 지어낼 수 있고, 이미 한 답과 모순만 없으면 된다. 어떤 항공망이 처음 $i$개의 답과 일치한다는 것은, 그 $i$개의 질문 중 답이 예인 도시 쌍은 직항 노선으로 이어져 있고 답이 아니오인 도시 쌍은 이어져 있지 않다는 뜻이다. 아직 묻지 않은 쌍은 이어져 있어도 되고 아니어도 된다. 처음 $i$개의 답과 일치하는 항공망 중 전체가 연결된 것과 연결되지 않은 것이 둘 다 있으면, 메이유는 아직 아무것도 확정하지 못한다.

메이유가 질문하는 순서가 주어진다. 지안지아가 이기는 답의 나열 중 사전순으로 가장 앞서는 것을 구하라. 답은 아니오를 $0$, 예를 $1$로 적고 $0$이 $1$보다 앞선다. $n \ge 2$이면 지안지아가 이기는 답의 나열은 항상 존재한다.

첫 줄에 도시의 수 $n$이 주어진다.

다음 $r = n(n-1)/2$개의 줄에는 메이유가 묻는 순서대로 질문이 하나씩 주어진다. 각 줄에는 서로 다른 두 정수 $x$와 $y$가 공백으로 구분되어 주어지며, 도시 $x$와 도시 $y$가 직항 노선으로 이어져 있는지 묻는 질문을 뜻한다. 순서를 무시한 쌍 $(x, y)$는 입력 전체에서 정확히 한 번씩 나온다.

길이가 $r$인 문자열을 한 줄에 출력한다. $i$번째 문자는 $i$번째 질문에 대한 지안지아의 답이며, 아니오는 $0$, 예는 $1$로 적는다. 지안지아가 이기는 문자열이 여러 개면 사전순으로 가장 앞서는 것을 출력한다.

• $2 \le n \le 100$
• $0 \le x < n$, $0 \le y < n$, $x \ne y$