gwcc2p4

G.W. Coding Contest 2 P4: Giving to Guidance

The staff at Dr. G.W. Williams are having trouble scheduling students for next semester, so they have offloaded the work onto you! Given a students \(N\) courses, and \(M\) boundaries of the schedule, return the scheduled order of the courses. A boundary is defined as course \(A\) must come before course \(B\).

Input Specification:

The first line of input will contain two integers, \(N\) and \(M\), where \(N\) is an integer representing the number of courses and \(M\) is an integer representing the number of boundaries.

The next \(N\) lines will contain each of the course names

The next \(M\) lines will contain two strings representing the names of the courses. The course that appears first must come before the course that appears second in each line.

Any possible output will be accepted. There will always be some correct answer.

Output Specification:

The output will contain \(N\) strings, representing the correct order of the courses.

Each string should be seperated by only one space, including the final string. Any mismatching whitespace will graded as incorrect.

TIME CONSTRAINT: 1s

Sample Input 1:

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

Sample Output 1:

1 3 2 4 5

Explanation for Sample Input 1:

There are 5 courses and 5 course boundaries.
According to the boundaries, 1 comes before 2, 1 comes before 3, 2 comes before 4, 3 comes before 2 and 4 comes before 5. Thus, the course order must be 1 3 2 4 5.

Sample Input 2:

5 4
History
Math
French
Business
Geography
History Math
Math French
French Business
Business Geography

Sample Output 2:

History Math French Business Geography

Explanation for Sample Input 2:

There are 5 courses and 4 course boundaries.
History comes before Math, Math comes before French and Business comes before Geography. The correct order is therefore:
History Math French Business Geography.