HCI '16 - Wizardry

View as PDF
Submit solution
Points: 7
Time limit: 0.3s
Memory limit: 64M
Authors:
zj97, damian, fanpu
Problem type

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.

Comments


  • 2
    0xc3  commented on Jan. 22, 2018, 7:32 p.m.

    Time limit seems too strict. Can't even read in input without TLEing (even with C++ and fast input).


  • 0
    nathanl3  commented on Dec. 26, 2016, 4:30 a.m.

    Does the output have to be sorted?


    • 0
      chenj  commented on Dec. 26, 2016, 4:30 p.m.

      The output should be in the order that you must learn the spells