[Solution] Edge Split Codeforces Solution

D. Edge Split

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given a connected, undirected and unweighted graph with 𝑛$n$ vertices and 𝑚$m$ edges. Notice the limit on the number of edges: 𝑚≤𝑛+2$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 𝑐1$c_1$. Similarly, consider only the blue edges and count the number of connected components in the graph. Let this value be 𝑐2$c_2$.

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

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡$t$ (1≤𝑡≤105$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≤𝑛≤2⋅105$2\le n\le 2\cdot {10}^5$; 𝑛−1≤𝑚≤min(𝑛+2,𝑛⋅(𝑛−1)2)$n-1\le m\le min(n+2,\frac{n\cdot (n-1)}{2})$) — the number of vertices and the number of edges respectively.

Solution Click Below:-  👉CLICK HERE👈

👇👇👇👇👇

𝑚$m$ lines follow. The 𝑖$i$-th line contains two integers 𝑢𝑖$u_i$ and 𝑣𝑖$v_i$ (1≤𝑢𝑖,𝑣𝑖≤𝑛$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 106${10}^6$. It is guaranteed that the sum of 𝑚$m$ over all test cases does not exceed 2⋅106$2\cdot {10}^6$.

Output

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.