Contests | Virtual Contests | Problems | Submit | Runs Status | Rank List | Forum |

Time Limit: 3.0 Seconds Memory Limit: 65536K Special Judge

Total Runs: 66 Accepted Runs: 44 Multiple test files

Case Time Limit: 2.0 Seconds

According to the Automobile Collision Monitor (ACM), most fatal traffic accidents
occur on two-way streets. In order to reduce the number of fatalities caused by
traffic accidents, the mayor wants to convert as many streets as possible into
one-way streets. You have been hired to perform this conversion, so that from
each intersection, it is possible for a motorist to drive to all the other intersections
following some route.

You will be given a list of streets (all two-way) of the city. Each street connects two intersections, and does not go through an intersection. At most four streets meet at each intersection, and there is at most one street connecting any pair of intersections. It is possible for an intersection to be the end point of only one street. You may assume that it is possible for a motorist to drive from each destination to any other destination when every street is a two-way street.

**Input**

The input consists of a number of cases. The first line of each case contains
two integers n and m. The number of intersections is n (2 ≤ n ≤ 1000),
and the number of streets is m. The next m lines contain the intersections incident
to each of the m streets. The intersections are numbered from 1 to n, and each
street is listed once. If the pair i j is present, j i will not be present.
End of input is indicated by n = m = 0.

**Output**

For each case, print the case number (starting from 1) followed by a blank line.
Next, print on separate lines each street as the pair i j to indicate that the
street has been assigned the direction going from intersection i to intersection
j. For a street that cannot be converted into a one-way street, print both i
j and j i on two different lines. The list of streets can be printed in any
order. Terminate each case with a line containing a single `#' character.

Note: There may be many possible direction assignments satisfying the requirements. Any such assignment is acceptable.

**Sample Input**

7 10 1 2 1 3 2 4 3 4 4 5 4 6 5 7 6 7 2 5 3 6 7 9 1 2 1 3 1 4 2 4 3 4 4 5 5 6 5 7 7 6 0 0

**Sample Output**

1 1 2 2 4 3 1 3 6 4 3 5 2 5 4 6 4 6 7 7 5 # 2 1 2 2 4 3 1 4 1 4 3 4 5 5 4 5 6 6 7 7 5 #

**Note:** Special judge problem, you may get "Wrong Answer" when output in wrong format.

Maintance:G.D.Retop. Developer: SuperHacker, G.D.Retop