| Codeforces Round 167 (Div. 2) |
|---|
| Закончено |
Дима приехал в страну коней. В стране коней живет n коней. У каждого коня в стране коней есть несколько врагов (отношение вражды симметричное). Страна коней не очень враждебная, поэтому количество врагов каждого коня не превышает трех.
Сейчас в стране коней выборы. Поэтому кони поручили Диме разделить их на две партии. При этом кони хотят, чтобы выполнялось следующее условие: у каждого коня не должно быть более одного врага в своей партии.
Помогите Диме разделить коней на партии. Обратите внимание, что одна из партий может оказаться пустой.
В первой строке записаны два целых числа n, m 
— количество коней в стране коней и количество пар врагов.
В следующих m строках заданы пары врагов. В i-той строке записаны целые числа ai, bi (1 ≤ ai, bi ≤ n; ai ≠ bi), которые обозначают, что конь ai враг коня bi.
Считайте, что кони пронумерованы некотором образом от 1 до n. Гарантируется, что у каждого коня не более трех врагов. Никакая пара врагов не задана во входных данных более одного раза.
Выведите строку, состоящую из n символов: i-тый символ строки должен быть равен «0», если конь номер i будет принадлежать первой партии, иначе этот символ должен быть равен «1».
Если не существует способа разделить коней требуемым образом выведите -1.
3 3
1 2
3 2
3 1
100
2 1
2 1
00
10 6
1 2
1 3
1 4
2 3
2 4
3 4
0110000000
