Line Up
Time limit2sMemory limit128 MB
Given N students and M precedence constraints, compute the minimum and maximum possible position each student can occupy in any valid linear order, or report impossibility if a cycle exists.
- Level
Medium7 of 10
- Topics
- Topological sort, Graph, Bit manipulation
- Solved
- No attempts yet
Problem
N students want to stand in one line according to their height order. Since their exact heights cannot be measured directly, only the relative order of some pairs of students is known.
Given these comparison results, determine the range of positions each student can occupy in the line. Positions are numbered from 1 at the front to N at the back.
Input
The first line contains N (1 ≤ N ≤ 256) and M (1 ≤ M ≤ 100,000), the number of height comparisons.
Each of the next M lines contains two student numbers A and B. This means student A must stand before student B. The same pair of students may have been compared more than once. A and B are never the same student.
Output
Print N lines. On line i, print the earliest and latest positions where student i can stand.
If no valid line can satisfy all comparisons, print -1 on the first line.
Hint
In the provided visible case, students 1 and 2 have no fixed order between them, but both must stand before student 3. Therefore students 1 and 2 can each occupy positions 1 through 2, while student 3 can only occupy position 3.