Lenient Vertex Cover
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.
Here are the graphs from the first example. The vertices in the lenient vertex covers are marked red.   
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$$$.
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.
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def get_root(s):
    v = []
    while not s == root[s]:
        v.append(s)
        s = root[s]
    for i in v:
        root[i] = s
    return s

def unite(s, t):
    (rs, rt) = (get_root(s), get_root(t))
    if not rs ^ rt:
        return
    if rank[s] == rank[t]:
        rank[rs] += 1
    if rank[s] >= rank[t]:
        root[rt] = rs
        size[rs] += size[rt]
    else:
        root[rs] = rt
        size[rt] += size[rs]
    return

def same(s, t):
    return True if get_root(s) == get_root(t) else False

def get_size(s):
    return size[get_root(s)]

def make_graph(n, m, x):
    s = [0] * (n + 3)
    for i in range(m):
        (u, v) = (x[2 * i], x[2 * i + 1])
        s[u + 2] += 1
        s[v + 2] += 1
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    G = [0] * (2 * m)
    for i in range(2 * m):
        j = x[i] + 1
        G[s[j]] = x[i ^ 1]
        s[j] += 1
    return (G, s)

def bfs(s):
    q = []
    dist = [inf] * (n + 1)
    for i in s:
        q.append(i)
        dist[i] = 0
    parent = [-1] * (n + 1)
    for k in range(n):
        i = q[k]
        di = dist[i]
        for v in range(s0[i], s0[i + 1]):
            j = G[v]
            if dist[j] == inf:
                q.append(j)
                dist[j] = di + 1
                parent[j] = i
    return (q, dist, parent)

def dfs(s):
    st = [s]
    now = list(s0)
    visit = [0] * (n + 1)
    visit[s] = 1
    u = [s]
    while st:
        i = st[-1]
        if u[-1] ^ i:
            u.append(i)
        if now[i] == s0[i + 1]:
            st.pop()
            continue
        j = G[now[i]]
        if not visit[j]:
            visit[j] = 1
            st.append(j)
        now[i] += 1
    return u

def get_min(s, t):
    s += l1
    t += l1
    ans = inf
    while s <= t:
        if s % 2:
            ans = min(ans, tree[s])
            s += 1
        s >>= 1
        if not t % 2:
            ans = min(ans, tree[t])
            t -= 1
        t >>= 1
    return ans
t = int(input())
ans = []
inf = pow(10, 15) + 1
for _ in range(t):
    (n, m) = map(int, input().split())
    root = [i for i in range(n + 1)]
    rank = [1 for _ in range(n + 1)]
    size = [1 for _ in range(n + 1)]
    (x, y) = ([], [])
    for _ in range(m):
        (u, v) = map(int, input().split())
        if not same(u, v):
            unite(u, v)
            x.append(u)
            x.append(v)
        else:
            y.append(u)
            y.append(v)
    (G, s0) = make_graph(n, n - 1, x)
    (p, dist, parent) = bfs([1])
    t0 = dfs(1)
    t1 = [-1] * (n + 1)
    t2 = [-1] * (n + 1)
    l = len(t0)
    for i in range(l):
        if t1[t0[i]] == -1:
            t1[t0[i]] = i
    for i in range(l - 1, -1, -1):
        if t2[t0[i]] == -1:
            t2[t0[i]] = i
    l1 = pow(2, l.bit_length())
    l2 = 2 * l1
    tree = [inf] * l2
    for i in range(l):
        j = t0[i]
        (tree[i + l1], t2[j]) = (dist[j] * (n + 1) + j, i)
    for i in range(l1 - 1, 0, -1):
        tree[i] = min(tree[2 * i], tree[2 * i + 1])
    dp = [0] * (n + 1)
    z = []
    for i in range(0, len(y), 2):
        (u, v) = (y[i], y[i + 1])
        if t1[u] > t1[v]:
            (u, v) = (v, u)
        w = get_min(t1[u], t2[v]) % (n + 1)
        d = -1
        if not (dist[u] + dist[v]) % 2:
            z.append(u)
            z.append(v)
            d = 1
        dp[u] += d
        dp[v] += d
        dp[w] -= 2 * d
    for i in p[::-1][:-1]:
        j = parent[i]
        dp[j] += dp[i]
    ma = max(dp[2:])
    ans0 = 'YES'
    if 2 * ma == len(z) and ma:
        i = dp[2:].index(ma) + 2
        (_, dist, _) = bfs([i, parent[i]])
    elif len(z) == 2:
        (_, dist, _) = bfs(z)
    elif z:
        ans0 = 'NO'
    ans.append(ans0)
    if ans0 == 'NO':
        continue
    ans1 = [dist[i] & 1 ^ 1 for i in range(1, n + 1)]
    ans.append(''.join(map(str, ans1)))
sys.stdout.write('\n'.join(ans))
import sys
input = lambda : sys.stdin.readline().rstrip()
out = []
DFS_IN = 0
DFS_OUT = 1

def solve():
    (n, m) = map(int, input().split())
    g = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(int, input().split())
        g[u - 1].append(v - 1)
        g[v - 1].append(u - 1)
    col = [-1] * n
    level = [0] * n
    dp_good = [0] * n
    dp_bad = [0] * n
    cnt = 0
    flip = 0
    stack = [(0, -1, DFS_IN)]
    while stack:
        (u, par, state) = stack.pop()
        if state == DFS_IN:
            if col[u] != -1:
                continue
            if par == -1:
                col[u] = 0
                level[u] = 1
            else:
                col[u] = 1 - col[par]
                level[u] = level[par] + 1
            stack.append((u, par, DFS_OUT))
            for v in g[u]:
                if col[v] == -1:
                    stack.append((v, u, DFS_IN))
                elif level[v] < level[u] - 1:
                    if col[v] == col[u]:
                        cnt += 1
                        flip = 1 - col[v]
                        dp_bad[u] += 1
                        dp_bad[v] -= 1
                    else:
                        dp_good[u] += 1
                        dp_good[v] -= 1
        else:
            dp_good[par] += dp_good[u]
            dp_bad[par] += dp_bad[u]

    def change_color(u):
        stack = [u]
        while stack:
            u = stack.pop()
            col[u] ^= 1
            for v in g[u]:
                if level[v] == level[u] + 1:
                    stack.append(v)
    if cnt == 1:
        if flip:
            col = [1 - c for c in col]
        out.append('YES')
        out.append(''.join(map(str, col)))
        return
    rmv = -1
    for i in range(n):
        if dp_bad[i] == cnt and dp_good[i] == 0:
            rmv = i
            break
    if rmv == -1:
        out.append('NO')
    else:
        if col[rmv] == 1:
            col = [1 - c for c in col]
        change_color(rmv)
        out.append('YES')
        out.append(''.join(map(str, col)))
for _ in range(int(input())):
    solve()
print('\n'.join(out))
input = __import__('sys').stdin.readline
DFS_IN = 0
DFS_OUT = 1

def solve():
    (n, m) = map(int, input().split())
    adj = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = map(lambda x: int(x) - 1, input().split())
        adj[u].append(v)
        adj[v].append(u)
    cnt_odd = 0
    dfs_in = [0] * n
    dfs_out = [0] * n
    depth = [0] * n + [-1]
    color = [-1] * n + [1]
    removed_back_edge = None
    dp = [[0] * 2 for _ in range(n + 1)]
    i = 0
    stack = [(0, -1, DFS_IN)]
    while len(stack) > 0:
        i += 1
        (u, par, state) = stack.pop()
        if state == DFS_IN:
            if color[u] != -1:
                continue
            dfs_in[u] = i
            color[u] = color[par] ^ 1
            depth[u] = depth[par] + 1
            stack.append((u, par, DFS_OUT))
            for v in adj[u]:
                if color[v] == -1:
                    stack.append((v, u, DFS_IN))
                elif depth[v] - depth[u] not in (-1, 1) and depth[u] > depth[v]:
                    if color[u] == color[v]:
                        if removed_back_edge is None:
                            removed_back_edge = (u, v)
                        else:
                            removed_back_edge = (n, n)
                    parity = color[u] ^ color[v] ^ 1
                    dp[u][parity] += 1
                    dp[v][parity] -= 1
                    cnt_odd += parity
        if state == DFS_OUT:
            dfs_out[u] = i
            dp[par][0] += dp[u][0]
            dp[par][1] += dp[u][1]
    color.pop()
    if removed_back_edge is None or removed_back_edge != (n, n):
        xor = 1 if removed_back_edge is not None and (color[removed_back_edge[0]], color[removed_back_edge[1]]) == (0, 0) else 0
        print('YES')
        print(''.join((str(x ^ xor) for x in color)))
        return
    invert_node = next((u for u in range(1, n) if dp[u][1] == cnt_odd and dp[u][0] == 0), None)
    if invert_node is None:
        print('NO')
        return
    xor = color[invert_node]
    xor_subtree = lambda u: dfs_in[invert_node] <= dfs_in[u] <= dfs_out[invert_node]
    print('YES')
    print(''.join((str(x ^ (1 if xor_subtree(u) else 0) ^ xor) for (u, x) in enumerate(color))))
for _ in range(int(input())):
    solve()