Cereal

题目描述

Farmer John 的奶牛们早餐最喜欢的就是麦片！事实上，奶牛们胃口很大，每顿饭每头牛都会吃掉一整盒麦片。 农场最近收到了一批包含 $M$ 种不同类型麦片的货物 $(1\le M\le 10^5)$。不幸的是，每种麦片只有一盒！$N$ 头奶牛 $(1\le N\le 10^5)$ 中，每头牛都有一种最喜欢的麦片和一种次喜欢的麦片。当给奶牛一组可选择的麦片时，一头奶牛会进行如下过程： 如果她最喜欢的麦片盒还可用，就拿走并离开。 否则，如果她次喜欢的麦片盒还可用，就拿走并离开。 否则，她会失望地哞叫一声，不拿任何麦片就离开。 奶牛们排成一列来领取麦片。对于每个 $0 \leq i \leq N-1$，请确定如果 Farmer John 从队伍中移除最前面的 $i$ 头奶牛，会有多少头奶牛能拿到一盒麦片。

输入格式

输入格式（文件 cereal.in）： 第一行包含两个用空格分隔的整数 $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$ 头奶牛最喜欢和次喜欢的麦片编号。

输出格式

输出格式（文件 cereal.out）： 对于每个 $0\le i\le N-1$，输出一行，包含对应 $i$ 的答案。

4 2
1 2
1 2
1 2
1 2

2
2
2
1

提示

如果至少还剩两头奶牛，那么恰好有两头奶牛能得到一盒麦片。 SCORING: 测试点 2-3 满足 $N,M\le 1000.$ 测试点 4-10 没有额外限制。 题目来源：Dhruv Rohatgi

标签: USACO|2020|Silver

来源

USACO|2020|Silver