XI Olympiad in Informatics 2003/2004
|
II stage competition |
Source file: | bra.xxx (xxx=pas,c,cpp) |
Memory limit: | 32 MB |
Let us consider a circuit consisting of n gates. The gates are numbered from 0 to n-1. Each gate has a certain number of inputs and exaclty one output. Each of them (inputs and outputs) may be in either one of the states 0, 1 or 1/2. Each input is connected to exactly one output of some gate. Input's state equals the state of the output it is connected to. Each output may be connected to an aribtrary number of inputs. The gates with numbers 0 i 1 are special --- they don't have any input at all while their outputs are always in the following states: 0 for a gate with a number 0, 1 for a gate with a number 1. We say that the state of the output of a gate (in short: gate's state) is "valid", if:
Write a programme that:
The first line of the standard input contains the number of gates n, 2 <= n <= 10,000. The following n-2 lines contain the descriptions of gates' connections - line no. i describes inputs of the gate no. i. There is the number k_i of inputs of this gate, followed by k_i numbers of gates, k_i >= 1. Those are the numbers of gates whose outputs are connected to successive inputs of the gate's no. i. Numbers in each line are separated by single spaces. The total number of all inputs of all gates does not exceed 200,000.
For the following input data:
5 2 0 1 2 4 2 2 2 4
the correct answer ist:
0 1 1/2 ? ?