eolymp
bolt
Try our new interface for solving problems
Problems

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

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

Федерація об'єктноорієнтованого програмування вирішила втрутитися в політку Країни УУП. У Країні УУП $n$ міст, які з'єднані між собою $n-1$ двосторонніми дорогами так, що між будь-якими двома містами існує сполучення. Міста Країни УУП пронумеровані цілими числами від $1$ до $n$. Множину міст $S$ Федерація вважає хорошою, якщо виконуються наступні умови: \begin{itemize} \item Для будь-якої пари міст з множини $S$ існує сполучення між цими містами, що містить лише міста з множини $S$. \item Кількість міст з множини $S$ є непарною. \end{itemize} Зверніть увагу, що множина $S$ може містити лише одне місто. Для розробки плану втручання у політику Пану X та Пану Y доведеться зіграти у таку гру: \begin{itemize} \item Гравці виконуватимуть ходи по черзі, починаючи з Пана X. \item На своєму кроці гравець повинен вибрати певну хорошу підмножину міст та замалювати олівцем на мапі ці міста. Звісно, двічі замальовувати одне і те саме місто не дозволяється. \item Програє той гравець, який не зможете зробити свій хід. \end{itemize} Знайдіть, хто ж виграє у цій грі, при умові що обидва гравці користуються оптимальними стратегіями. \InputFile Перший рядок містить одне ціле число $n$ ($1\le n\le 10^5$). Кожен з наступних $n-1$ рядків містить по два цілі числа $u$ та $v$ ($1\le u, v\le n$, $u\ne v$)~--- номери міст, які сполучає відповідна дорога. \OutputFile Виведіть <<\t{Pan X}>>, якщо виграє Пан X, або <<\t{Pan Y}>>, якщо виграє Пан Y. \Note У першому прикладі при замальовуванні Паном X будь-якого з двох міст, Пан Y замалює на свому ході інше місто, після чого переможе. \Scoring Рішення, які правильно працюватимуть при $n\le 6$, набиратимуть не менше $50\%$ балів.
Time limit 1 second
Memory limit 256 MiB
Input example #1
2
1 2
Output example #1
Pan Y
Input example #2
3
1 2
2 3
Output example #2
Pan X
Author Ihor Barenblat