该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

样例下载

题目描述

N 个人排队入场看电影。

有 M 个座位，编号为 1 ~ M。

排在第 i 个位置的人最想坐 Ai 号座位，次想坐 Bi 号座位。

现在，他们要按照排队的顺序依次就坐。当轮到排在第 i 个位置的人时，如果 Ai 号座位还空着，则他会坐在 Ai 号座位；如果 Ai 已经被别人坐了，但 Bi 号座位还空着，则他会坐在 Bi 号座位。如果 Ai 号和 Bi 号座位都被别人坐了，则他就会离开，不再看电影了。

现在问你这样的问题：如果队伍的前 K (0 ≤ K ＜ N) 个人全部离开不再入场，剩余的人仍按原顺序依次入场，会有多少人可以坐下看电影？

输入格式

第一行：两个整数 N, M；

接下来 N 行，每行两个整数 Ai, Bi。

输出格式

共 N 行，每行一个整数，依次表示当 K = 0, 1, ……, N-1 时的答案。

样例输入

3 2
1 2
2 1
1 2

样例输出

2
2
1

数据范围

30% 的数据：1 ≤ N, M ≤ $10^3$。

100% 的数据：1 ≤ N, M ≤ $10^5$, 1 ≤ Ai, Bi ≤ M 且 Ai ≠ Bi