题目描述

在魔法学院的期末考试中，有一个导师分配系统。系统中有 $m$ 位导师（编号 $1 \sim m$）和 $n$ 位学生（编号 $1 \sim n$）。每位学生提交两个不同的导师志愿 $a_i$ 和 $b_i$（$a_i \neq b_i$）。分配按学生编号从小到大的顺序进行，对于每位学生：

1. 首先尝试将其分配至第一志愿导师 $a_i$。如果该导师尚未被任何学生选择，则分配成功；
2. 否则尝试将其分配至第二志愿导师 $b_i$。如果该导师尚未被任何学生选择，则分配成功；
3. 如果两个志愿导师都已被之前的学生选择，则该学生分配失败。

一旦导师被分配给某个学生，就不能再分配给其他学生。

现在，对于每一个 $i$（$1 \le i \le n$），你需要回答：如果仅考虑从第 $i$ 位学生开始到第 $n$ 位学生进行分配，最多能让多少位学生成功分配到导师？

输入格式

第一行包含两个整数 $n, m$，分别表示学生数量和导师数量。

接下来 $n$ 行，每行两个整数 $a_i, b_i$，表示第 $i$ 位学生的两个志愿导师编号。

输出格式

输出 $n$ 行，第 $i$ 行一个整数，表示仅考虑第 $i$ 到第 $n$ 位学生时，能够成功分配的学生数量的最大值。

样例

4 2
1 2
1 2
1 2
1 2

2
2
2
1

样例解释

• $i=1$：从第 $1$ 位学生开始分配。学生 $1$ 选导师 $1$（成功），学生 $2$ 选导师 $2$（成功），学生 $3$ 和 $4$ 的两个志愿都已被选，无法分配。成功 $2$ 人。
• $i=2$：从第 $2$ 位学生开始分配。学生 $2$ 选导师 $1$（成功），学生 $3$ 选导师 $2$（成功），学生 $4$ 无法分配。成功 $2$ 人。
• $i=3$：从第 $3$ 位学生开始分配。学生 $3$ 选导师 $1$（成功），学生 $4$ 选导师 $2$（成功）。成功 $2$ 人。
• $i=4$：从第 $4$ 位学生开始分配。学生 $4$ 选导师 $1$（成功）。成功 $1$ 人。

数据范围与提示

• 对于 $10\%$ 的数据，$n, m \le 5$；
• 对于 $30\%$ 的数据，$n, m \le 1000$；
• 对于 $100\%$ 的数据，$1 \le n, m \le 100000$，$1 \le a_i, b_i \le m$，$a_i \neq b_i$。