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 n,mn,mn,m (1≤n≤100,0≤m≤100001 \leq n \leq 100, 0 \leq m \leq 100001≤n≤100,0≤m≤10000) , representing the number of nodes and edges in the graph, respectively.
For the next mmm lines, each contains two integers ui,viu_i,v_iui,vi (1≤ui,vi≤n,ui≠vi)1\leq u_i,v_i \leq n, u_i \neq v_i)1≤ui,vi≤n,ui=vi), which means there is an edge connecting node uiu_iui and viv_ivi. It is possible to have multiple edges between the same pair of nodes.
输出格式
If it is possible to assign the values, print nnn values of 000 or 111 in a single line. The iii-th of them represents the value assigned to the iii-th node. Otherwise, print −1-1−1.
If there are multiple solutions, you can print any of them.