eolymp
bolt
Try our new interface for solving problems
Problems

Друзья и враги

Друзья и враги

Time limit 1 second
Memory limit 256 MiB

На острове Дженту живут n крокодилов. Каждый крокодил имеет ровно одного друга и ровно одного врага среди остальных крокодилов на острове. Отношения дружбы и вражды симметричны: если крокодил A - друг крокодила B, то крокодил B - друг крокодила A; если же крокодил A - враг крокодила B, то и крокодил B - враг крокодила A. Никакой крокодил не является одновременно врагом и другом другого крокодила. Кроме того, никакой крокодил не может быть ни другом, ни врагом самому себе.

Крокодилы острова Дженту весьма эмоциональны. Когда встречаются два врага, они со страшной силой колотят по земле хвостами, а затем происходит Битва Крокодилов. Когда встречаются два друга, они исполняют разрушительный Танец Дружбы Крокодилов.

Недавно танцы и битвы разбудили вулкан, находящийся под островом, и остров раскололся на две части. Вулкан успокоился, но крокодилы опасаются, что дальнейшие танцы и битвы разбудят его снова, и обе половины острова зальёт лава.

Теперь крокодилы хотят расселиться по двум половинам острова таким образом, чтобы на каждой половине оказалось нейтральное множество крокодилов - такое множество, что никакие два крокодила в нём не являются ни друзьями, ни врагами. Расселившись так, крокодилы не будут устраивать танцы и битвы, а значит, можно надеяться, что вулкан не будет извергаться снова.

Крокодилы острова Дженту мудры, но непрактичны. Они понимают, что при таком устройстве дружбы и вражды разделение крокодилов на два нейтральных множества всегда возможно, но не знают, как именно разделиться на такие множества.

Помогите им! Найдите такое разбиение крокодилов на два множества, что у каждого крокодила в своём множестве нет ни друзей, ни врагов.

Input data

В первой строке входного файла задано натуральное число n - количество крокодилов (4n100). Следующие n строк описывают крокодилов. В первой из них записаны два числа f_1 и e_1 через пробел - номер друга первого крокодила и номер его врага. Во второй записаны числа f_2 и e_2 - номера друга и врага второго крокодила, и так далее. В последней из этих строк записаны f_n и e_n - друг и враг крокодила с номером n. Крокодилы пронумерованы числами от 1 до n в том порядке, в котором они описываются во входном файле.

Все числа f_k и e_k целые и лежат в пределах от 1 до n, включительно. Отношения дружбы и вражды симметричны. Друг и враг каждого крокодила различны. Никакой крокодил не является ни другом, ни врагом самому себе.

Output data

В первой строке выходного файла выведите n чисел через пробел. Каждое из этих чисел должно быть равно либо 1, либо 2. Если i-е и j-е числа равны, это означает, что крокодилы с номерами i и j оказались на одной половине острова. Если же эти числа различны, значит, крокодилы i и j оказались на разных половинах острова.

Если правильных ответов несколько, можно вывести любой из них.

Examples

Input example #1
4
2 4
1 3
4 2
3 1
Output example #1
1 2 1 2
Author Ivan Kazmenko