## 题目描述 ## 说明 小美参加的编程夏令营引入了新的导师分配系统： 系统配置： 有 $m$ 位导师（编号 $1 ~ m$）和 $n$ 位学生（编号 $1 ~ n$） 每位学生提交两个不同的导师志愿（$a_i$ 和 $b_i$） 分配规则（按学生编号顺序处理）： 首先尝试分配第一志愿导师 $a_i$。如果该导师未被选中，则成功分配，否则尝试第二志愿 $b_i$ 如果第二志愿导师未被选中，则成功分配 如果两个志愿导师都已被选中，则该学生分配失败 一旦导师被分配给某个学生，就不能再分配给其他学生 ## 输入格式 输入第一行是两个整数nm分别表示同学数量和教练数量(教练编号为1～m)接下来n行，每行包含两个整数aibi含义如题 对于10%的数据，nm≤5; 对于30%的数据，nm≤1000; 对于100%的数据，1≤nm≤1000001≤a[i]b[i]≤Ma[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$。 ## 来源 递归 枚举