Thousands Islands | 프로그래밍의 벗 PivotOJ

문제

Thousands Islands is a group of beautiful islands located in the Java Sea. It consists of $N$ islands, numbered from $0$ to $N - 1$ .

There are $M$ canoes, numbered from $0$ to $M - 1$ , that can be used to sail between islands. For each $i$ such that $0 \le i \le M - 1$ , canoe $i$ can be docked either at island $U [i]$ or $V [i]$ , and can be used to sail between islands $U [i]$ and $V [i]$ . Specifically, when the canoe is docked at island $U [i]$ , it can be used to sail from island $U [i]$ to island $V [i]$ , after which the canoe becomes docked at island $V [i]$ . Similarly, when the canoe is docked at island $V [i]$ , it can be used to sail from island $V [i]$ to island $U [i]$ , after which the canoe becomes docked at island $U [i]$ . Initially, the canoe is docked at island $U [i]$ . It is possible that multiple canoes can be used to sail between the same pair of islands. It is also possible that multiple canoes are docked at the same island.

For safety reasons, a canoe needs to be maintained after every time it is sailed, which forbids the same canoe to be sailed two times in a row. That is, after using some canoe $i$ , another canoe must be used before canoe $i$ can be used again.

Bu Dengklek wants to plan a journey through some of the islands. Her journey is valid if and only if the following conditions are satisfied.

She starts and ends her journey at island $0$ .
She visits at least one island other than island $0$ .
After the journey ends, each canoe is docked at the same island as it was before the journey. I.e., canoe $i$ , for each $i$ such that $0 \le i \le M - 1$ , must be docked at island $U [i]$ .

Help Bu Dengklek find any valid journey involving sailing at most $2\,000\,000$ times, or determine that no such valid journey exists. It can be proven that under the constraints specified in this task (see Constraints section), if a valid journey exists, there also exists a valid journey that does not involve sailing more than $2\,000\,000$ times.