“禁忌卡牌”游戏由 $N$ 名编号为 $1$ 到 $N$ 的玩家和一副卡牌进行。每张卡牌上写有一个 $1$ 到 $M$（含 $1$ 和 $M$）之间的数字，且可能存在多张写有相同数字的卡牌。

最初，每位玩家依次抽取两张卡牌。第 $i$ 位玩家抽到的第一张和第二张卡牌上的数字分别为 $A_i$ 和 $B_i$。保证 $A_i \neq B_i$。在所有玩家抽完卡牌后，游戏主持人（非玩家）将决定并指定一个 $1$ 到 $M$ 之间的数字 $X$ 作为禁忌数字。

在每一轮中，玩家必须打出一张手牌并将其弃掉。所打出的卡牌上的数字必须是之前未被出过的，且该数字不能等于 $X$。如果玩家在轮到自己时无法打出任何卡牌（即手中没有卡牌，或者手中所有卡牌上的数字要么已经被出过，要么等于 $X$），则该玩家输掉游戏。

游戏按 $1, 2, \dots, N-1, N, 1, 2, \dots$ 的顺序循环进行，直到有玩家输掉游戏。

游戏中存在一种名为“先出第一张牌”（first card first）的朴素确定性策略，即每位玩家优先打出他们手中的第一张牌（即编号为 $A_i$ 的牌），只有在无法打出第一张牌时，才会打出第二张牌（编号为 $B_i$）。

你的任务是确定对于每位玩家，有多少种不同的禁忌数字 $X$ 会导致该玩家输掉游戏，假设所有玩家都采用“先出第一张牌”的策略。

例如，设 $N = 3$ 名玩家，卡牌数字在 $1$ 到 $M = 6$ 之间。设 $A_i, B_i$ 表示第 $i$ 位玩家抽到的卡牌数字。玩家 $1$ 持有 $1, 2$，玩家 $2$ 持有 $2, 4$，玩家 $3$ 持有 $4, 2$。

所有可能的对局情况如下：

• $X = 1 \to$ 玩家 $3$ 输；玩家 $1$ 出 $2$，玩家 $2$ 出 $4$，最后玩家 $3$ 无法出牌。
• $X = 2 \to$ 玩家 $3$ 输；玩家 $1$ 出 $1$，玩家 $2$ 出 $4$，最后玩家 $3$ 无法出牌。
• $X = 3 \to$ 玩家 $1$ 输；玩家 $1$ 出 $1$，玩家 $2$ 出 $2$，玩家 $3$ 出 $4$，最后玩家 $1$ 无法出牌。
• $X = 4 \to$ 玩家 $3$ 输；玩家 $1$ 出 $1$，玩家 $2$ 出 $2$，最后玩家 $3$ 无法出牌。
• $X = 5 \to$ 玩家 $1$ 输；玩家 $1$ 出 $1$，玩家 $2$ 出 $2$，玩家 $3$ 出 $4$，最后玩家 $1$ 无法出牌。
• $X = 6 \to$ 玩家 $1$ 输；玩家 $1$ 出 $1$，玩家 $2$ 出 $2$，玩家 $3$ 出 $4$，最后玩家 $1$ 无法出牌。

总之，$X = 3, 5, 6$ 会导致玩家 $1$ 输掉游戏，$X = 1, 2, 4$ 会导致玩家 $3$ 输掉游戏。另一方面，在这个例子中，没有任何禁忌数字 $X$ 会导致玩家 $2$ 输掉游戏。

输入格式

输入的第一行包含两个整数：$N$ 和 $M$ ($1 \le N \le 100\,000; 2 \le M \le 10^6$)，分别表示玩家人数和卡牌上可能出现的最大数字。接下来的 $N$ 行，每行包含两个整数：$A_i$ 和 $B_i$ ($1 \le A_i, B_i \le M; A_i \neq B_i$)，分别表示第 $i$ 位玩家的第一张和第二张卡牌上的数字。

输出格式

输出包含 $N$ 行。第 $i$ 行包含一个整数，表示会导致第 $i$ 位玩家输掉游戏的禁忌数字 $X$ 的不同可能数量。

样例

样例输入 1

3 6
1 2
2 4
4 2

样例输出 1

3
0
3

说明 1

这是题目描述中的例子。

样例输入 2

4 10
1 5
2 6
3 7
4 8

样例输出 2

4
2
2
2