수천개의 섬

수천개의 섬은 자바 해역에 위치한 아름다운 섬들의 그룹이다. 수천개의 섬은 $N$ 개의 섬으로 구성되며 $0$ 부터 $N - 1$ 까지 번호가 붙어 있다.

섬들 사이를 오가는데 사용될 수 있는 카누가 $M$ 개 있고 $0$ 부터 $M - 1$ 까지 번호가 붙어 있다. $0 \le i \le M - 1$ 인 각 $i$ 에 대해, $i$ 번 카누는 섬 $U\[i]$ 나 섬 $V\[i]$ 에 정박해 있거나 $U\[i]$ 와 $V\[i]$ 사이를 운항 중일 수 있다. 특별히, 카누가 섬 $U\[i]$ 에 정박해 있을 때에는 섬 $U\[i]$ 에서 섬 $V\[i]$ 로 운항할 수 있고 이후 섬 $V\[i]$ 에 정박하게 된다. 비슷하게, 카누가 섬 $V\[i]$ 에 정박해 있을 때에는 섬 $V\[i]$ 에서 섬 $U\[i]$ 로 운항할 수 있고 이후 섬 $U\[i]$ 에 정박하게 된다. 처음에 카누는 섬 $U\[i]$ 에 정박해 있다. 여러 카누가 동일한 두 섬 사이를 오가는 것도 가능하다. 한 섬에 여러 카누가 정박하는 것도 가능하다.

안전상의 이유로 카누는 매 운항 이후 유지보수가 필요하고, 이로 인해 같은 카누가 두 번 연속해서 운항하는 것을 금지한다. 즉, $i$ 번 카누가 사용된 후에는, $i$ 번 카누가 다시 사용되기 전에 다른 카누가 반드시 사용되어야 한다.

부 뎅클렉은 몇 개의 섬을 여행할 계획을 세우려고 한다. 그녀의 여행이 유효하다는 것은 다음 조건들이 만족됨을 의미한다.

그녀의 여행은 섬 $0$ 에서 시작해서 섬 $0$ 에서 끝난다.
그녀는 섬 $0$ 이 아닌 다른 섬을 최소한 하나는 방문한다.
여행이 끝나면, 각 카누는 여행이 시작되기 전과 동일한 섬에 정박하게 된다. 즉, $0 \le i \le M - 1$ 인 각 $i$ 에 대해, $i$ 번 카누는 섬 $U\[i]$ 에 정박해야만 한다.

당신은 부 뎅클렉이 최대 $2\\,000\\,000$ 번 운항하는 유효한 여행을 찾도록 도와주거나, 그러한 유효한 여행이 없음을 결정하도록 도와야 한다. 이 문제에서 제시하는 제약조건(Constraints 부분 참고) 하에서는, 만약 유효한 여행이 존재한다면 운항 횟수가 $2\\,000\\,000$ 번을 넘지 않는 유효한 여행이 존재함을 증명할 수 있다.

수천개의 섬

문제

제한