题目描述

JOI 国由 $N$ 个城市和连接它们的 $M$ 条道路构成。城市被编号为 $1$ 到 $N$，道路被编号为 $1$ 到 $M$。道路 $i \ (1 \le i \le M)$ 双向连接城市 $A_i$ 和城市 $B_i$。这里，$A_i < B_i$。此外，对于任意两个城市的配对，连接它们的道路最多只有 $1$ 条。也就是说，$A_i \ne A_j$ 或 $B_i \ne B_j \ (1 \le i < j \le M)$。

比太郎现在在城市 $s$，正在制定旅行计划。旅行计划用数列 $v = (v_1, v_2, \dots)$ 表示，它表示比太郎将访问的城市编号的顺序。这里，$v$ 是由 $1$ 以上 $N$ 以下的整数组成的、长度至少为 $1$ 的数列。由于比太郎对旅行中访问城市编号的顺序有很强的执念，数列 $v$ 在其长度为 $l$ 时，必须满足以下所有条件。

1. $v_1 = s$。
2. 对于各个 $j = 1, 2, \dots, l - 1$，城市 $v_j$ 与城市 $v_{j+1}$ 由道路连接。
3. 对于各个 $j = 1, 2, \dots, l - 1$，当 $j$ 为奇数时有 $v_j < v_{j+1}$ 成立，当 $j$ 为偶数时有 $v_j > v_{j+1}$ 成立。

例如，$v = (2)$ 和 $v = (1, 4, 1, 5, 3)$ 满足第 $3$ 个条件，但 $v = (3, 2)$ 不满足第 $3$ 个条件。

比太郎想知道：无论制定怎样的旅行计划都无法到达的城市，即在满足上述所有条件的任意数列 $v$ 中都不会出现其编号的城市，总共有多少个。

由于你不知道比太郎当前在什么城市，因此希望对 $s = 1, 2, \dots, N$ 各自，计算比太郎问题的答案。

给定关于 JOI 国的城市与道路的信息，请编写程序，对 $s = 1, 2, \dots, N$ 各自，求出无论比太郎制定怎样的旅行计划都无法到达的城市个数。

输入格式

输入按以下格式给出。

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

输出格式

输出 $N$ 行。第 $k \ (1 \le k \le N)$ 行输出当 $s = k$ 时，无论比太郎制定怎样的旅行计划都无法到达的城市个数。

4 4
1 2
1 3
1 4
3 4

0
3
0
3

2 0

1
1

4 3
1 3
3 4
2 4

2
1
1
3

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

1
1
3
5
3
5

提示

样例解释

样例 $1$ 解释

当 $s = 1$ 时，作为 $v$ 可能的数列有 $v = (1)$、$v = (1, 2)$、$v = (1, 3)$、$v = (1, 4, 1)$、$v = (1, 4, 1, 2)$ 等。不存在无论制定怎样的旅行计划都无法到达的城市。

当 $s = 2$ 时，作为 $v$ 可能的数列只有 $v = (2)$。无论制定怎样的旅行计划，都无法到达城市 $1, 3, 4$。

当 $s = 3$ 时，作为 $v$ 可能的数列有 $v = (3)$、$v = (3, 4, 1, 2)$ 等。不存在无论制定怎样的旅行计划都无法到达的城市。

当 $s = 4$ 时，作为 $v$ 可能的数列只有 $v = (4)$。无论制定怎样的旅行计划，都无法到达城市 $1, 2, 3$。

该输入示例满足子任务 $2, 5$ 的约束。

样例 $2$ 解释

当 $s = 1$ 时，作为 $v$ 可能的数列只有 $v = (1)$。无论制定怎样的旅行计划，都无法到达城市 $2$。

当 $s = 2$ 时，作为 $v$ 可能的数列只有 $v = (2)$。无论制定怎样的旅行计划，都无法到达城市 $1$。

该输入示例满足子任务 $2, 4, 5$ 的约束。

样例 $3$ 解释

该输入示例满足所有子任务的约束。

样例 $4$ 解释

该输入示例满足子任务 $2, 4, 5$ 的约束。

约束

• $1 \le N \le 300\,000$。
• $0 \le M \le 300\,000$。
• $1 \le A_i < B_i \le N \ (1 \le i \le M)$。
• $A_i \ne A_j$ 或 $B_i \ne B_j \ (1 \le i < j \le M)$。
• 输入的值全部为整数。

子任务

• （12 分）$N \le 1000$，$M = N - 1$。另外，存在一个将 $(1, 2, \dots, N)$ 重新排列得到的某个排列 $P = (P_1, P_2, \dots, P_N)$，并且对各个 $i = 1, 2, \dots, N - 1$，存在一条连接 $P_i$ 与 $P_{i+1}$ 的道路。
• （19 分）$N \le 1000$，$M \le 1000$。
• （15 分）$M = N - 1$。另外，存在一个将 $(1, 2, \dots, N)$ 重新排列得到的某个排列 $P = (P_1, P_2, \dots, P_N)$，并且对各个 $i = 1, 2, \dots, N - 1$，存在一条连接 $P_i$ 与 $P_{i+1}$ 的道路。
• （17 分）对每个城市，与该城市直接由道路连接的城市最多为 $2$ 个。
• （37 分）没有额外约束。