Ланцюжок доміно

Обмеження: 2 сек., 512 МіБ

Марічка дала Зенику послідовність із \(n\) доміношок. Кожна доміношка складається з двох половин, на яких є певна кількість цяток.

Зеник хоче викласти всі доміношки в ряд у заданому порядку. Кожну доміношку можна перевернути, помінявши її ліву та праву половини місцями. Переставляти доміношки не можна.

Ряд викладено правильно, якщо для кожної пари сусідніх доміношок кількість цяток на правій половині попередньої дорівнює кількості цяток на лівій половині наступної. Допоможіть Зенику визначити, чи можна правильно викласти задану послідовність.

Вхідні дані

У першому рядку задано одне ціле число \(n\) — кількість доміношок.

У наступних \(n\) рядках задано по два цілі числа \(a_i\) та \(b_i\) — кількість цяток на лівій та правій половинах \(i\)-тої доміношки відповідно. Доміношки задано в тому порядку, у якому їх потрібно викласти.

Вихідні дані

В єдиному рядку виведіть TAK, якщо доміношки можна правильно викласти в заданому порядку, або NI, якщо це неможливо.

Обмеження

\(1 \le n \le 10^5\),

\(0 \le a_i, b_i \le 6\) для всіх \(1 \le i \le n\).

Приклади

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
4 1 2 3 2 3 3 4 3	TAK

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
3 1 2 2 3 2 4	NI

Вхідні дані (stdin) копіювати	Вихідні дані (stdout) копіювати
1 0 6	TAK

Примітки

У першому прикладі можна перевернути другу та четверту доміношки й отримати такий ряд:

На кожному стику кількості цяток збігаються.

У другому прикладі обидва стики з другою доміношкою потребують половини з 2 цятками. Друга доміношка має лише одну таку половину, тому правильно викласти ряд неможливо.

У третьому прикладі є лише одна доміношка, тому умова для сусідніх доміношок виконується.