Determine Circuit Gate States

Consider a circuit consisting of \(n\) gates numbered from \(0\) to \(n-1\). Each gate has several inputs and exactly one output. Every input and output can only take one of the three states: \(0\), \(1\), or \(\frac{1}{2}\). Each input is connected to the output of some gate and gets its state from that connection. An output may be connected to one or more inputs.

There are two special gates: gate \(0\) always outputs \(0\) and gate \(1\) always outputs \(1\).

The output of any other gate is determined by the following rules based on its inputs:

• If the number of inputs in state \(0\) is greater than the number of inputs in state \(1\), then its output is \(0\).
• If the number of inputs in state \(0\) is equal to the number of inputs in state \(1\), then its output is \(\frac{1}{2}\).
• If the number of inputs in state \(0\) is less than the number of inputs in state \(1\), then its output is \(1\).

Given the description of a circuit, determine the state of every gate whose output can be determined.

Input Format: The circuit information is given in the following format. The first line contains an integer \(n\) (\(n \ge 2\)), the total number of gates. The following \(n\) lines each describe one gate in order from gate \(0\) to gate \(n-1\). Each gate description begins with an integer \(k\) which is the number of inputs for that gate, followed by \(k\) space separated integers. Each of these integers is the index of another gate whose output is connected to this input.

Note: Even if a gate has no input (\(k = 0\)), its state can only be determined if it is one of the special gates \(0\) or \(1\); otherwise, it remains undetermined.

Output Format: For every gate whose output state can be determined, output a line in ascending order of gate indices containing the gate's index and its determined state separated by a space. The state should be output as 0, 1, or 1/2.

inputFormat

The first line contains an integer \(n\) — the number of gates in the circuit. The next \(n\) lines each describe one gate from \(0\) to \(n-1\). Each of these lines starts with an integer \(k\), representing the number of inputs for that gate, followed by \(k\) integers indicating the indices of the gates that provide the inputs.

outputFormat

For each gate whose output state can be determined, output a single line containing the gate's index and its output state separated by a space. The gates must be listed in increasing order of indices. The output state is one of: 0, 1, or 1/2.

sample

3
0
0
2 0 1

0 0
1 1
2 1/2