新华书店新到了一批限量版图书，共 M 种不同的书，每种书只有一本。书店决定按照会员排队的顺序进行限量发售。

书店一共有 N 位会员提前预约，当图书发售时，所有会员会按顺序排队等候购买。每位会员都有自己最想买的第一目标图书和第二目标图书（两种图书编号不同）。

会员购买图书的规则如下：

• 如果她第一目标的图书还有剩余，就购买该书并离开。
• 否则，如果第二目标的图书还有剩余，就购买该书并离开。
• 否则，她会放弃购买。

现在书店想提前模拟发售过程中的一种特殊情况：如果前 i 位会员取消预约的情况下（即：只剩下后 N-i 位会员，相对排队顺序保持不变，仍按原顺序依次排队购书），统计最终会有多少位会员成功购买到一本图书。

请你编写程序，计算对于每种可能的 i（0 ≤ i ≤ N-1），当只让后 N-i 位会员依次排队购买时，成功购到书的会员数量是多少。

第一行包含两个正整数 N 和 M，分别表示预约购书的会员总数和图书种类数。

接下来 N 行，每行两个正整数 A_i 和 B_i（1 ≤ A_i, B_i ≤ M 且 A_i ≠ B_i），表示第 i 位排队的会员的第一目标和第二目标图书编号。

输出 N 行，每行一个整数。第 i+1 行表示当取消前 i 位会员预约（即只让第 i+1 到第 N 位会员排队购买）时，成功购到图书的会员数量。

样例 1 说明

共有 4 位会员，2 种图书，每位会员都最喜欢 1 号书，其次喜欢 2 号书。

• 取消前 0 位（全部 4 人排队）：只有 2 本书，最多 2 人能购到 → 输出 2 。
• 取消前 1 位（后 3 人排队）：仍只有 2 本书 → 输出 2。
• 取消前 2 位（后 2 人排队）：2 人正好购买走 2 本书 → 输出 2 。
• 取消前 3 位（只剩最后 1 人）：1 人购买走 1 本书 → 输出 1 。

数据范围

对于 30\% 的数据，保证 1 ≤ N, M ≤ 10^3。

对于全部测试数据，保证 1 ≤ N, M ≤ 10^5，1 ≤ A_i, B_i ≤ M，A_i ≠ B_i。

月赛26年2月模拟O2优化