Want to try solving this problem? You can submit your code online if you log in or register.

The City of Sydney has been having problems with "hooliganism" as of late. Out of control youths are driving around non-stop all night, scaring hippos and driving over daisies. Now you must help implement a plan to lock out these hooligans once and for all.

The City of Sydney is made up of N intersections, numbered 1 to N, connected by R roads. Each night all roads in Sydney will become one-way. You decide which way each road goes. To prevent congestion, each intersection has a maximum number of roads that are allowed to leave from it.

You must find a way to make each of these roads one-way such that each intersection has no more than the specified number of roads leaving it, and that there is no way for hooligans to drive around all night. In particular, hooligans should not be able to drive through the same intersection more than once.

- The first line of input will contain two space-separated
integers N R, representing the number of intersections and roads in Sydney respectively.
- The following N lines of input will each contain an integer a
_{i}, the i-th of which gives the maximum number of one-way roads allowed to leave intersection i. - The following R lines of input will each contain two space-separated
integers b c, indicating that intersections b and c have a road between them.

If Sydney cannot prevent hooligans from driving around all night, then output `IMPOSSIBLE`.

If it is possible for Sydney to construct such a road network, then output R lines, each containing two integers b_{i} c_{i}, indicating a one-way road from intersection b_{i} to intersection c_{i}. These lines must describe every road in Sydney, and can be output in any order.

3 3 0 2 0 1 2 1 3 2 3

IMPOSSIBLE

3 3 1 1 1 1 2 1 3 2 3

IMPOSSIBLE

3 3 1 2 0 1 2 1 3 2 3

1 3 2 1 2 3

For all subtasks, 1 ≤ R ≤ 100,000 and 2 ≤ N ≤ 100,000. Additionally, no two intersections will be directly connected by more than one road, and no intersection will be connected to itself. It is not necessarily possible to go from any intersection to any other.

- For Subtask 1 (20 points), a
_{i}= N, that is, the maximum number of roads allowed to leave each intersection is the same as the number of intersections. - For Subtask 2 (20 points), every intersection has exactly two other intersections connected to it.
- For Subtask 3 (30 points), 1 ≤ R ≤ 100,000 and 2 ≤ N ≤ 1,000.
- For Subtask 4 (30 points), no further constraints apply.

The score for each input scenario will be 100% if a correct answer is written to the output file, and 0% otherwise.

Privacy
statement

© Australian Mathematics Trust 2001-2022

Page generated: 25 September 2022, 3:36am AEST