Дима приехал в страну коней. В стране коней живет n коней. У каждого коня в стране коней есть несколько врагов (отношение вражды симметричное). Страна коней не очень враждебная, поэтому количество врагов каждого коня не превышает трех.
Сейчас в стране коней выборы. Поэтому кони поручили Диме разделить их на две партии. При этом кони хотят, чтобы выполнялось следующее условие: у каждого коня не должно быть более одного врага в своей партии.
Помогите Диме разделить коней на партии. Обратите внимание, что одна из партий может оказаться пустой.
Выходные данные
Выведите строку, состоящую из n символов: i-тый символ строки должен быть равен «0», если конь номер i будет принадлежать первой партии, иначе этот символ должен быть равен «1».
Если не существует способа разделить коней требуемым образом выведите -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 3
1 2
3 2
3 1
|
100
|
|
2
|
2 1
2 1
|
00
|
|
3
|
10 6
1 2
1 3
1 4
2 3
2 4
3 4
|
0110000000
|