Town
In the city, traffic congestion is a significant issue. Most residents prefer driving cars over walking. The challenge arises because the streets are narrow, and the cars are wide. When two cars travel in opposite directions on the same street, it results in a traffic jam. To address this, the decision has been made to convert all streets into one-way roads. However, there is a shortage of road signs, so your assistance is required.
You are provided with a city map represented as a planar graph. Your task is to assign directions to all the streets, adhering to the following constraint: No more than three outgoing arcs can originate from any vertex (the number of incoming arcs is unrestricted). You do not need to consider other factors such as vertex reachability or strong connectivity. If multiple solutions are possible, you may choose any one of them.
Input
The first line of input contains two integers N and M (1 ≤ N ≤ 200000, 1 ≤ M ≤ 1000000), where N is the number of vertices, and M is the number of edges. The following M lines describe the edges, with each edge specified by two adjacent vertices i and j (1 ≤ i, j ≤ N). The graph is guaranteed to be planar, meaning it can be drawn on a plane with vertices as points and edges as segments, such that no two segments intersect except at their endpoints. The graph contains no loops or multiple edges.
Output
The output should be in the same format as the input, but with the edges directed. An edge (i, j) indicates a direction from i to j. If it is impossible to assign directions under the given constraints, output the word no.