时间限制：1秒　　内存限制：256M

---

【题目描述】

　　小H上初中了，第一课就是残酷的军训。其中用餐也是特定的训练项目。

　　食堂每餐提供 \(m\) 份不同的食物，每个学员最多选择一份食物。\(n\) 名学员中的每人都有自己最喜欢的食物和第二喜爱的食物。每个学员选择食物的规则是：

　　◆ 如果他最爱的食物还在，取走并离开；
　　◆ 如果最喜欢的食物被其他人取走，但他第二喜爱的食物还在，则取走并离开；
　　◆ 若喜欢的两份食物都被取走，则他会失望地离开。

　　学员们按 \(1..n\) 的顺序排队领取食物。对于每一个 \(i\)，求如果教官从队伍中移除前 \(i\) 名学员，则此时有多少学员会取走食物？请你计算！

【输入格式】

　　输入的第一行包含两个空格分隔的整数 \(n\) 和 \(m\)。
　　接下来的 \(n\) 行，每行包含两个整数，其中的第 \(i+1\) 行的两个整数是两个空格分隔的整数 \(f_i\) 和 \(s_i\)（\(1≤f_i,s_i≤m\) 且 \(f_i≠s_i\)），为队伍中第 \(i\) 名学员最喜爱和第二喜爱的食物。

【输出格式】

　　 输出 \(n\) 行，第 \(i\) 行的整数表示移除前 \(i-1\) 个人后，最多有多少学员能吃到食物。

【输入输出样例】

　Input

6 3
1 3
2 3
1 2
3 2
2 1
3 2

　Output

3
3
3
2
2
1

【输出样例解释】

　　对于 6 名学员，第 1 个学员吃食物1，第2个学员吃食物2，第 3 个学员最喜欢食物和第二喜欢的食物都被吃掉了，所以他吃不到食物，第 4 个吃食物3，所以 3 人能吃到食物；
　　移走学员1，剩下的 5 名学员中，第 1 个学员吃食物2，第 2 个学员吃食物1，第 3 个学员吃食物3，所以 3 人能吃到食物；
　　当移走学员 1，2，3，剩下的 3 名学员中，第 1 个学员吃食物3，第 2 个学员吃食物2，第 3 个学员最喜欢的和第二喜欢都被吃掉了，所以 2 人能吃到食物；

【数据限制】

　　对于 \(30\%\) 的数据，\(1≤n,m≤1000\)。
　　对于 \(100\%\) 的数据，\(1≤n,m≤100000\)。

【来源】

　　Mr.he