题目描述

小美参加的编程夏令营引入了新的导师分配系统：

系统配置： 有 $m$ 位导师（编号 $1 \sim m$）和 $n$ 位学生（编号 $1 \sim n$） 每位学生提交两个不同的导师志愿（$a_i$ 和 $b_i$）

分配规则（按学生编号顺序处理）： 首先尝试分配第一志愿导师 $a_i$。如果该导师未被选中，则成功分配，否则尝试第二志愿 $b_i$； 如果第二志愿导师未被选中，则成功分配； 如果两个志愿导师都已被选中，则该学生分配失败； 一旦导师被分配给某个学生，就不能再分配给其他学生。

输入格式

输入第一行是两个整数 $n, m$，分别表示同学数量和教练数量（教练编号为 $1 \sim m$）。 接下来 $n$ 行，每行包含两个整数 $a_i, b_i$，含义如题。

输出格式

输出 $n$ 行，每行包含一个整数表示第 $i$ 个同学应该给出的答案。

样例输入

4 2
1 2
1 2
1 2
1 2

样例输出

2
2
2
1

提示

样例解释

对1号学生的查询： 1选1号导师(成功) 2选2号导师(成功) 3、4号无法选择 →答案2

对2号学生的查询： 2选1号导师(成功) 3选2号导师(成功) 4号无法选择 →答案2

对3号学生的查询： 3选1号导师(成功) 4选2号导师(成功) →答案2

对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$。