Given an undirected graph without self-loops, your task is to assign either 0 or 1 to each node. Subsequently, any edge connecting two nodes with different values will be removed. Each connected component should then have at least one Eulerian path. If there are multiple ways to assign values to the nodes, you can choose any one of them.

Eulerian path: an Eulerian trail (or Eulerian path) is a trail in a finite graph that visits every edge exactly once (allowing for revisiting vertices).

Connected component: a component of an undirected graph is a connected subgraph that is not part of any larger connected subgraph.

The first line contains two integers  () , representing the number of nodes and edges in the graph, respectively.

For the next  lines, each contains two integers  (, which means there is an edge connecting node  and . It is possible to have multiple edges between the same pair of nodes.

If it is possible to assign the values, print  values of  or  in a single line. The -th of them represents the value assigned to the -th node. Otherwise, print .

If there are multiple solutions, you can print any of them.

3 6
2 3
1 3
2 1
2 1
1 2
1 3

0 1 0