Quiet Quarry

# Quiet Quarry ## Problem Farmer Bessie is managing a quarry operation with N tasks that must be completed. Each task has a unique ID from 1 to N. Some tasks have prerequisites — before starting task B, task A must be completed first. Your job is to find a valid order to complete all N tasks such that all prerequisite constraints are satisfied. If no valid order exists (due to a cycle), output `IMPOSSIBLE`. ## Input The first line contains two integers N and M: - N: the number of tasks (1 ≤ N ≤ 100,000) - M: the number of prerequisite relationships (0 ≤ M ≤ 200,000) The next M lines each contain two integers A and B, meaning task A must be completed before task B can begin. ## Output If a valid order exists, output N integers representing one valid ordering of the tasks. If a cycle is detected, output `IMPOSSIBLE`. ## Constraints - 1 ≤ N ≤ 100,000 - 0 ≤ M ≤ 200,000 - 1 ≤ A, B ≤ N - A ≠ B ## Sample Input ``` 4 3 1 3 2 3 3 4 ``` ## Sample Output ``` 1 2 3 4 ``` ## Explanation There are 4 tasks. The edges are: - Task 1 must be done before task 3 - Task 2 must be done before task 3 - Task 3 must be done before task 4 One valid order is [1, 2, 3, 4]. Task 1 and 2 can be done in any order (or in parallel), followed by task 3, then task 4. Other valid orderings include [2, 1, 3, 4].