Гра з картками

Тьомич і n його друзів грають у гру. Тьомич виходить з кімнати. На картках пишуться числа від 1 до n, і кожен з друзів бере собі по одній картці так, щоб Тьомич не знав, у кого яка картка. Вважатимемо, що друзі перенумеровані числами від 1 до n. Після того, як Тьомич повертається, кожен з друзів виголошує по 2 висловлювання наступного виду (сформульовані для друга номер i):

1. У мене картка a[i].

2. У людини номер b[i] картка c[i] (b[i] ≠ i).

З кожних двох таких тверджень одне є істинним, а інше хибним. Відомо, що жодні двоє людей не сказали, що у людини b картка c, і жодна людина не сказала, що у людини b картка c у випадку, якщо людина b зізналася, що у неї саме ця картка. Завдання Тьомича - визначити для кожного друга, яке з висловлювань є істинним.

Вхідні дані

У першому рядку розташоване число n (2 ≤ n ≤ 1000). У наступних n рядках знаходяться трійки чисел a[i], b[i], c[i] - показання друзів.

Вихідні дані

Виведіть через пробіл n чисел - номер висловлювання кожного з друзів (1 або 2), яке є істинним. Гарантується, що хоча б одне рішення існує.

Приклади