우랄의 하키

우랄 지역 하키의 대중화와 하키 팀들의 기량 향상을 위해 전우랄 토너먼트가 열렸다. 토너먼트에는 우랄 지역 도시들의 하키 팀 $N$개가 초청되었다.

각 팀이 한 경기씩 치른 처음 두 라운드가 끝난 뒤, 팀이 너무 많다는 사실이 드러났다. 토너먼트 조직위원회는 처음 두 라운드에서 서로 맞붙지 않은 팀 $K$개만 이후 참가를 허용하기로 결정했다.

조건을 만족하는 $K$개 팀의 집합을 찾는 프로그램을 작성하라. 그러한 집합이 존재하지 않으면 불가능하다는 메시지를 출력해야 한다. 조건을 만족하는 집합이 여러 개라면 그중 아무거나 하나를 찾으면 된다.

첫째 줄에는 수 $N$이 주어진다 ($2 \leqslant N \leqslant 100\,000$, $N$은 짝수).

다음 $N$개 줄에는 이미 치러진 모든 경기의 정보가 주어진다. 각 경기의 정보는 경기에 참가한 두 팀의 번호이며, 각각 $N$을 넘지 않는 자연수이다. 처음 $N/2$개 줄은 첫 라운드의 경기이고, 나머지 줄은 둘째 라운드의 경기이다.

마지막 줄에는 수 $K$가 하나 주어진다 ($2 \leqslant K \leqslant N$).

각 팀은 정확히 두 경기를 치렀다. 즉 첫 라운드에서 한 경기, 둘째 라운드에서 한 경기를 치렀음이 보장된다.

해가 존재하지 않으면 수 $0$을 하나 출력한다. 그렇지 않으면 선택한 팀의 번호 $K$개를 서로 다르게 출력한다.

• $N \leqslant 100\,000$