题目描述

The forbidden card game is played by $N$ players numbered from $1$ to $N$ and a set of cards. Each card has a number written on it between $1$ and $M$, inclusive, and there might be more than one card with the same number written on it.

Initially, each player draws two cards one by one. The numbers written on the first card and the second card drawn by the $i^\text{th}$ player are $A_i$ and $B_i$, respectively. It is guaranteed that $A_i \neq B_i$. After all the players have drawn their cards, the game master (who is not among the players) will decide and designate a number $X$ between $1$ and $M$, inclusive, to be a forbidden number.

In one turn, a player should play and discard one card from their hand. The card being played should have a number that has not been played before and this number should not be the same as $X$. If a player cannot discard any card on their move, i.e. when they have no card in hand or all the numbers on their cards have already been played or equal to $X$, then they lose the game.

The game is played alternately in a circular manner from player $1, 2, \dots, N-1, N, 1, 2, \dots$ until a player loses the game.

There is a naive deterministic strategy to play this game called first card first where each player prioritizes to play the first card they have (i.e. card numbered $A_i$) and play the second card (numbered $B_i$) only when they cannot play their first card.

Your task in this problem is to determine for each player the number of different possible forbidden numbers $X$ that will cause the player to lose the game assuming all players adopt the first card first strategy.

For example, let there be $N = 3$ players and the cards are numbered between $1$ and $M = 6$, inclusive. Let $\langle A_i, B_i \rangle$ represents the number written on the cards drawn by the $i^\text{th}$ player. Player 1 has $\langle 1, 2 \rangle$, player 2 has $\langle 2, 4 \rangle$, and player 3 has $\langle 4, 2 \rangle$.

All possible plays are as follows.

• $X = 1 \rightarrow$ player 3 loses; player 1 plays 2, player 2 plays 4, and finally, player 3 cannot make any move.
• $X = 2 \rightarrow$ player 3 loses; player 1 plays 1, player 2 plays 4, and finally, player 3 cannot make any move.
• $X = 3 \rightarrow$ player 1 loses; player 1 plays 1, player 2 plays 2, player 3 plays 4, and finally, player 1 cannot make any move.
• $X = 4 \rightarrow$ player 3 loses; player 1 plays 1, player 2 plays 2, and finally, player 3 cannot make any move.
• $X = 5 \rightarrow$ player 1 loses; player 1 plays 1, player 2 plays 2, player 3 plays 4, and finally, player 1 cannot make any move.
• $X = 6 \rightarrow$ player 1 loses; player 1 plays 1, player 2 plays 2, player 3 plays 4, and finally, player 1 cannot make any move.

In summary, $X = 3, 5, 6$ will cause player 1 to lose the game, and $X = 1, 2, 4$ will cause player 3 to lose the game. On the other hand, there is no forbidden number $X$ that will cause player 2 to lose the game in this example.

输入格式

Input begins with a line containing two integers: $N\ M$ ($1 \leq N \leq 100\,000$; $2 \leq M \leq 10^6$) representing the number of players and the maximum possible numbers on the cards, respectively. The next $N$ lines each contains two integers: $A_i\ B_i$ ($1 \leq A_i, B_i \leq M$; $A_i \neq B_i$) representing the number on the first and second cards of the $i^\text{th}$ player, respectively.

输出格式

Output contains $N$ lines. The $i^\text{th}$ line contains an integer representing the number of different possible forbidden numbers that will cause the $i^\text{th}$ player to lose the game.

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

提示

Explanation for the sample input/output #1

This is the example from the problem description.