Edge Split
Contest: Codeforces Round 819 (Div. 1 + Div. 2) and Grimoire of Code Annual Contest 2022
Difficulty rating: 2000
Tags: brute force, constructive algorithms, dfs and similar, dsu, graphs, probabilities, trees

You are given a connected, undirected and unweighted graph with $$$n$$$ vertices and $$$m$$$ edges. Notice the limit on the number of edges: $$$m \le n + 2$$$.

Let's say we color some of the edges red and the remaining edges blue. Now consider only the red edges and count the number of connected components in the graph. Let this value be $$$c_1$$$. Similarly, consider only the blue edges and count the number of connected components in the graph. Let this value be $$$c_2$$$.

Find an assignment of colors to the edges such that the quantity $$$c_1+c_2$$$ is minimised.

Input format:
Each test contains multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^5$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$n-1 \leq m \leq \min{\left(n+2,\frac{n \cdot (n-1)}{2}\right)}$$$) — the number of vertices and the number of edges respectively.

$$$m$$$ lines follow. The $$$i$$$-th line contains two integers $$$u_i$$$ and $$$v_i$$$ ($$$1 \le u_i,v_i \le n$$$, $$$u_i \ne v_i$$$) denoting that the $$$i$$$-th edge goes between vertices $$$u_i$$$ and $$$v_i$$$. The input is guaranteed to have no multiple edges or self loops. The graph is also guaranteed to be connected.

It is guaranteed that the sum of $$$n$$$ over all test cases does not exceed $$$10^6$$$. It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^6$$$.

Output format:
For each test case, output a binary string of length $$$m$$$. The $$$i$$$-th character of the string should be 1 if the $$$i$$$-th edge should be colored red, and 0 if it should be colored blue. If there are multiple ways to assign colors to edges that give the minimum answer, you may output any.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

Note:
- The corresponding graph of the first test case is:  $$$c_1 + c_2 = 1 + 2 = 3$$$
- The corresponding graph of the second test case is:  $$$c_1 + c_2 = 2 + 2 = 4$$$

Example input:
4
5 7
1 2
2 3
3 4
4 5
5 1
1 3
3 5
4 4
1 2
2 3
1 4
3 4
6 7
1 2
1 3
3 4
4 5
1 4
5 6
6 2
2 1
1 2

Example output:
0111010
1001
0001111
0

Editorial:
Let's say for convenience that the set of red edges is called $$$R$$$ and the set of blue edges is called $$$B$$$.
Fact: In at least one optimal configuration, $$$R$$$ or $$$B$$$ forms a spanning tree.
Proof: Let's say that $$$R$$$ is not a spanning tree in some optimal configuration. If we move an edge connecting two disconnected vertices in $$$R$$$ from $$$B$$$ to $$$R$$$ (this edge must exist since the input is a connected graph), $$$c_2$$$ will increase by at most $$$1$$$, and $$$c_1$$$ will decrease by $$$1$$$. Also, if we have a cycle in $$$R$$$, we can move this edge from $$$R$$$ to $$$B$$$ and $$$c_1$$$ won't change. But $$$c_2$$$ may decrease by $$$1$$$. So making $$$R$$$ a spanning tree never makes the answer worse. We can swap $$$R$$$ and $$$B$$$ in this proof, it doesn't matter.
If $$$R$$$ is a spanning tree then $$$c_1=1$$$ and we want to minimise $$$c_2$$$. Clearly, it would be best if there was no cycle in $$$B$$$. It turns out that we can ensure this.
Notice that $$$m \leq (n-1)+3$$$, so the number of extra edges is very small. Let us build a spanning tree using DFS. A DFS tree will only have back edges and no cross edges. If there is no cycle taking these back edges in $$$B$$$, we are done. However, if there is a cycle (and there can be at most $$$1$$$ cycle, since you need at least $$$5$$$ edges for $$$2$$$ cycles), it looks like edges $$$u-v$$$ $$$v-w$$$ $$$u-w$$$ where $$$u$$$ is an ancestor of $$$v$$$ and $$$v$$$ is an ancestor of $$$w$$$. It is easy to get rid of this cycle by dropping one back edge ending at $$$w$$$ and taking the span edge connecting $$$w$$$ with its parent in the DFS tree. Note that $$$R$$$ remains a spanning tree. Hence we are done.
Time complexity: $$$\mathcal{O}(n)$$$