IOI '95 P5 - Street Race

View as PDF

Points: 15 (partial)
Time limit: 1.0s
Memory limit: 8M

Problem type
IOI '95 - Eindhoven, Netherlands

Figure 1 gives an example of a course for a street race. You see some points, labeled from to (here ), and some arrows connecting them. Point is the start of the race; point is the finish. The arrows represent one-way streets. The participants of the race move from point to point via the streets, in the direction of the arrows only. At each point, a participant may choose any outgoing arrow.

Figure 1: A street course with points

A well-formed course has the following properties:

1. Every point in the course can be reached from the start.
2. The finish can be reached from each point in the course.
3. The finish has no outgoing arrows.

A participant does not have to visit every point of the course to reach the finish. Some points, however, are unavoidable. In the example, these are points and . Given a well-formed course, your program has to determine the set of unavoidable points that all participants have to visit, excluding start and finish.

Suppose the race has to be held on two consecutive days. For that purpose the course has to be split into two courses, one for each day. On the first day, the start is at point , and the finish at some 'splitting point'. On the second day, the start is at this splitting point and the finish is at point . Given a well-formed course, your program has to determine the set of splitting points.

A point is a splitting point for the well-formed course if differs from the start and the finish of , and the course can be split into two well-formed courses that have no common arrows and that have as only common point. In the example, only point is a splitting point.

Input Specification

The input describes a well-formed course with at most points and at most arrows. There are lines in the input. The first lines contain the endpoints of the arrows that leave from the points through respectively. Each of these lines ends with the number . The last line contains the number .

Output Specification

Your program should write two lines. The first line should contain the number of unavoidable points in the input course, followed by the labels of these points, in ascending order. The second line should contain the number of splitting points of the input course, followed by the labels of all these points, in ascending order.

Sample Input

1 2 -2
3 -2
3 -2
5 4 -2
6 4 -2
6 -2
7 8 -2
9 -2
5 9 -2
-1

Sample Output

2 3 6
1 3