Problem Description

Let us consider a circuit containing $n$ gates.

The gates are numbered from $0$ to $n-1$. Each gate has several inputs and one output.

Each input and output can only be in one of three states: $0$, $1$, or $\dfrac{1}{2}$. Each input is connected to the output of some gate, so the state of an input is equal to the state of the output it is connected to. Each output may be connected to any number of inputs.

Gates $0$ and $1$ are two special gates. The output of gate $0$ is always $0$, and the output of gate $1$ is always $1$.

The condition for a gate’s output state is as follows:

1. If the number of $0$ among its inputs is greater than the number of $1$, then the output state is $0$.

2. If the number of $0$ among its inputs is equal to the number of $1$, then the output state is $\dfrac{1}{2}$.

3. If the number of $0$ among its inputs is less than the number of $1$, then the output state is $1$.

4. For gates $0$ and $1$, they output $0$ and $1$ respectively.

Now you are given the circuit information. Please write a program to determine the states of all gates whose states can be determined.

Input Format

The first line contains an integer $n$.

The next $n-2$ lines describe the connections of the gates. Line $i$ describes the input terminals of gate $i$: an integer $k_i$ indicating the number of its input terminals, followed by $k_i$ integers giving the indices of the gates connected to each input terminal.

Output Format

Output $n$ lines, representing the output states of the $n$ gates. If it can be determined, output the specific state value; otherwise output $?$.

5
2 0 1
2 4 2
2 2 4

0
1
1/2
?
?

Hint

For all testdata, $2 \le n \le 10000$, $k_i \ge 1$. The testdata guarantees that the total number of input terminals over all gates does not exceed $200000$.

Translated by ChatGPT 5