게이트

$n$개의 게이트로 이루어진 회로를 생각하자. 게이트에는 $0$번부터 $n-1$번까지 번호가 매겨져 있다. 각 게이트는 여러 개의 입력과 정확히 하나의 출력을 가진다. 모든 입력과 출력은 $0$, $1/2$, $1$ 중 하나의 상태를 가진다.

각 입력은 어떤 게이트의 출력 하나에 연결되며, 그 입력의 상태는 연결된 출력의 상태와 같다. 하나의 출력은 임의의 개수의 입력에 연결될 수 있다.

$0$번과 $1$번 게이트는 특별하다. 이 두 게이트는 입력이 전혀 없으며, 출력의 상태가 항상 고정되어 있다. $0$번 게이트의 출력은 항상 $0$, $1$번 게이트의 출력은 항상 $1$이다.

게이트의 출력 상태(줄여서 게이트의 상태)가 유효하다(valid)는 것은 다음 중 하나를 만족하는 경우이다.

1. 상태가 $0$이고, 상태가 $0$인 입력의 개수가 상태가 $1$인 입력의 개수보다 많다.
2. 상태가 $1/2$이고, 상태가 $0$인 입력의 개수와 상태가 $1$인 입력의 개수가 같다.
3. 상태가 $1$이고, 상태가 $1$인 입력의 개수가 상태가 $0$인 입력의 개수보다 많다.
4. 특별한 게이트($0$번 또는 $1$번)이고, 그 상태가 각각 $0$ 또는 $1$이다.

회로의 상태가 유효하다는 것은 모든 게이트의 상태가 유효하다는 뜻이다. 어떤 게이트의 상태가 고정되어 있다(fixed)는 것은, 회로의 모든 유효한 상태에서 그 게이트가 항상 같은 상태를 가진다는 뜻이다.

각 게이트에 대해 그 상태가 고정되어 있는지 판정하고, 고정되어 있다면 그 값을 구하는 프로그램을 작성하라.

첫째 줄에 게이트의 개수 $n$이 주어진다 ($2 \le n \le 10{,}000$).

이어지는 $n-2$개의 줄은 게이트의 연결을 설명한다. 위에서부터 순서대로 이 줄들은 게이트 $2, 3, \dots, n-1$에 대응하며, 게이트 $i$에 해당하는 줄은 그 게이트의 입력을 나타낸다. 각 줄은 그 게이트의 입력 개수 $k_i$로 시작하고($k_i \ge 1$), 이어서 $k_i$개의 게이트 번호가 주어진다. 이 번호들은 게이트 $i$의 각 입력에 출력이 연결된 게이트들의 번호이며, 입력 순서대로 나열된다. 한 줄의 숫자들은 공백 하나로 구분된다.

모든 게이트의 입력 개수의 총합은 $200{,}000$을 넘지 않는다.

$n$개의 줄을 출력한다. $i$번째 줄은 게이트 $i-1$의 상태에 대한 결과이며, 다음 중 하나를 출력한다.

• 0 — 상태가 $0$으로 고정된 경우
• 1/2 — 상태가 $1/2$로 고정된 경우
• 1 — 상태가 $1$로 고정된 경우
• ? — 상태가 고정되지 않은 경우