P15593 [ICPC 2020 Jakarta R] Forbidden Card

禁忌纸牌游戏由编号为 $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$ 位玩家输掉游戏的不同可能禁忌数字的个数。

#### 样例 #1 解释 此为题目描述中的示例。 翻译由 DeepSeek 完成