OI题库

【题目描述】

让我们考虑一个有n个门的电路。这些门从0到n-1编号。每个门有着确定数目的输入和一个输出。所有这些输入输出的值都是0，1或1/2.每个输入都来自某个门的一个输出，这两者的值相等。每个输出可以和不止一个输入相连。编号为0，1的门是特殊的——它们没有输入，并且输出值总是等于其编号：0号门总是输出0，1号门总是输出1.我们说门的输出状态（简称为门的状态）是合法的，如果满足以下条件：

·a) 输出值等于0并且这个门的输入中0多于1.

·b) 输出值等于1/2并且这个门的输入中0与1数目相同。

·c) 输出值等于1并且这个门的输入中1多于0.

·d) 这个门是特殊的，即其编号为0或1，并且其输出值等于编号。

当所有门的状态都合法时，我们称这个电路是合法的。我们说一个门的状态是固定的，如果这个门的输出状态在所有有效电路中都一样。

你需要读入电路的描述，并且对每个门，计算出它的状态是否固定，如果固定，这个状态是多少。

【输入格式】

输入文件的第一行是门的数量n，2<=n<=10000.

第2行到第n-1行描述了门的连接状态。第i行包含i号门的输入。这一行开头有一个整数k_i表示输入个数（k_i>=1），接下来有k_i个整数，描述了i号门的输入来自哪些门的输出。其中k_i>=1。这些数都用空格隔开。所有门的输入数之和不超过200000.

【输出格式】

输出n行，依次描述从0号门到n-1号门的固定情况。

根据i-1号门的状态，第i行应当输出：

·0——如果i号门的状态固定为0，

·1/2——如果i号门的状态固定为1/2，

·1——如果i号门的状态固定为1，

·?（问号）——如果不确定

【样例输入】

5

2 0 1

2 4 2

2 2 4

【样例输出】

0

1

1/2

?

?

【提示】

样例如下图：

【来源】

POI 2004 Gates