수천 개의 섬

수천 개의 섬은 자바 해역에 있는 아름다운 섬들의 무리이다. 섬은 $N$개이며, 0부터 $N - 1$까지 번호가 붙어 있다.

섬 사이를 오갈 때 쓸 수 있는 카누가 $M$대 있으며, 0부터 $M - 1$까지 번호가 붙어 있다. 각 $0 \le i \le M - 1$에 대해, $i$번 카누는 섬 $U[i]$ 또는 섬 $V[i]$에 정박해 있거나, $U[i]$와 $V[i]$ 사이를 운항 중일 수 있다. 구체적으로, $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$번 카누는 섬 $U[i]$에 정박해 있어야 한다.

부 뎅클렉이 운항 횟수가 최대 $2\,000\,000$번인 유효한 여행을 찾도록 도와주거나, 유효한 여행이 없음을 판단하도록 도와야 한다. 이 문제의 제약 조건에서는 유효한 여행이 존재한다면, 운항 횟수가 $2\,000\,000$번을 넘지 않는 유효한 여행도 존재함을 증명할 수 있다.

• $2 \le N \le 100\,000$
• $1 \le M \le 200\,000$
• 모든 $0 \le i \le M - 1$에 대해 $0 \le U[i] \le N - 1$이고 $0 \le V[i] \le N - 1$이다.
• 모든 $0 \le i \le M - 1$에 대해 $U[i] \ne V[i]$이다.