Problem: Dima came to the horse land. There are n horses living in the land. Each horse in the horse land has several enemies (enmity is a symmetric relationship). The horse land isn't very hostile, so the number of enemies of each horse is at most 3.

Right now the horse land is going through an election campaign. So the horses trusted Dima to split them into two parts. At that the horses want the following condition to hold: a horse shouldn't have more than one enemy in its party.

Help Dima split the horses into parties. Note that one of the parties can turn out to be empty.

Input

The first line contains two integers n, m <image> — the number of horses in the horse land and the number of enemy pairs.

Next m lines define the enemy pairs. The i-th line contains integers ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi), which mean that horse ai is the enemy of horse bi.

Consider the horses indexed in some way from 1 to n. It is guaranteed that each horse has at most three enemies. No pair of enemies occurs more than once in the input.

Output

Print a line, consisting of n characters: the i-th character of the line must equal "0", if the horse number i needs to go to the first party, otherwise this character should equal "1".

If there isn't a way to divide the horses as required, print -1.

Examples

Input

3 3
1 2
3 2
3 1


Output

100


Input

2 1
2 1


Output

00


Input

10 6
1 2
1 3
1 4
2 3
2 4
3 4


Output

0110000000

Solution (in JAVA):

Solution:

import java.io.*;
import java.lang.reflect.*;
import java.util.*;

public class C {

	final int MOD = (int)1e9 + 7;
	final double eps = 1e-12;
	final int INF = (int)1e9;
	
	public C () {
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		Integer [][] E = new Integer [N][3]; int [] NE = new int[N];
		for (int i = 0; i < M; ++i) {
			int x = sc.nextInt() - 1, y = sc.nextInt() - 1;
			E[x][NE[x]++] = y;
			E[y][NE[y]++] = x;			
		}

		BitSet R = new BitSet();
		Queue<Integer> Q = new LinkedList<Integer>();
		BitSet V = new BitSet();
		
		for (int i = 0; i < N; ++i) {
			Q.add(i);
			V.set(i);
		}
		
		while(!Q.isEmpty()) {
			int U = Q.poll(); V.clear(U);
			int Z = 0, W = -1;
			for (int j = 0; j < NE[U]; ++j)
				if (R.get(U) == R.get(E[U][j]))
					++Z;
				else
					W = E[U][j];
			
			if (Z > 1) {
				R.flip(U);
				if (W >= 0 && !V.get(W)) {
					Z = 0;
					for (int k = 0; k < NE[W]; ++k)
						if (R.get(E[W][k]) == R.get(W))
							++Z;
					if (Z > 1) {
						Q.add(W);
						V.set(W);
					}
				}
			}
		}
		
		char [] res = new char [N];
		for (int i = 0; i < N; ++i)
			res[i] = R.get(i) ? '1' : '0';
		
		//cprint(res);
		pw.println(new String(res));
	}		

	////////////////////////////////////////////////////////////////////////////////////
	
	static MyScanner sc;
	
	static class MyScanner {
		public String next() {
			readToken();
			return new String(b, T[0], T[1] - T[0]);
		}
		
		public char nextChar() {
			readToken();
			return (char)b[T[0]];
		}
				
		public int nextInt() {
			return (int)nextLong();
		}
		
		public long nextLong() {
			readToken();
			return calc(T[0], T[1]);
		}
		
		public double nextDouble() {
			return Double.parseDouble(next());
		}
		
		public String nextLine() {
			readLine();
			return new String(b, T[0], T[1] - T[0]);
		}
		
		public String [] next(int N) {
			String [] res = new String [N];
			for (int i = 0; i < N; ++i)
				res[i] = next();
			return res;
		}
		
		public Integer [] nextInt(int N) {
			Integer [] res = new Integer [N];
			for (int i = 0; i < N; ++i)
				res[i] = nextInt();
			return res;
		}
		
		public Long [] nextLong(int N) {
			Long [] res = new Long [N];
			for (int i = 0; i < N; ++i)
				res[i] = nextLong();
			return res;
		}
		
		public Double [] nextDouble(int N) {
			Double [] res = new Double [N];
			for (int i = 0; i < N; ++i)
				res[i] = nextDouble();
			return res;
		}
		
		public String [] nextLine(int N) {
			String [] res = new String [N];
			for (int i = 0; i < N; ++i)
				res[i] = nextLine();
			return res;
		}
		
		public String [] nextStrings() {
			readLine();
			int s = T[0], c = 0;
			String [] res = new String[count(T[0], T[1])];
			for (int i = T[0]; i < T[1]; ++i)
				if (b[i] == SPACE) {
					res[c++] = new String(b, s, i - s);
					s = i+1;
				}
			res[c] = new String (b, s, T[1] - s);
			return res;
		}
		
		public char [] nextChars() {
			readToken();
			int c = 0;
			char [] res = new char[T[1] - T[0]];
			for (int i = T[0]; i < T[1]; ++i)
				res[c++] = (char)b[i];
			return res;
		}

		public Integer [] nextInts() {
			readLine();
			int s = T[0], c = 0;
			Integer [] res = new Integer[count(T[0], T[1])];
			for (int i = T[0]; i < T[1]; ++i)
				if (b[i] == SPACE) {
					res[c++] = (int)calc(s, i);
					s = i+1;
				}
			res[c] = (int)calc(s, T[1]);
			return res;
		}	
		
		public Long [] nextLongs() {
			readLine();
			int s = T[0], c = 0;
			Long [] res = new Long[count(T[0], T[1])];
			for (int i = T[0]; i < T[1]; ++i)
				if (b[i] == SPACE) {
					res[c++] = calc(s, i);
					s = i+1;
				}
			res[c] = calc(s, T[1]);
			return res;
		}

		public Double [] nextDoubles() {
			readLine();
			int s = T[0], c = 0;
			Double [] res = new Double[count(T[0], T[1])];
			for (int i = T[0]; i < T[1]; ++i)
				if (b[i] == SPACE) {
					res[c++] = Double.parseDouble(new String(b, s, i - s));
					s = i+1;
				}
			res[c] = Double.parseDouble(new String(b, s, T[1] - s));
			return res;
		}

		String [][] nextStrings(int N) {
			String [][] res = new String [N][];
			for (int i = 0; i < N; ++i)
				res[i] = nextStrings();
			return res;
		}
		
		char [][] nextChars(int N) { 
			char [][] res = new char [N][];
			for (int i = 0; i < N; ++i)
				res[i] = nextChars();
			return res;
		}
		
		Integer [][] nextInts(int N) {
			Integer [][] res = new Integer [N][];
			for (int i = 0; i < N; ++i)
				res[i] = nextInts();
			return res;
		}
		
		Long [][] nextLongs(int N) { 
			Long [][] res = new Long [N][];
			for (int i = 0; i < N; ++i)
				res[i] = nextLongs();
			return res;
		}
		
		Double [][] nextDoubles(int N) {
			Double [][] res = new Double [N][];
			for (int i = 0; i < N; ++i)
				res[i] = nextDoubles();
			return res;
		}
		
		//////////////////////////////////////////////
		
		private final static int MAX_SZ = 12000000;
		private final byte [] b = new byte[MAX_SZ];
		private final int [] T = new int [2];
		private int cur = 0; 

		MyScanner () {
			try {
				InputStream is = new BufferedInputStream(System.in);
				while (is.available() == 0)
					Thread.sleep(1);
				start();
				int off = 0, c;
				while ((c = is.read(b, off, MAX_SZ - off)) != -1)
					off += c;
			} catch (Exception e) {
				throw new Error(e);
			}
		}
		
		private void readLine() {
			int c;
			for (c = cur; b[c] != LF && b[c] != CR && b[c] != 0; ++c);
			T[0] = cur; T[1] = c;
			for (cur = c; b[cur] == LF || b[cur] == CR; ++cur);
		}
		
		private void readToken() {
			int c;
			for (c = cur; b[c] != SPACE && b[c] != LF && b[c] != CR && b[c] != 0; ++c);
			T[0] = cur; T[1] = c;
			for (cur = c; b[cur] == SPACE || b[cur] == LF || b[cur] == CR; ++cur);
		}

		private int count(int s, int e) {
			int cnt = 1;
			for (int i = s; i < e; ++i)
				if (b[i] == SPACE)
					++cnt;		
			return cnt;
		}
		
		private long calc(int s, int e) {
			long res = 0, f = 1;
			for (int i = s; i < e; ++i)
				if (b[i] == '-')
					f = -1;
				else
					res = 10 * res + b[i] - '0';
			return res * f;			
		}
		
		private static final char LF = '\n';
		private static final char CR = '\r';
		private static final char SPACE = ' ';
	}
	
	static void print(Object o, Object... a) {
		printDelim(" ", o, a);
	}
	
	static void cprint(Object o, Object... a) {
		printDelim("", o, a);
	}
	static void printDelim (String delim, Object o, Object... a) {
		pw.println(build(delim, o, a));
	}

	static void exit (Object o, Object... a) {
		print(o, a);
		exit();
	}

	static void exit () {
		pw.close();
		System.out.flush();
		System.err.println("------------------");
		System.err.println("Time: " + ((millis() - t) / 1000.0));
		System.exit(0);
	}
	
	void NO() {
		throw new Error("NO!");
	}
	
	////////////////////////////////////////////////////////////////////////////////////
	
	static String build(String delim, Object o, Object... a) {
		StringBuilder b = new StringBuilder();
		append(b, o, delim);
		for (Object p : a)
			append(b, p, delim);
		return b.toString().trim();		
	}
	
	static void append(StringBuilder b, Object o, String delim) {
		if (o.getClass().isArray()) {
			int L = Array.getLength(o);
			for (int i = 0; i < L; ++i)
				append(b, Array.get(o, i), delim);
		} else if (o instanceof Iterable<?>) {
			for (Object p : (Iterable<?>)o)
				append(b, p, delim);
		} else
			b.append(delim).append(o);		
	}
	
	////////////////////////////////////////////////////////////////////////////////////
	
	public static void main(String[] args) {
		sc = new MyScanner ();
		new C();
		exit();
	}

	static void start() {
		t = millis();
	}

	static PrintWriter pw = new PrintWriter(System.out);
	
	static long t;
	
	static long millis() {
		return System.currentTimeMillis();
	}	
}