给定一个包含 $N$ 个顶点和 $M$ 条边的有向图。顶点编号为 $1$ 到 $N$，边编号为 $1$ 到 $M$。第 $i$ 条边 ($1 \le i \le M$) 从顶点 $A_i$ 指向顶点 $B_i$。

你的任务是为图中的每个顶点分配颜色 $1, \dots, N$，使得满足以下条件：

• 对于每个顶点 $i$ ($1 \le i \le N$)，设 $c_i$ 为分配给它的颜色。对于任意一对满足 $c_i = c_j$ 的顶点 $(i, j)$ ($1 \le i < j \le N$)，必须存在从顶点 $i$ 到顶点 $j$ 的路径，或者从顶点 $j$ 到顶点 $i$ 的路径（或两者皆有）。
• $\max\{c_1, \dots, c_N\}$ 的值尽可能小。

请构造一种满足上述条件的染色方案。

输入格式

输入通过标准输入给出，格式如下：

$N \ M$ $A_1 \ B_1$ $A_2 \ B_2$ $\vdots$ $A_M \ B_M$

• 输入中的所有值均为整数。
• $1 \le N \le 7 \times 10^3$
• $0 \le M \le 7 \times 10^3$
• $1 \le A_i, B_i \le N$ ($1 \le i \le M$)
• $A_i \neq B_i$ ($1 \le i \le M$)
• $(A_i, B_i) \neq (A_j, B_j)$ ($1 \le i < j \le M$)

输出格式

输出满足条件的颜色分配 $c_1, c_2, \dots, c_N$。

样例

输入格式 1

5 5
1 4
2 3
1 3
2 5
5 1

输出格式 1

2 1 1 2 2

输入格式 2

5 7
1 2
2 1
4 3
5 1
5 4
4 1
4 5

输出格式 2

2 2 1 1 1

输入格式 3

8 6
6 1
3 4
3 6
2 3
4 1
6 4

输出格式 3

4 4 4 4 3 4 2 1