题目描述

新华书店新到了一批限量版图书，共 $M$ 种不同的书，每种书只有一本。书店决定按照会员排队的顺序进行限量发售。

书店一共有 $N$ 位会员提前预约，当图书发售时，所有会员会按顺序排队等候购买。每位会员都有自己最想买的第一目标图书和第二目标图书（两种图书编号不同）。

会员购买图书的规则如下：

1. 如果她第一目标的图书还有剩余，就购买该书并离开。
2. 否则，如果第二目标的图书还有剩余，就购买该书并离开。
3. 否则，她会放弃购买。

现在书店想提前模拟发售过程中的一种特殊情况：如果前 $i$ 位会员取消预约的情况下（即：只剩下后 $N-i$ 位会员，相对排队顺序保持不变，仍按原顺序依次排队购书），统计最终会有多少位会员成功购买到一本图书。

请你编写程序，计算对于每种可能的 $i$（$0 ≤ i ≤ N-1$），当只让后 $N-i$ 位会员依次排队购买时，成功购到书的会员数量是多少。

输入格式

第一行包含两个正整数 $N$ 和 $M$，分别表示预约购书的会员总数和图书种类数。 接下来 $N$ 行，每行两个正整数 $A_i$ 和 $B_i$（$1 ≤ A_i, B_i ≤ M$ 且 $A_i ≠ B_i$），表示第 $i$ 位排队的会员的第一目标和第二目标图书编号。

输出格式

输出 $N$ 行，每行一个整数。第 $i+1$ 行表示当取消前 $i$ 位会员预约（即只让第 $i+1$ 到第 $N$ 位会员排队购买）时，成功购到图书的会员数量。

输入输出样例

输入 #1

4 2
1 2
1 2
1 2
1 2

输出 #1

2
2
2
1

输入 #2

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

输出 #2

5
5
4
3
2
1

输入 #3

10 9
1 2
2 3
3 4
4 5
5 6
1 3
2 4
3 5
6 7
8 9

输出 #3

7
7
7
7
6
5
4
3
2
1

说明/提示

样例1说明

共有 $4$ 位会员，$2$ 种图书，每位会员都最喜欢 $1$ 号书，其次喜欢 $2$ 号书。

• 取消前 $0$ 位（全部 $4$ 人排队）：只有 $2$ 本书，最多 $2$ 人能购到 → 输出 $2$。
• 取消前 $1$ 位（后 $3$ 人排队）：仍只有 $2$ 本书 → 输出 $2$。
• 取消前 $2$ 位（后 $2$ 人排队）：$2$ 人正好购买走 $2$ 本书 → 输出 $2$。
• 取消前 $3$ 位（只剩最后 $1$ 人）：$1$ 人购买走 $1$ 本书 → 输出 $1$。

数据范围

对于 $30\%$ 的数据，$1 ≤ N, M ≤ 10^3$。

对于 $100\%$ 的数据，$1 ≤ N, M ≤ 10^5$，$1 ≤ A_i, B_i ≤ M$，$A_i ≠ B_i$。