← 返回题目列表

AtCoder · typical90_bb

054. 高桥数(★6)

中文机器翻译题面 查看原题

配点: 6 点

問題文

研究者高桥先生由于撰写了许多合著论文,因此相关人员出于敬意和幽默的意味创造了高桥数这一概念。高桥数如下所示,针对每位研究者来确定。

  1. 高桥先生的高桥数是 0 。
  2. 高桥数是 n 与研究者有合著经验,高桥数是 n 与高桥数低于某数的研究者没有合著经验的研究者的高桥数是 n+1 。
  3. 对于以上事项无法确定高桥数的研究者,其高桥数未被定义。

目前,在这个世界上,包括高桥先生在内 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