Problem Description

There are $ N $ people trying to park their cars in a parking lot. The parking lot has $ N $ parking spaces numbered from $ 1 $ to $ N $. There are also $ M $ bidirectional roads connecting pairs of parking spaces, where the $ i $-th road connects the $ u_i $-th and $ v_i $-th parking spaces. The parking space $ S $ is connected to the entrance of the parking lot.

For some reason, the $ i $-th person only wants to park their car in the $ i $-th parking space. Therefore, if they cannot reach the $ i $-th parking space from the entrance through roads and empty parking spaces that are not occupied by anyone, they will leave without parking their car.

People from the $ 1 $-st to the $ N $-th will come to the parking lot in order. Output the numbers of the people who eventually park their cars in the parking lot in ascending order.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ S $ $ u_1 $ $ v_1 $ : $ u_M $ $ v_M $

Output Format

Output the numbers of the people who eventually park their cars in the parking lot in ascending order, one per line.

Sample Input and Output

Sample Input #1

3 3 2
1 2
2 3
1 3

Sample Output #1

1
2

Sample Input #2

5 6 5
1 5
3 5
3 2
4 1
1 2
4 3

Sample Output #2

1
2
3
5

Sample Input #3

5 5 5
1 4
4 3
3 2
2 5
5 1

Sample Output #3

1
2
5

Notes/Hints

Constraints

• $1 \leq N, M \leq 2 \times 10^5$
• $1 \leq u_i, v_i \leq N$
• $u_i \neq v_i$
• $1 \leq S \leq N$
• It is possible to reach all parking spaces from the entrance via roads and parking spaces.

Partial Points

• If you correctly solve all test cases where $M \leq 2,000$, you will be awarded 40 points as partial credit.

Sample Explanation 1

The $ 1 $-st car can park in space $ 1 $. The $ 2 $-nd car can park in space $ 2 $. The $ 3 $-rd car cannot reach space $ 3 $ because it is blocked by the $ 2 $-nd car and thus leaves.

Sample Explanation 2

Using blue circles for empty parking spaces and red circles for occupied parking spaces, the parking spaces fill up in the order shown in the figure, and the $ 4 $-th car cannot park.

见题面 Input 部分

见题面 Output 部分