Tom wants to learn how to cast some spells. However, as some spells are more advanced than others, there are some spells you have to learn before you learn others. There are some very interesting spells that he wishes to learn. However, many of them are very advanced, which means that he will have to learn many other spells before he learns the interesting spell.

Input

~n~, the number of spells where ~2 \le n \le 2\,000\,000~, followed by ~e~ where ~n>e~, followed by ~i~, the spell Tom wishes to learn. The next ~e~ lines will tell what you have to learn first before others, in the format ~a~ ~b~, where you have to learn spell ~a~ before you learn spell ~b~ (~a \neq b~). The spells will be numbered from ~0~ to ~n - 1~. You are assured that there will be no cycle (e.g. to learn 0, learn 1 first. to learn 1, learn 0 first.).

Output

The spells you will have to learn before Tom can learn the spell ~i~. There will not be more than 1 spell you must learn directly before you can learn a certain spell (e.g. There will not be a line 0 1 and a line 2 1).

Constraints

Subtask 1 [30%]

~2 \le n \le 25~

Subtask 2 [70%]

~2 \le n \le 2\,000\,000~

Sample Input

5 3 2
0 1
1 2
3 4

Sample Output

0 1

Explanation

To learn spell 2, he will have to learn spell 1. To learn spell 1, he will have to learn spell 0.