Description

小美参加的编程夏令营引入了新的导师分配系统： 系统配置： 有 $m$ 位导师（编号 $1 ~ m$）和 $n$ 位学生（编号 $1 ~ n$） 每位学生提交两个不同的导师志愿（$a_i$ 和 $b_i$） 分配规则（按学生编号顺序处理）： 首先尝试分配第一志愿导师 $a_i$。如果该导师未被选中，则成功分配，否则尝试第二志愿 $b_i$ 如果第二志愿导师未被选中，则成功分配 如果两个志愿导师都已被选中，则该学生分配失败 一旦导师被分配给某个学生，就不能再分配给其他学生

Input Format

输入第一行是两个整数n,m,分别表示同学数量和教练数量(教练编号为1～m)接下来n行，每行包含两个整数ai,bi,含义如题

对于10%的数据，n,m≤5;
对于30%的数据，n,m≤1000;
对于100%的数据，1≤n,m≤100000,1≤a[i],b[i]≤M,a[i]≠b[i]。

Output Format

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

4 2
1 2
1 2
1 2
1 2

2
2
2
1

Hint

样例解释 

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

Source

递归 枚举