Description

moyu_028 gives you an undirected graph with $n$ vertices and $m$ edges. Now you need to assign a direction to each edge. Please find a direction assignment such that a topological order can be generated under this assignment, and this topological order is the $k$-th smallest in lexicographical order among all possible topological orders.

Input Format

The first line contains three positive integers $n$, $m$, and $k$, as described above.

Then there are $m$ lines. The $i$-th line contains two positive integers $x_i$ and $y_i$, indicating an undirected edge between $x_i$ and $y_i$.

Output Format

Output one line containing a 01 string of length $m$. The $i$-th character indicates the direction of the undirected edge between $x_i$ and $y_i$. If it is 0, the edge is directed from $x_i$ to $y_i$; if it is 1, the edge is directed from $y_i$ to $x_i$. It can be proven that the answer is unique, and the testdata guarantees that a solution exists.

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

0111001

11 20 20091210
2 3
3 1
2 5
4 6
7 9
8 10
8 1
7 2
2 3
3 2
4 5
5 7
7 6
7 8
9 7
9 8
10 2
2 3
1 3
1 7

10110000100110110111

Hint

Topological order: In a DAG (Directed Acyclic Graph), we sort the vertices in a linear order such that for every directed edge $(u,v)$ from vertex $u$ to vertex $v$, $u$ appears before $v$. Such a sequence is called a topological order.

Sample Explanation

Sample 1 Explanation

The graph of the answer is as follows. The answer can be obtained from the graph.

Constraints

For $100\%$ of the testdata, $1 \leq n \leq 11$, $1 \leq m \leq 2 \times 10^3$, $1 \leq k \leq 10^8$, $1 \leq x_i, y_i \leq n$, $x_i \not= y_i$.

For test point 1 (10 points): $n = 1$.

For test point 2 (30 points): $n \leq 11$, $m \leq 20$.

For test point 3 (30 points): $n \leq 11$, $k = 1$.

For test point 4 (30 points): no special constraints.

This problem has 4 test points, with a total score of 100 points. The time limit for each test point is 5 seconds.

Source

"JYLOI Round 1" A

Idea: moyu_028 & abcdeffa

Solution: LiuXiangle

Data: abcdeffa

Translated by ChatGPT 5