提供一种顺着推的思路。

首先考虑求每头奶牛在哪个时间点可以拿到麦片，然后用差分处理，做个前缀和就能得到答案了。

那么先需要维护一个 $p$ 数组，$p(i,x)$ 表示在前 $i$ 头牛中，第 $x$ 种麦片最后被拿是在哪头牛上（也可以理解为：对于前 $i$ 头牛而言，在第 $p_x$ 头牛之后第 $x$ 种麦片就没有牛会拿了 ）。

注意这个 $p$ 数组是用来辅助后面求答案的。

而且一开始，在第一头牛之前，$p$ 数组全是 0 ，肯定是对的，那么只需要确保此后每次能更新对 $p$ 数组就行。

假设现在考虑到第 $i$ 头奶牛，显然，这头奶牛能拿到麦片的时间点就是 $\min(p(i - 1,f_i), p(i - 1, s_i)) + 1$ 。(就是看这两种麦片哪种最先能拿)

那么再考虑更新 $p$ 数组，首先肯定的是 $p$ 数组只可能在两个位置改变，并且实现的时候也不需要开两维，直接覆盖就行。

1. $p(i,f_i) = i$ 。

   因为第 $i$ 头首要就是拿麦片 $f_i$ 。

   如果没轮到第 $i$ 头牛，那么前面一定有牛拿了；否则就是第 $i$ 头牛拿了。

   但不需要管是谁，总之不删除到第 $i$ 头，麦片 $f_i$ 就是会被拿，后面的牛就是不能要。

   因此， $p(i,f_i) = i$ 。（所以说 $p$ 数组是考虑对后面的牛的影响的）

2. $p(i,s_i) = max(p(i - 1, s_i),p(i - 1,f_i))$ 。

   可能会有点难理解，但是可以仿照上面的思路。

   首先第 $i$ 头牛选择第二重要的麦片的前提是，麦片 $f_i$ 被拿了。

   那么就是在 $p(i-1,f_i)$ 之前，奶牛 $i$ 只会选择麦片 $s_i$ 。

   同上，如果没轮到第 $i$ 头牛，那么麦片 $s_i$ 在前面一定有牛拿了；否则就是第 $i$ 头牛拿了。

   但不需要管是谁，总之至少， 不删除到第 $p(i-1,f_i)$ 头牛，麦片 $s_i$ 就是会被拿，后面的牛就是不能要。

   但是这里的值与上面不同，不是 $i$ ，即不是最大的，它不一定能更新 $p$ 数组，所以跟原先取个 $\max$ 就好。

那么这个题就做完了，代码实现起来也很简单。

#include <cstdio>
#include <algorithm>
using namespace std;
const int maxn = 1000005;
int n, m;
int p[maxn], s[maxn];
int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        ++s[min(p[a], p[b]) + 1];
        --s[i + 1];
        p[b] = max(p[b], p[a]);
        p[a] = i;
    }
    for (int i = 1; i <= n; i++) printf("%d\n", s[i] += s[i - 1]);
    return 0;
}