You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

让我们考虑一个包含 $n$ 个门的电路。

门从 $0$ 到 $n-1$ 编号，每个门都包含若干个输入和一个输出。

每一个输入和输出都只可能是 $0,1,\dfrac{1}{2}$ 三种状态，每个输入都连接着某个门的输出，输入的状态就等于它连接的输出的状态值，而每个输出可能连接着任意多个输入。

$0$ 和 $1$ 是很特殊的两个门。门 $0$ 的输出永远为 $0$，门 $1$ 的输出永远为 $1$。

一个门有效的输出状态条件如下:

1. 它的输入中 $0$ 的个数多于 $1$ 的个数那么输出状态为 $0$。

2. 它的输入中 $0$ 的个数等于 $1$ 的个数那么输出状态为 $\dfrac{1}{2}$。

3. 它的输入中 $0$ 的个数少于 $1$ 的个数那么输出状态为 $1$。

4. 对于门 $0$ 和 $1$，他们分别输出 $0$ 和 $1$。

现在给出电路信息，请你编写一个程序，确定所有可以确定状态的门的状态分别是什么。

输入格式

第一行一个数 $n$。

接下来 $n-2$ 行表示门的连接信息，第 $i$ 行描述第 $i$ 个门的输入端，一个数 $k_i$ 表示它的输入端个数，接下来 $k_i$ 个数分别表示每个输入端的门的编号。

输出格式

输出 $n$ 行，表示 $n$ 个门的输出状态。如果确定，请输出具体状态值，否则输出 $?$ 。

5
2 0 1
2 4 2
2 2 4

0
1
1/2
?
?

提示

对于全部数据，$2 \le n \le 10000,k_i \ge 1$，数据保证所有门的输入端总数不超过 $200000$。