样例下载

题目描述

A 国对 B 国的军事基地进行了轰炸，摧毁了军事基地之间的所有道路。

已知 B 国共有 $N$ 个军事基地，编号为 $1$ ~ $N$，每个军事基地上都有驻军。由于所有道路被炸毁，B 国准备重新布置军事基地。B 国指挥官依次发出了 $M$ 条命令，每条命令包含两个或三个整数，具体形式和含义如下：

• 0 i 表示基地 i 的驻军全部撤出
• 1 i j 表示在两个仍有驻军的基地 $i$ 和 $j$ 之间修建一条道路
• 2 i 表示将之前修建的第 $i$ 条道路炸毁

对于一个军事基地 i，如果该基地仍有驻军，或者可以通过一条路径到达某一个仍有驻军的军事基地，则认为军事基地 i 仍然属于 B 国，否则认为军事基地 i 失守。

问：对于每个军事基地 i, 即当 i = 1, 2, ……, N 时，在第几次命令后，基地 i 失守？如果基地 i 一直未失守，则输出 0.

输入格式

第一行：两个整数 $N, M$。

接下来 $M$ 行，每行两或三个整数，描述一条命令，具体含义如题所述。数据保证所有命令均是合法的，例如不会两次从同一个基地撤军，修建的道路一定是在两个仍有驻军的基地之间，炸毁的道路肯定是存在的，不会两次炸毁同一条道路。

输出格式

共 $N$ 行，每个答案占一行。

样例输入

4 7
0 3
1 1 2
1 2 4
0 2
2 2
2 1
0 4

样例输出

0 
6 
1 
7

【数据范围】

• 25% 的数据满足 $N ≤ 10^3$，$M ≤ 2×10^3$。

• 100% 的数据满足 $1 ≤ N ≤ 10^5$, $0 ≤ M ≤ 2×10^5$