Determining Unavoidable and Intermediate Intersections

A race track is represented by a directed graph. The vertices (intersections) are labeled from 0 to N (inclusive) where 0 is the start and N is the finish. Each directed edge represents a one‐way street. The track is good if it satisfies the following properties:

• Every intersection is reachable from the start.
• From every intersection the finish is reachable.
• The finish has no outgoing streets.

An intersection is called unavoidable if every possible route from the start to the finish must pass through it. (Note that the start and the finish are trivially unavoidable; for this problem they are not reported.)

The track is to be split for a two‐day race. The original track must be partitioned into two good tracks: one from the start to a chosen intermediate intersection, and one from that intersection to the finish. The two parts should share no common street; the intermediate intersection is the only common vertex and it serves as the finish of the first day and the start of the second day.

Your task is to first determine the set of unavoidable intersections (excluding the start and finish). Then, among these, you must choose those intersections S for which the track can be split into two good tracks, and we call such intersections intermediate.

Note. In the example below the unavoidable intersections are 0, 3, 6, 9 but the only intermediate intersection is 3.

Input Format: The first line contains two integers N+1 and M where N+1 is the number of intersections (intersections are labeled 0 through N) and M is the number of one‐way streets. The following M lines each contain two integers u and v indicating a directed edge from u to v.

Output Format: Two lines are to be printed. The first line lists (in increasing order) all unavoidable intersections (excluding 0 and N) separated by a space. The second line lists (in increasing order) all intermediate intersections. If there are none in a category, output an empty line for that category.

Explanation of the example:

Input:
10 13
0 1
0 2
0 3
1 3
2 3
3 4
3 5
4 6
5 6
6 7
6 8
7 9
8 9

Output:
3 6
3

Implementation Note: To solve the problem, one may first determine an intersection S (other than 0 and N) to be unavoidable by temporarily removing S and checking whether the finish becomes unreachable from the start. For intermediate intersections, note that while every splitting point must be unavoidable, not every unavoidable point qualifies. In our solution we use the following heuristic: for every unavoidable intersection S, perform a DFS (with S removed) from the start. Let r(S) be the number of intersections reached. Then S is considered an intermediate intersection if r(S) is minimum among all unavoidable intersections. (In the sample the DFS without 3 reaches 3 vertices while without 6 reaches 6 vertices; hence, only 3 is intermediate.)

inputFormat

The input begins with two integers N+1 and M on one line, where N+1 is the total number of intersections (0 to N) and M is the number of directed edges. Following this are M lines, each with two integers u and v indicating a one-way street from intersection u to intersection v. The given graph is guaranteed to be a good track.

outputFormat

Print two lines. The first line contains the unavoidable intersections (in increasing order, excluding 0 and N) separated by a single space. The second line contains the intermediate intersections (in increasing order). If a set is empty, output an empty line.

sample

10 13
0 1
0 2
0 3
1 3
2 3
3 4
3 5
4 6
5 6
6 7
6 8
7 9
8 9

3 6
3

</p>