[Solution] Lenient Vertex Cover solution codeforces

Lenient Vertex Cover solution codeforces – You are given a simple connected undirected graph, consisting of 𝑛n vertices and 𝑚m edges. The vertices are numbered from 11 to 𝑛n.

[Solution] 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.

Input

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.

[Solution] 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.

Examples
input

Copy
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

[Solution] Lenient Vertex Cover solution codeforces

output

Copy
YES
001100
NO
YES
01100110
YES
0110
input

Copy
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

Copy
YES
0101100100
input

Copy
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

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

Lenient Vertex Cover solution codeforces

 

For Solution

Click here

Leave a Comment