Федерація ООП#10708

Федерація ООП

1 second

256 megabytes

Medium

Федерація об'єктно-орієнтованого програмування вирішила втрутитися в політику Країни УУП.

У Країні УУП $n$ міст, які з'єднані між собою $n - 1$ n-1 двосторонніми дорогами так, що між будь-якими двома містами існує шлях. Міста Країни УУП пронумеровано цілими числами від $1$ до $n$ .

Множина міст $S$ вважається хорошою, якщо виконуються наступні умови:

Для будь-якої пари міст із множини $S$ існує шлях між цими містами, що містить лише міста з множини $S$ .
Кількість міст у множині $S$ є непарною.

Зверніть увагу, що множина $S$ може містити лише одне місто.

Щоб розробити план втручання у політику, Пану X і Пану Y доведеться зіграти у таку гру:

Гравці виконують ходи по черзі, починаючи з Пана X.
На своєму ході гравець повинен вибрати певну хорошу підмножину міст і замалювати ці міста на мапі. Двічі замальовувати одне й те саме місто не дозволяється.
Програє той гравець, який не може зробити свій хід.

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

Input

Перший рядок містить одне ціле число $n$ ( $1 \leq n \leq 1 0^{5}$ 1 \le n \le 10^5).

Кожен із наступних $n - 1$ n-1 рядків містить два цілі числа $u$ та $v$ ( $1 \leq u, v \leq n$ 1 \le u, v \le n, $u \neq = v$ u \ne v) — номери міст, які поєднує відповідна дорога.

Output

Виведіть Pan X, якщо виграє Пан X, або Pan Y, якщо виграє Пан Y.

Examples

Example 1

Example 2

Note

У першому прикладі, якщо Пан X замалює будь-яке з двох міст, Пан Y на своєму ході замалює інше місто і переможе.

Scoring

Рішення, які правильно працюватимуть для $n \leq 6$ n \le 6, набиратимуть не менше $50%$ балів.