[Solution] Edge Split solution codeforces

Edge Split solution codeforces – You are given a connected, undirected and unweighted graph with 𝑛n vertices and 𝑚m edges. Notice the limit on the number of edges𝑚𝑛+2m≤n+2.

[Solution] Edge Split solution codeforces

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 𝑐1c1. Similarly, consider only the blue edges and count the number of connected components in the graph. Let this value be 𝑐2c2.

Find an assignment of colors to the edges such that the quantity 𝑐1+𝑐2c1+c2 is minimised.

Input

Each test contains multiple test cases. The first line contains a single integer 𝑡t (1𝑡1051≤t≤105) — 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𝑛21052≤n≤2⋅105𝑛1𝑚min(𝑛+2,𝑛(𝑛1)2)n−1≤m≤min(n+2,n⋅(n−1)2)) — the number of vertices and the number of edges respectively.

𝑚m lines follow. The 𝑖i-th line contains two integers 𝑢𝑖ui and 𝑣𝑖vi (1𝑢𝑖,𝑣𝑖𝑛1≤ui,vi≤n𝑢𝑖𝑣𝑖ui≠vi) denoting that the 𝑖i-th edge goes between vertices 𝑢𝑖ui and 𝑣𝑖vi. 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 106106. It is guaranteed that the sum of 𝑚m over all test cases does not exceed 21062⋅106.

[Solution] Edge Split solution codeforces

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.

Example
input

Copy
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
output

Copy
0111010
1001
0001111
0


[Solution] Edge Split solution codeforces

• The corresponding graph of the first test case is:
𝑐1+𝑐2=1+2=3c1+c2=1+2=3
• The corresponding graph of the second test case is:
𝑐1+𝑐2=2+2=4