- Time limit: 1.00 s
- Memory limit: 512 MB
Given an undirected graph, your task is to choose a direction for each edge so that the resulting directed graph is strongly connected.
Input
The first input line has two integers and : the number of nodes and edges. The nodes are numbered .
After this, there are lines describing the edges. Each line has two integers and : there is an edge between nodes and .
You may assume that the graph is simple, i.e., there are at most one edge between two nodes and every edge connects two distinct nodes.
Output
Print lines describing the directions of the edges. Each line has two integers and : there is an edge from node to node . You can print any valid solution.
If there are no solutions, only print "IMPOSSIBLE".
Constraints
Example
Input:
3 3 1 2 1 3 2 3
Output:
1 2 2 3 3 1