Rating changes for last rounds are temporarily rolled back. They will be returned soon.
×

The package for this problem was not updated by the problem writer or Codeforces administration after we've upgraded the judging servers. To adjust the time limit constraint, a solution execution time will be multiplied by 2. For example, if your solution works for 400 ms on judging servers, then the value 800 ms will be displayed and used to determine the verdict.

Codeforces Round 167 (Div. 2) |
---|

Finished |

Virtual contest is a way to take part in past contest, as close as possible to participation on time. It is supported only ICPC mode for virtual contests.
If you've seen these problems, a virtual contest is not for you - solve these problems in the archive.
If you just want to solve some problem from a contest, a virtual contest is not for you - solve this problem in the archive.
Never use someone else's code, read the tutorials or communicate with other person during a virtual contest.

combinatorics

constructive algorithms

graphs

*2200

No tag edit access

The problem statement has recently been changed. View the changes.

×
E. Dima and Horses

time limit per test

2 secondsmemory limit per test

256 megabytesinput

standard inputoutput

standard outputDima 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* — 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 *a*_{i}, *b*_{i} (1 ≤ *a*_{i}, *b*_{i} ≤ *n*; *a*_{i} ≠ *b*_{i}), which mean that horse *a*_{i} is the enemy of horse *b*_{i}.

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

Codeforces (c) Copyright 2010-2024 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Apr/24/2024 12:30:17 (l1).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|