3390. [USACO20 Open Silver]Cereal

【题目描述】

Farmer John 的奶牛们的早餐最爱当然是麦片了！事实上，奶牛们的胃口是如此之大，每头奶牛一顿饭可以吃掉整整一箱麦片。

最近农场收到了一份快递，内有 $M$ 种不同种类的麦片（$1\le M\le 10^5$）。不幸的是，每种麦片只有一箱！$N$ 头奶牛（$1\le N\le 10^5$）中的每头都有她最爱的麦片和第二喜爱的麦片。给定一些可选的麦片，奶牛会执行如下的过程：

 • 1. 如果她最爱的麦片还在，取走并离开。

 • 2. 否则，如果她第二喜爱的麦片还在，取走并离开。

 • 3. 否则，她会失望地“哞”叫一声然后不带走一片麦片地离开。

奶牛们排队领取麦片。对于每一个 $0 \leq i \leq N-1$，求如果 Farmer John 从队伍中移除前 $i$ 头奶牛，有多少奶牛会取走一箱麦片。

【输入格式】

输入的第一行包含两个空格分隔的整数 $N$ 和 $M$。

对于每一个 $1\le i\le N$，第 $i$ 行包含两个空格分隔的整数 $f_i$ 和 $s_i$（$1\le f_i,s_i\le M$，且 $f_i\neq s_i$），为队伍中第 $i$ 头奶牛最喜爱和第二喜爱的麦片。

【输出格式】

对于每一个 $0\le i\le N-1$，输出一行，包含对于 $i$ 的答案。

【样例输入】

4 2
1 2
1 2
1 2
1 2

【样例输出】

2
2
2
1

【样例解释】

如果至少两头奶牛留下，那么恰有两头奶牛取走了一箱麦片。

【提示】

对于$ 30\% $的测试数据(测试点$ 1 \sim 3 $)，满足$ N,M \le 10^3 $。

对于$ 100\% $的测试数据，均满足上文所给出的数据规模。

【来源】

USACO 美国公开赛 Silver 组