Directed Graph Orientation with k-th Lexicographical Topological Order

You are given an undirected graph with n vertices and m edges. Your task is to assign a direction to each edge such that the resulting directed graph is acyclic. Moreover, if we list all valid topological orders of the resulting DAG in lexicographical order (i.e. comparing the ordered sequence of vertices element‐by‐element), the topological order corresponding to your assignment must be the k-th smallest.

One way to guarantee a valid assignment is to choose a permutation P = [P₁, P₂, ..., P_n] of the vertices and, for every undirected edge {u,v}, direct the edge from u to v if u appears earlier than v in the permutation P (i.e. if index_P(u) < index_P(v)); otherwise, direct it from v to u. This will result in a DAG which has P as one of its topological orders. Note that the DAG may have other topological orders as well; however, the assignment must be such that the permutation P is exactly the k-th lexicographical topological order among all valid ones.

A natural approach is to choose P as the k-th permutation of {1, 2, …, n} in lexicographical order. Then, for every edge (u, v) given in the input, define its orientation as follows:

$$\text{if } pos_{P}(u) < pos_{P}(v):\quad u \to v, \\[6pt] \text{otherwise}:\quad v \to u. $$

You need to output the assigned directions for the m edges in the same order as they are given in the input. It is guaranteed that an answer exists.

inputFormat

The first line contains three integers n, m and k where:

• n (1 ≤ n ≤ 10) is the number of vertices.
• m is the number of edges.
• k (1 ≤ k ≤ n!) is the index in lexicographical order.

Each of the next m lines contains two integers u and v (1 ≤ u,v ≤ n, u ≠ v) representing an undirected edge between u and v.

outputFormat

Output m lines. The i-th line should contain two integers a and b, representing that the i-th edge (in input order) is directed from vertex a to vertex b.

Note: The orientation must be chosen such that if we take the k-th lexicographical permutation of {1,2,…,n} (denoted by P) and assign each edge from the vertex appearing earlier in P to the later one, then P is exactly the k-th smallest topological order among all topological orders of the resulting DAG.

sample

3 3 2
1 2
2 3
3 1

1 2
3 2
1 3

</p>