CF1726D.Edge Split

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.

给你一个包含 $n$ 个顶点和 $m$ 条边的连通、无向、无权图。注意边数的限制：$m \le n + 2$。

我们对部分边染成红色，其余边染成蓝色。现在仅考虑红色边，并计算该子图中的连通分量数量，记为 $c_1$；类似地，仅考虑蓝色边，并计算该子图中的连通分量数量，记为 $c_2$。

请找出一种边的染色方案，使得 $c_1 + c_2$ 的值最小。

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

每个测试包含多个测试用例。第一行包含一个整数 $t$（$1 \le t \le 10^5$），表示测试用例的数量。随后是各测试用例的描述。

每个测试用例的第一行包含两个整数 $n$ 和 $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)}$），分别表示顶点数和边数。

接下来是 $m$ 行。第 $i$ 行包含两个整数 $u_i$ 和 $v_i$（$1 \le u_i,v_i \le n$，$u_i \ne v_i$），表示第 $i$ 条边连接顶点 $u_i$ 和 $v_i$。输入保证不存在重边或自环，且图是连通的。

保证所有测试用例的 $n$ 之和不超过 $10^6$；保证所有测试用例的 $m$ 之和不超过 $2 \cdot 10^6$。

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.

对于每个测试用例，输出一个长度为 $m$ 的二进制字符串。该字符串的第 $i$ 个字符应为 1，表示第 $i$ 条边应染成红色；为 0，表示第 $i$ 条边应染成蓝色。若存在多种染色方案可达到最小答案，输出任意一种即可。

• 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$

• 第一个测试用例对应的图如下：

  

  $c_1 + c_2 = 1 + 2 = 3$

• 第二个测试用例对应的图如下：

  

  $c_1 + c_2 = 2 + 2 = 4$