P6635 "JYLOI Round 1" Arrow Scheduling

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.

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 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.

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