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.util.*;

public class R167qC {
    
    static ArrayList<Integer> g[];
    static boolean vis[];
    static int ans[];
    
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        InputReader in = new InputReader(System.in);
        PrintWriter w = new PrintWriter(System.out);

        int n = in.nextInt();
        int m = in.nextInt();
        
        g = new ArrayList[n];
        for (int i = 0; i < n; i++)
            g[i] = new ArrayList<Integer>();
        
        for (int i = 0; i < m; i++) {
            int a = in.nextInt() - 1;
            int b = in.nextInt() - 1;
            g[a].add(b);
            g[b].add(a);
        }
        
        ans = new int[n];
        
        Queue<Integer> q = new LinkedList<Integer>();
        
        for (int i = 0; i < n; i++)
            if (g[i].size() > 1)
                q.add(i);
        
        while (!q.isEmpty()) {
            int c = q.remove();
            int bad = 0;
            for (int j = 0; j < g[c].size(); j++)
                if (ans[g[c].get(j)] == ans[c])
                    bad++;
            if (bad > 1) {
                ans[c] = 1 - ans[c]; 
                for (int j = 0; j < g[c].size(); j++)
                    q.add(g[c].get(j));
            }
        }
        
        for (int i = 0; i < n; i++)
            w.print(ans[i] == 0 ? '0' : '1');
        w.close();
    }
    
    static void dfs(int c) {
        int cnt[] = new int[3];
        int child[] = new int[4];
        int tot = 0;
        for (int next : g[c]) {
            if (!vis[next]) {
                vis[next] = true;
                dfs(next);
                cnt[ans[next]]++;
                child[tot++] = next;
            }
        }
        if (tot == 0)
            ans[c] = 2;
        else if (tot == 1) {
            if (ans[child[0]] <= 1)
                ans[c] = 1 - ans[child[0]];
            else {
                ans[c] = 0;
                ans[child[0]] = 1;
            }
        }
        else if (tot == 2) {
            if (cnt[2] == 0) {
                if (cnt[0] <= cnt[1])
                    ans[c] = 0;
                else
                    ans[c] = 1;
            } else if (cnt[2] == 1) {
                if (cnt[0] <= cnt[1])
                    ans[c] = 0;
                else
                    ans[c] = 1;
                for (int j = 0; j < tot; j++)
                    if (ans[child[j]] == 2)
                        ans[child[j]] = 1 - ans[c];
            } else if (cnt[2] == 2) {
                ans[c] = 0;
                ans[child[0]] = ans[child[1]] = 1;
            } else
                throw new RuntimeException();
        } else if (tot == 3) {
            if (cnt[0] <= cnt[1]) { 
                ans[c] = 1;
                for (int j = 0; j < tot; j++)
                    if (ans[child[j]] == 2)
                        ans[child[j]] = 0;
            }
            else {
                ans[c] = 0;
                for (int j = 0; j < tot; j++)
                    if (ans[child[j]] == 2)
                        ans[child[j]] = 1;
            }
        } else
            throw new RuntimeException();
    }

    static class InputReader {

        private final InputStream stream;
        private final byte[] buf = new byte[8192];
        private int curChar, snumChars;
        private SpaceCharFilter filter;

        public InputReader(InputStream stream) {
            this.stream = stream;
        }

        public int snext() {
            if (snumChars == -1)
                throw new InputMismatchException();
            if (curChar >= snumChars) {
                curChar = 0;
                try {
                    snumChars = stream.read(buf);
                } catch (IOException e) {
                    throw new InputMismatchException();
                }
                if (snumChars <= 0)
                    return -1;
            }
            return buf[curChar++];
        }

        public int nextInt() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            int res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public long nextLong() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            int sgn = 1;
            if (c == '-') {
                sgn = -1;
                c = snext();
            }
            long res = 0;
            do {
                if (c < '0' || c > '9')
                    throw new InputMismatchException();
                res *= 10;
                res += c - '0';
                c = snext();
            } while (!isSpaceChar(c));
            return res * sgn;
        }

        public int[] nextIntArray(int n) {
            int a[] = new int[n];
            for (int i = 0; i < n; i++) {
                a[i] = nextInt();
            }
            return a;
        }

        public String readString() {
            int c = snext();
            while (isSpaceChar(c)) {
                c = snext();
            }
            StringBuilder res = new StringBuilder();
            do {
                res.appendCodePoint(c);
                c = snext();
            } while (!isSpaceChar(c));
            return res.toString();
        }

        public boolean isSpaceChar(int c) {
            if (filter != null)
                return filter.isSpaceChar(c);
            return c == ' ' || c == '\n' || c == '\r' || c == '\t' || c == -1;
        }

        public interface SpaceCharFilter {
            public boolean isSpaceChar(int ch);
        }
    }
}