C. The Last Night on Earth
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given an undirected graph with $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered $$$1,2,\cdots,n$$$, and the edges are numbered $$$1,2,\cdots,m$$$.

You need to choose some of these edges.

We use a 01 sequence $$$\{a_i\}_{i=1}^m$$$ to represent which edges are chosen. If the edge with index $$$i$$$ is chosen, then $$$a_i=1$$$; otherwise, $$$a_i=0$$$.

The chosen edges must satisfy the following conditions:

  • After keeping the chosen edges and removing all unchosen edges, the degree of every vertex is odd. This requirement may be impossible to satisfy; in that case, there is no solution.
  • Under the above constraint, sequence $$$a$$$ must be lexicographically greatest.
Formally, for any two 01 sequences $$$\{b_{1,i}\}_{i=1}^m$$$ and $$$\{b_{2,i}\}_{i=1}^m$$$, we say that $$$b_1$$$ is lexicographically greater than $$$b_2$$$ if and only if there exists an integer $$$i\in[1,m]$$$ satisfying the following two conditions: for every integer $$$j\in[1,i)$$$, it holds that $$$b_{1,j}=b_{2,j}$$$; $$$b_{1,i}=1$$$ and $$$b_{2,i}=0$$$. It is easy to prove that all 01 sequences of length $$$m$$$ form a strict total order under lexicographical comparison.
Input

The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2\le n\le10^6$$$, $$$1\le m\le10^6$$$).

Each of the next $$$m$$$ lines contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1\le u_i,v_i\le n$$$), representing the edge with index $$$i$$$ that connects vertices $$$u_i$$$ and $$$v_i$$$.

It is guaranteed that there is no self-loop in the graph, i.e., $$$u_i\ne v_i$$$.

Output

If there is no solution, output -1.

Otherwise, output a 01 sequence of length $$$m$$$ (one line with $$$m$$$ integers, separated by single spaces) representing your choice of edges.

Examples
Input
4 4
1 2
2 3
3 4
4 1
Output
1 0 1 0
Input
3 2
1 2
2 3
Output
-1
Note

In the first example, if we do not require sequence $$$a$$$ to be lexicographically greatest, another valid solution is to choose edges numbered $$$2$$$ and $$$4$$$.