Lenient Vertex Cover
Contest: Educational Codeforces Round 128 (Rated for Div. 2)
Difficulty rating: 2600
Tags: dfs and similar, divide and conquer, dsu, graphs, trees

You are given a simple connected undirected graph, consisting of $$$n$$$ vertices and $$$m$$$ edges. The vertices are numbered from $$$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.

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 format:
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of testcases.

The first line of each testcase contains two integers $$$n$$$ and $$$m$$$ ($$$2 \le n \le 10^6$$$; $$$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.

Each of the next $$$m$$$ lines contains two integers $$$v$$$ and $$$u$$$ ($$$1 \le v, u \le n$$$; $$$v \neq 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 $$$10^6$$$. The sum of $$$m$$$ over all testcases doesn't exceed $$$10^6$$$.

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

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

Constraints:
Time limit: 5.0 s
Memory limit: 512.0 MB

Note:
Here are the graphs from the first example. The vertices in the lenient vertex covers are marked red.

Example 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

Example output:
YES
001100
NO
YES
01100110
YES
0110

Example input:
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

Example output:
YES
0101100100

Editorial:
Let's think about why we can't always make a perfect vertex cover — such a vertex cover that each edge has exactly one endpoint in it. Or why the answer can not exist at all.
Consider a bamboo. It's always possible to find a perfect vertex cover. Just choose every other vertex in it and account for parity.
Make a bamboo into a loop. Now you can see that an even length loop has a perfect vertex cover. An odd length doesn't.
That tells us that each odd length loop in a graph will have a bad edge on it. Odd length loops should instantly make you think about bipartite colorings.
So we can see that a bipartite graph always has a perfect vertex cover. Just choose one of the parts into a cover, and each edge will have exactly one endpoint in it. At the same time, a non-bipartite graph never has a perfect cover.
So our general goal is to remove (basically, mark as bad) at most one edge in such a way that the remaining graph is bipartite.
Consider a dfs tree of the graph, colored bipartitely. Every edge in the tree is good (has endpoints in different parts). Every edge outside the tree can be either good or bad. What happens to the tree if we remove an edge?
If we remove an edge outside the dfs tree, then nothing happens to it. So if there is no more than one bad edge outside the tree, then we found the answer. That was the easy part.
Now what happens if we remove an edge from the tree? The back edges from the subtree of the edge can force the subtree to either remain colored the same or flip all its colors. We don't really care if it remains the same, because we already took care of it in the first part. So let's pretend it always flips the colors.
Thus, all edges that go from the subtree upwards above the removed edge, have only one of their endpoints colors changed. Good edges turn bad, bad edges turn good.
All other edges don't change.
So you should choose such an edge to remove that all bad edges in the graph go from its subtree upwards above that edge and no good edges go from its subtree upwards above that edge.
That can be calculated with a dfs. Since all non-tree edges in the dfs tree are back edges, you can simply increment a counter on the bottom vertex, decrement the counter on the top vertex and collect sums from the bottom. The sum in the vertex will tell you the number of edges that start below or in the vertex and end above the vertex.
Do this for both kinds of edge and check the conditions for all vertices. Finally, choose such a part to be a vertex cover that the removed edge has both ends in it (if you choose the other part, that edge won't be covered at all).
The solution is linear, but the problem still requires a massive time and memory limit only because of recursion in the dfs.
Overall complexity: $$$O(n + m)$$$ per testcase.