暂无测试数据。

小 C 是 $n$ 个学生的老师，他现在要把所有学生分成两组，他会按照以下这些要求：

1、如果两个同学是好朋友那么他们就不会被分到同一组

2、小 C 想最小化两组人数差值

现在请你写一个程序来帮助小 C 分组，数据保证有合法的方案，如果有多种合法方案则输出字典序最小的

输入格式

第一行两个整数分别表示 $n,m$

接下来 $m$ 行，每行两个整数表示 $x_i,y_i$ 是好朋友

输出格式

如果第 $i$ 位学生被分到第 1 组则第 $i$ 位为 1，反之为 2

如果有多种合法方案则输出字典序最小的方案

数据范围

对于 $30\%$ 的数据,$2 \leq n \leq 16$

对于 $50\%$ 的数据,$2 \leq n \leq 100$

对于 $100\%$ 的数据,$2 \leq n \leq 1000,1 \leq m \leq 100000$

6 4
1 2
1 3
4 6
4 5

122211