### 问题描述 小齐的奶牛们非常喜欢吃麦片作为早餐！实际上，她的奶牛们有着如此之大的食欲，以至于它们每顿饭都能吃下一整盒麦片。 最近，农夫小齐的农场收到了一批不同种类的麦片（$1 \leq M \leq 10^5$）。不幸的是，每种麦片只有一盒！每头奶牛（$1 \leq N \leq 10^5$）都有一种最喜欢的麦片和一种次喜欢的麦片。当给定一些选择时，奶牛们会按照以下流程进行选择： 如果她最喜欢的麦片还有库存，就拿走它并离开。 否则，如果她次喜欢的麦片还有库存，就拿走它并离开。 否则，她会失望地哞一声，离开而没有拿走任何麦片。 奶牛们排队等着拿麦片。对于每个 $0 \leq i \leq N-1$，请确定如果小齐移除了队列中的前 $i$ 头奶牛，有多少头奶牛会拿到一盒麦片。 ### 输入格式 第一行包含两个以空格分隔的整数 $N$ 和 $M$。 对于每个 $1 \leq i \leq N$，第 $i$ 行包含两个以空格分隔的整数 $f_i$ 和 $s_i$，表示第 $i$ 头奶牛的最喜欢的和次喜欢的麦片编号（$1 \leq f_i, s_i \leq M$，且 $f_i \neq s_i$）。 ### 输出格式 对于每个 $0 \leq i \leq N-1$，输出一行，包含 $i$ 时有多少头奶牛拿到了麦片。 ### 样例输入 ``` 4 2 1 2 1 2 1 2 1 2 ``` ### 样例输出 ``` 2 2 2 1 ``` ### 评测数据规模 $1 \leq M \leq 10^5$，$1 \leq N \leq 10^5$。