配点: 6 点
問題文
研究者高桥先生由于撰写了许多合著论文,因此相关人员出于敬意和幽默的意味创造了高桥数这一概念。高桥数如下所示,针对每位研究者来确定。
- 高桥先生的高桥数是 0 。
- 高桥数是 n 与研究者有合著经验,高桥数是 n 与高桥数低于某数的研究者没有合著经验的研究者的高桥数是 n+1 。
- 对于以上事项无法确定高桥数的研究者,其高桥数未被定义。
目前,在这个世界上,包括高桥先生在内 N 位研究者, M 有 合著论文篇数, i 第n篇合著论文是 K_i 位研究者 R_{i,1}, \dots, R_{i,K_i} 的合著。这里,假设高桥先生是研究者 1 。在这种情况下, N 关于每位研究人员,高桥数是否被定义了?如果已定义,其值是多少?
制約
- 2 \leq N \leq 10^5
- 1 \leq M \leq 10^5
- 2 \leq K_i \leq N
- K_1+K_2+\dots+K_M \leq 2 \times 10^5
- 1 \leq R_{i,1} < \dots < R_{i,K_i} \leq N
- 所有输入值均为整数
入力
输入是按以下格式从标准输入给出的。
N M
K_1
R_{1,1} \cdots R_{1,K_1}
\vdots
K_M
R_{M,1} \cdots R_{M,K_M}
出力
输出是
由 N 行组成。j 行目 (1 \leq j \leq N) 对于研究人员 j 的高桥数,如果存在,则为该高桥数;如果不存在,则为 -1 。
入力例 1
6 3 3 1 2 3 2 3 4 2 5 6
出力例 1
0 1 1 2 -1 -1
6 每位研究人员的高桥数可以如下计算。
- 研究者 1 (高桥氏)的高桥数根据定义 0 。
- 研究者 2,3 的高桥数为 0 与研究人员 1 有过共同著作经验,并且与高桥数 0 以下的研究人员没有共同著作经验,因此其高桥数为 1 。
- 研究者 4 的高桥数为 1 与研究人员 3 有过共同著作经验,并且与高桥数 1 以下的研究人员没有共同著作经验,因此其高桥数为 2 。
- 研究者 5,6 分别有共同著作经验,但与高桥数被定义的研究人员没有共同著作经验,因此其高桥数未被定义。
综上所述,从研究人员 1 开始,高桥数依次为 0,1,1,2,\times,\times (\times 表示高桥数不存在) 。
入力例 2
4 3 2 1 2 2 2 3 2 3 4
出力例 2
0 1 2 3
入力例 3
4 1 3 2 3 4
出力例 3
0 -1 -1 -1
入力例 4
11 5 4 2 6 9 10 3 1 3 8 5 2 4 6 8 10 2 6 7 4 5 6 7 8
出力例 4
0 2 1 2 2 2 2 1 3 2 -1