You are given a simple connected undirected graph, consisting of 𝑛n vertices and 𝑚m edges. The vertices are numbered from 11 to 𝑛n. For each testcase, the first line should contain YES if a lenient vertex cover exists, and NO otherwise. If it exists, the second line should contain a binary string 𝑠s of length 𝑛n, where 𝑠𝑖=0si=0 means that vertex 𝑖i is in the vertex cover, and 𝑠𝑖=1si=1 means that vertex 𝑖i isn’t.
Lenient Vertex Cover solution codeforces
A vertex cover of a graph is a set of vertices such that each edge has at least one of its endpoints in the set.
Let’s call a lenient vertex cover such a vertex cover that at most one edge in it has both endpoints in the set.
Find a lenient vertex cover of a graph or report that there is none. If there are multiple answers, then print any of them.
The first line contains a single integer 𝑡t (1≤𝑡≤1041≤t≤104) — the number of testcases.
The first line of each testcase contains two integers 𝑛n and 𝑚m (2≤𝑛≤1062≤n≤106; 𝑛−1≤𝑚≤min(106,𝑛⋅(𝑛−1)2)n−1≤m≤min(106,n⋅(n−1)2)) — the number of vertices and the number of edges of the graph.
Each of the next 𝑚m lines contains two integers 𝑣v and 𝑢u (1≤𝑣,𝑢≤𝑛1≤v,u≤n; 𝑣≠𝑢v≠u) — the descriptions of the edges.
For each testcase, the graph is connected and doesn’t have multiple edges. The sum of 𝑛n over all testcases doesn’t exceed 106106. The sum of 𝑚m over all testcases doesn’t exceed 106106.
Lenient Vertex Cover solution codeforces
For each testcase, the first line should contain YES if a lenient vertex cover exists, and NO otherwise. If it exists, the second line should contain a binary string 𝑠s of length 𝑛n, where 𝑠𝑖=0si=0 means that vertex 𝑖i is in the vertex cover, and 𝑠𝑖=1si=1 means that vertex 𝑖i isn’t.
If there are multiple answers, then print any of them.
input
4 6 5 1 3 2 4 3 4 3 5 4 6 4 6 1 2 2 3 3 4 1 4 1 3 2 4 8 11 1 3 2 4 3 5 4 6 5 7 6 8 1 2 3 4 5 6 7 8 7 2 4 5 1 2 2 3 3 4 1 3 2 4
Lenient Vertex Cover solution codeforces
output
YES 001100 NO YES 01100110 YES 0110
input
Copy
Lenient Vertex Cover solution codeforces
1 10 15 9 4 3 4 6 4 1 2 8 2 8 3 7 2 9 5 7 8 5 10 1 4 2 10 5 3 5 7 2 9
output
YES 0101100100
input
Copy
Lenient Vertex Cover solution codeforces
1 10 19 7 9 5 3 3 4 1 6 9 4 1 4 10 5 7 1 9 2 8 3 7 3 10 9 2 10 9 8 3 2 1 5 10 7 9 5 1 2
output
YES 1010000011
Lenient Vertex Cover solution codeforces
Here are the graphs from the first example. The vertices in the lenient vertex covers are marked red.
