야바위 게임

면접 대비

시간 제한1초메모리 제한1024 MB

요약

정점 X에서 출발한 공이 간선을 따라 정확히 Y번 이동했을 때 도달할 수 있는 모든 정점을 찾는다.

난이도: 보통10점 중 5점
유형: 그래프, BFS
정답자: 아직 제출이 없습니다

문제

준석이와 상원이는 게임을 한다. 게임판 위에는 $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$ 을 출력한다.

예제2

예제 1
입력
```
6 6 1 2
1 2
2 3
3 4
4 5
5 6
6 1
```
예상 출력
```
1 3 5
```
예제 2
입력
```
6 4 1 2
2 3
3 4
4 5
5 6
```
예상 출력
```
-1
```