说明

禁忌纸牌游戏由编号为 $1$ 到 $N$ 的 $N$ 名玩家和一副牌组成。每张牌上写有一个介于 $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$ 轮流，直至某位玩家输掉游戏。

有一种简单的确定性策略称为 优先出第一张牌，即每位玩家优先打出其持有的第一张牌（即数字为 $A_i$ 的牌），仅当无法打出第一张牌时才打出第二张牌（数字为 $B_i$）。

你的任务是，假设所有玩家都采用优先出第一张牌策略，对于每位玩家，计算会导致该玩家输掉游戏的不同可能禁忌数字 $X$ 的个数。

例如，假设有 $N = 3$ 名玩家，牌上的数字范围为 $1$ 到 $M = 6$（包含）。用 $\langle A_i, B_i \rangle$ 表示第 $i$ 位玩家抽到的两张牌上的数字。玩家 1 持有 $\langle 1, 2 \rangle$，玩家 2 持有 $\langle 2, 4 \rangle$，玩家 3 持有 $\langle 4, 2 \rangle$。

所有可能的游戏过程如下：

• $X = 1 \rightarrow$ 玩家 3 输；玩家 1 打出 2，玩家 2 打出 4，最后玩家 3 无法行动。
• $X = 2 \rightarrow$ 玩家 3 输；玩家 1 打出 1，玩家 2 打出 4，最后玩家 3 无法行动。
• $X = 3 \rightarrow$ 玩家 1 输；玩家 1 打出 1，玩家 2 打出 2，玩家 3 打出 4，最后玩家 1 无法行动。
• $X = 4 \rightarrow$ 玩家 3 输；玩家 1 打出 1，玩家 2 打出 2，最后玩家 3 无法行动。
• $X = 5 \rightarrow$ 玩家 1 输；玩家 1 打出 1，玩家 2 打出 2，玩家 3 打出 4，最后玩家 1 无法行动。
• $X = 6 \rightarrow$ 玩家 1 输；玩家 1 打出 1，玩家 2 打出 2，玩家 3 打出 4，最后玩家 1 无法行动。

总结，$X = 3, 5, 6$ 会导致玩家 1 输掉游戏，$X = 1, 2, 4$ 会导致玩家 3 输掉游戏。另一方面，在此例中不存在会导致玩家 2 输掉游戏的禁忌数字 $X$。

输入格式

输入第一行包含两个整数 $N$ 和 $M$（$1 \leq N \leq 100\,000$；$2 \leq M \leq 10^6$），分别表示玩家数量和牌上可能的最大数字。接下来 $N$ 行，每行包含两个整数 $A_i$ 和 $B_i$（$1 \leq A_i, B_i \leq M$；$A_i \neq B_i$），分别表示第 $i$ 位玩家第一张和第二张牌上的数字。

输出格式

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

3 6
1 2
2 4
4 2

3
0
3

4 10
1 5
2 6
3 7
4 8

4
2
2
2

提示

样例 #1 解释

此为题目描述中的示例。

翻译由 DeepSeek 完成