Pick up sticks
Time limit1sMemory limit128 MB
Given a set of on-top-of relations between sticks, output the lexicographically smallest removal order, or IMPOSSIBLE if a cycle exists.
- Level
Medium6 of 10
- Topics
- Topological sort, Graph, Heap, Greedy
- Solved
- No attempts yet
Problem
Pick-up sticks is a game played with a tangled heap of coloured sticks dumped on a table. Players take turns removing a single stick at a time without disturbing any of the others. A stick can only be removed when no other stick lies on top of it, so the players want to remove the sticks in an order that never forces them to pull a stick out from underneath another one. Given which sticks lie on top of which, find such an order.
Input
The input contains several test cases. The first line of each test case has two integers and , each at least and at most : is the number of sticks (numbered to ) and is the number of lines that follow. Each of those lines contains two integers and , meaning that at some point stick lies on top of stick . The very last line of the input is 0 0; it is a terminator, not a test case, and must not be processed as one.
Output
For each test case, output an order in which the sticks can be removed so that a stick is never taken while another stick lies on top of it, one stick number per line ( lines in total). Several such orders may exist; to make the answer unique, output the lexicographically smallest one — compare two orders by their sequence of stick numbers from first to last, and choose the order whose first differing position holds the smaller number. If no valid order exists, output a single line containing the word IMPOSSIBLE instead.