23741번 - 야바위 게임

문제

준석이와 상원이는 게임을 한다. 게임판 위에는 $N$개의 정점과 $M$개의 간선이 있다. 각 정점 위에는 컵이 하나씩 있고 그중 하나에는 공이 들어 있다. 모든 간선은 서로 다른 두 정점을 양방향으로 잇는다.

준석이가 컵을 섞으면 상원이는 공이 어디에 있는지 맞혀야 한다. 준석이는 간선으로 연결된 두 컵을 잡고 위치를 바꿀 수 있다.

상원이는 준석이의 화려한 손기술에 속아서 컵이 어떻게 움직였는지 까먹었다. 하지만 처음에 공이 들어있던 컵과 그 컵을 움직인 횟수는 기억하고 있다.

처음에 공이 들어있는 컵이 있던 정점과 그 컵이 움직인 횟수가 주어지면, 지금 공이 들어있는 컵이 있을 수 있는 정점들의 후보를 모두 찾아보자!

입력

첫 번째 줄에 정점 수 $N,ドル 간선 수 $M,ドル 게임 시작 시 공이 놓여있는 정점 번호 $X,ドル 공이 든 컵이 움직인 횟수 $Y$가 주어진다. (1ドル \leq N, Y \leq 10^3,ドル 1ドル \leq M \leq 10^4,ドル 1ドル \leq X \leq N$)

다음 줄부터 $M$개의 줄 각각에 각 간선이 연결하는 두 정점의 번호가 주어진다. 정점의 번호는 1ドル$부터 $N$까지이다. 어떤 두 정점을 잇는 간선이 여러 개일 수 있다.

출력

공이 있을 수 있는 곳을 정점 번호가 작은 순서대로 한 줄에 출력한다.

가능한 후보가 없다면 $-1$을 출력한다.

제한

힌트