시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
---|---|---|---|---|---|
2 초 | 512 MB | 118 | 61 | 45 | 45.918% |
$2N$ knights sit around a round table, they are numbered by King Arthur in clockwise order with integers from 1 to $2N$. Knight $j$ is a neighbor of knights $j - 1$ and $j + 1$, knights 1 and $2N$ are neighbors too. The knights represent $N$ orders, each order is represented by exactly two knights and each knight represents exactly one order.
There are two types of magical potion today prepared by Merlin. Let's call them X and Y. Merlin wants to distribute drinks between the knights satisfying the following conditions:
Find any distribution which conforms with Merlin's requirements or determine that no such distribution exists
The first line contains a single integer $N$ ($2 \le N \le 5 \cdot 10^5$) --- the number of orders represented at the table. Each of the next $N$ lines describes one order and contains two integers $a$ and $b$ ($1 \le a, b \le 2N$), denoting the numbers of knights of that order at the table. All numbers in those $N$ lines are pairwise distinct.
If there is no solution, print a single word "impossible
".
Otherwise, print a single string with $2N$ characters 'X
' and 'Y
' describing the distribution of potions. The $i$-th character must represent the selection for knight $i$.
If there is more than one possible distribution, print any of them.
4 1 5 2 3 6 7 4 8
XYXYYXYX