Finding Cities at a Specific Distance

Interview

Time limit2sMemory limit256 MB

Summary

Given a directed unweighted graph, print every city whose shortest distance from a start city equals K, in increasing order, or -1 if none exist.

Level: Medium4 of 10
Topics: Graph, BFS, Shortest path
Solved: No attempts yet

Problem

A country has cities numbered 1 through N and M one-way roads. Every road has distance 1.

Write a program that prints the numbers of all cities reachable from a given city X whose shortest distance from X is exactly K. The shortest distance from the starting city X to itself is always 0.

For example, suppose N=4, K=2, X=1 and the graph is built as follows.

Among the cities reachable from city 1, the only one whose shortest distance is 2 is city 4. Cities 2 and 3 have shortest distance 1, so they are not printed.

Input

The first line gives the number of cities N, the number of roads M, the distance K, and the number of the starting city X. (2 ≤ N ≤ 300,000, 1 ≤ M ≤ 1,000,000, 1 ≤ K ≤ 300,000, 1 ≤ X ≤ N) The next M lines each give two positive integers A and B separated by a space. This means a one-way road goes from city A to city B. (1 ≤ A, B ≤ N) Here A and B are distinct positive integers.

Output

Among the cities reachable from X, print the numbers of all cities whose shortest distance is K, one per line in increasing order.

If no reachable city has shortest distance exactly K, print -1.

Examples3

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