P6908: 谷类食品
传统题
1.000s
时间限制
256MB
内存限制
1 提交
1 解决
【题目描述】
【题目描述】
Farmer John
的奶牛们的早餐最爱当然是麦片了！事实上，奶牛们的胃口是如此之大，每头奶牛一顿饭可以吃掉整整一箱麦片。
最近农场收到了一份快递，内有 M
种不同种类的麦片（1≤M≤10^5
）。不幸的是，每种麦片只有一箱！N
头奶牛（1≤N≤10^5
）中的每头都有她最爱的麦片和第二喜爱的麦片。给定一些可选的麦片，奶牛会执行如下的过程：
1.如果她最爱的麦片还在，取走并离开。
2.否则，如果她第二喜爱的麦片还在，取走并离开。
3.否则，她会失望地哞叫一声然后不带走一片麦片地离开。
奶牛们排队领取麦片。对于每一个0≤i≤N−1
，求如果 Farmer John
从队伍中移除前 i
头奶牛，有多少奶牛会取走一箱麦片。
【
输入格式】
（文件名：cereal.in
）：
输入的第一行包含两个空格分隔的整数 N
和 M。
对于每一个 1≤i≤N
，第 i
行包含两个空格分隔的整数 fi 和 si（1≤fi,si≤M
，且 fi≠si
），为队伍中第 i
头奶牛最喜爱和第二喜爱的麦片。
【
输出格式】
（文件名：cereal.out
）：
对于每一个 0≤i≤N−1
，输出一行，包含对于 i
的答案。
【
输入样例】
：
4 2
1 2
1 2
1 2
1 2
【
输出样例】
：
2
2
2
1
【样例说明】
如果至少两头奶牛留下，那么恰有两头奶牛取走了一箱麦片。
【
测试点性质】
：
测试点 2-3
满足 N,M≤1000。
测试点 4-10
没有额外限制。