# 题目内容

塔子哥老家有一座分层水库，这个水库按高度分为 $N$ 层，从高到低编号分别为 $0,1,...,N-1$ 。除最低层外每一层上都有一个蓄水池，通过若干管道将每一层面水池中的水输送至最低层的水库中，管道之间通过水控制阀连接(水控制阀总数为 $M$ )，现要找到每一层中离水库最近的关键水控制阀。

某一层的关键水控制阀定义为从该层蓄水池流向水库的水要么经过该水控制阀且不全部流向更低层(不考虑水库层)关键水控制阀，或者不经过该水控制阀且必须经过更低层(不考虑水库层)的关键水控制阀。

即：第 $n$ ( $n \lt N - 2$ )层的关键水控制阀为 $k_n$ ，从 $n$ 层蓄水池流向水库的水如果流经 $k_n$ ，则必须存在流经 $k_n$ 的水未流经任何 $k_i$ ( $n\lt i\le N-2$ )，如未流经 $k_n$ ，则至少流经一个 $k_i$ ( $n\lt i\le N-2$ )。其中，第 $N-2$ 层的关键水控制阀为 $k_{N -2}$ ，必须使得所有从第 $N-2$ 层蓄水池流向水库的水全部经过 $k_{N-2}$

关键门阀有如下性质：

任何路径从水池流向水库的水，都必须经过至少一个关键水控制阀；

关键水控制阀从底层向上层确定，每层只有至多一个关键水控制阀；

如果一层中从蓄水池流向水库的水全部流经了更低层的关键水控制阀则该层无关键水控制阀；

如果一层中有多个水控制阀符合要求，则更靠近水库的确定为关键水控制阀；

水库层无关键水控制阀。

# 输入描述

第一行：输入两个整数 $N$ 和 $M$ ，其分别表示层数与水控制阀总数。

第二行：输入 $M$ 个数字表示 $ID$ 为 $0$ 到 $M-1$ 的水控制阀所在层数，层数为递增顺序。

接下来输入 $M$ 行，第 $i$ 行中的第一个数字 $k_i$ ，表示通过水控制阀 $i- 1$ 下一步可到达的水控制阀个数。该行后面的 $k_i$ 个数字分别表示这些水控制阀的编号 $ID$ ，若 $k_i$ 为 $0$ 则则表示下一步没有可到达的水控制阀。

注：最后一层有且只有一个水控制阀连接到水库，不同层中水只能由高层流向低层，同一层中水只能由小 $ID$ 的水控制阀流向大 $ID$ 的水控制阀。每层的最小 $ID$ 的水控制阀只能接收来自该层蓄水池的水。

其中， $1\le M\le 2000$ ， $1\le N\le 2000$ ， $0\le k_i \le M$ 。

# 输出描述

按从高到低输出每层(不包含水库层) 离水库最近(从该水控制阀到水库所经历的水控制阀数最少)的关键水控制阀编号，若该层不存在关键水控制阀，则该层输出 $-1$ 。

# 样例

# 样例1

输入

3 10
0 0 0 1 1 1 1 1 1 2 
2 1 2
1 7
1 4
2 4 5
1 6
1 6
2 7 8
1 9
1 9
0

输出

1 6

样例解释

先考虑第 $1$ 层，由于没有更低层，所以该层的关键水控制阀需要水池 $1$ 中的流向水库的水全部流经该水控制阀，所以 $3$ 和 $6$ 符合条件，而水控制阀 $6$ 离水库最近，故第 $1$ 层结果为水控制阀 $6$ 。

接着考虑第 $0$ 层，若 $2$ 为关键水控制阀，则流经水控制阀 $1$ 的水并没有经过任何关键水控制阀，不符合条件。

水控制阀 $1$ 和水控制阀 $0$ 均符合关键水控制阀的定义，而水控制阀 $1$ 离水库更近，所以离水库最近的关键水控制阀为水控制阀 $1$ 。

所以最终结果为 1 6 。

# 样例2

输入

6 1 9
0 0 0 1 1 2 2 2 2 3 3 4 4 4 4 4 4 4 5
1 1
2 2 4
2 7 8
1 4
1 7
1 6
1 7
4 8 12 14 15
1 15
1 10
0
2 12 13
1 14
1 14
2 15 16
1 17
1 18
1 18
0

输出

2 -1 7 -1 14

样例解释

先考虑第 $4$ 层，由于没有更低层，所以该层的关键水控制阀需要水池1中的流解释向水库的水全部流经该水控制阀，所以 $11$ 和 $14$ 符合条件，而水控制阀 $14$ 离水库最近，故第 $1$ 层结果为水控制阀 $14$ ；

接着考虑第 $3$ 层，由于没有通向水库的水控制阀，故为 $-1$ ；

接着考虑第 $2$ 层，由于该层所有水流均流向水控制阀 $7$ ，而流经水控制阀 $7$ 的水有流经更低层关键水控制阀 $14$ 的也有流向非关键水控制阀 $15$ 的故 $7$ 为关键水控制阀， $5,6$ 水控制阀同理，但 $7$ 离水库最近，故结果为水控制阀 $7$ ；

接着考虑第 $1$ 层，第一层流经水控制阀 $3,4$ 的水均流向了更低层的关键水控制阀 $7$ 故该层无关键水控制阀，结果为 $-1$ ；

最后考虑第 $0$ 层，可以得到 $2$ 为关键水控制阀，由于该层未流经水控制阀 $2$ 的水均流向更低层的关键水控制阀 $7$ ，且流经 $2$ 的水有未流经任何关键水控制阀到达水库的路线，故 $2$ 为关键水控制阀。同样 $0$ ， $1$ 也为关键水控制阀，而 $2$ 距离水库更近，故关键水控制阀为水控制阀 $2$ ；

综上，最终结果为 2 -1 7 -1 14 。

# 题解

to do

← 第2题-获取最多食物第1题-塔子哥监考 →