Shell Game

Interview

Time limit1sMemory limit1024 MB

Summary

Given a start vertex and an exact number of moves Y, find every vertex reachable by a walk of length exactly Y in an undirected graph.

Level: Medium5 of 10
Topics: Graph, BFS, Dynamic programming, Implementation
Solved: No attempts yet

Problem

Junseok and Sangwon play a game. On the board there are $N$ vertices and $M$ edges. Each vertex has one cup on it, and one of the cups holds a ball. Every edge connects two distinct vertices in both directions.

Junseok shuffles the cups, and Sangwon has to guess where the ball is. Junseok can grab two cups connected by an edge and swap their positions.

Sangwon was fooled by Junseok's flashy handwork and forgot how the cups moved. But he remembers the cup that held the ball at the start and the number of times that cup moved.

Given the vertex where the ball's cup started and the number of times that cup moved, find all candidate vertices where the ball's cup can be right now.

Input

The first line gives the number of vertices $N$ , the number of edges $M$ , the vertex number $X$ where the ball is placed at the start of the game, and the number of times $Y$ the ball's cup moved. ( $1 \leq N, Y \leq 10^3$ , $1 \leq M \leq 10^4$ , $1 \leq X \leq N$ )

Each of the next $M$ lines gives the numbers of the two vertices connected by one edge. Vertex numbers range from $1$ to $N$ . There can be multiple edges connecting the same pair of vertices.

Output

Print, in one line, the vertices where the ball can be, in increasing order of vertex number.

If there are no possible candidates, print $-1$ .

Examples2

Example 1
Input
```
6 6 1 2
1 2
2 3
3 4
4 5
5 6
6 1
```
Expected output
```
1 3 5
```
Example 2
Input
```
6 4 1 2
2 3
3 4
4 5
5 6
```
Expected output
```
-1
```