C. 地球上最后的夜晚

给定一张由 $n$ 个节点和 $m$ 条边构成的无向图。节点的编号是 $1,2,\cdots,n$，边的编号是 $1,2,\cdots,m$。

你需要选取若干条边。

用 01 序列 $\{a_i\}_{i=1}^m$ 来表示边的选取情况。若编号为 $i$ 的边被选，则 $a_i=1$；否则，$a_i=0$。

你的选边方案必须满足：

• 保留被选的边而删除不选的边后，所有节点的度数都是奇数。这有可能无法被满足，此时无解。
• 在满足上条要求的前提下，使序列 $a$ 的字典序最大。

第一行两个整数 $n,m$（$2\le n\le10^6$，$1\le m\le10^6$）。

接下来 $m$ 行中的第 $i$ 行，有两个整数 $u_i,v_i$（$1\le u_i,v_i\le n$），表示编号为 $i$ 的边连接节点 $u_i$ 和 $v_i$。

保证图中无自环，即 $u_i\ne v_i$。

若无解，输出 -1。

否则，输出一个长度为 $m$ 的 01 序列（一行 $m$ 个整数，相邻的数之间用一个空格隔开），表示你的选边方案。

样例 1

输入

4 4
1 2
2 3
3 4
4 1

输出

1 0 1 0

解释

若不要求使 $a$ 的字典序最大，方案还可以是选取编号为 $2$ 和 $4$ 的边。

样例 2

输入

3 2
1 2
2 3

输出

-1