[Solution] Lenient Vertex Cover Codeforces Solution | Codeforces Problem Solution 2022

[Solution] Lenient Vertex Cover Codeforces Solution | Codeforces Problem Solution 2022

F. Lenient Vertex Cover

time limit per test

5 seconds

memory limit per test

512 megabytes

input

standard input

output

standard output

You are given a simple connected undirected graph, consisting of 𝑛$n$ vertices and 𝑚$m$ edges. The vertices are numbered from 1$1$ to 𝑛$n$.

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.

Solution Click Below:-  CLICK HERE

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≤𝑡≤104$1\le t\le {10}^4$) — the number of testcases.

The first line of each testcase contains two integers 𝑛$n$ and 𝑚$m$ (2≤𝑛≤106$2\le n\le {10}^6$; 𝑛−1≤𝑚≤min(106,𝑛⋅(𝑛−1)2)$n-1\le m\le min({10}^6,\frac{n\cdot (n-1)}{2})$) — the number of vertices and the number of edges of the graph.

Minimums and Maximums Codeforces Solution 

Robots Codeforces Solution 

Binary String Codeforces Solution

Dog Walking Codeforces Solution

Moving Chips Codeforces Solution

Lenient Vertex Cover Codeforces Solution 

Each of the next 𝑚$m$ lines contains two integers 𝑣$v$ and 𝑢$u$ (1≤𝑣,𝑢≤𝑛$1\le v,u\le n$; 𝑣≠𝑢$v\ne 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 106${10}^6$. The sum of 𝑚$m$ over all testcases doesn't exceed 106${10}^6$.

Output

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 𝑠𝑖=0$s_i=0$ means that vertex 𝑖$i$ is in the vertex cover, and 𝑠𝑖=1$s_i=1$ means that vertex 𝑖$i$ isn't.

If there are multiple answers, then print any of them.

Join Now for Solution:-