Moment of Bloom (Codeforces 1583E)
Tags: Greedy, graph matchings

She does her utmost to flawlessly carry out a person's last rites and preserve the world's balance of yin and yang.Hu Tao, being the little prankster she is, has tried to scare you with this graph problem! You are given a connected undirected graph of $$$n$$$ nodes with $$$m$$$ edges. You also have $$$q$$$ queries. Each query consists of two nodes $$$a$$$ and $$$b$$$.Initially, all edges in the graph have a weight of $$$0$$$. For each query, you must choose a simple path starting from $$$a$$$ and ending at $$$b$$$. Then you add $$$1$$$ to every edge along this path. Determine if it's possible, after processing all $$$q$$$ queries, for all edges in this graph to have an even weight. If so, output the choice of paths for each query. If it is not possible, determine the smallest number of extra queries you could add to make it possible. It can be shown that this number will not exceed $$$10^{18}$$$ under the given constraints.A simple path is defined as any path that does not visit a node more than once.An edge is said to have an even weight if its value is divisible by $$$2$$$.

Input: The first line contains two integers $$$n$$$ and $$$m$$$ ($$$2 \leq n \leq 3 \cdot 10^5$$$, $$$n-1 \leq m \leq \min{\left(\frac{n(n-1)}{2}, 3 \cdot 10^5\right)}$$$).Each of the next $$$m$$$ lines contains two integers $$$x$$$ and $$$y$$$ ($$$1 \leq x, y \leq n$$$, $$$x\neq y$$$) indicating an undirected edge between node $$$x$$$ and $$$y$$$. The input will not contain self-loops or duplicate edges, and the provided graph will be connected.The next line contains a single integer $$$q$$$ ($$$1 \leq q \leq 3 \cdot 10^5$$$).Each of the next $$$q$$$ lines contains two integers $$$a$$$ and $$$b$$$ ($$$1 \leq a, b \leq n, a \neq b$$$), the description of each query.It is guaranteed that $$$nq \leq 3 \cdot 10^5$$$.

Output: If it is possible to force all edge weights to be even, print "YES" on the first line, followed by $$$2q$$$ lines indicating the choice of path for each query in the same order the queries are given. For each query, the first line should contain a single integer $$$x$$$: the number of nodes in the chosen path. The next line should then contain $$$x$$$ spaced separated integers $$$p_i$$$ indicating the path you take ($$$p_1 = a, p_x = b$$$ and all numbers should fall between $$$1$$$ and $$$n$$$). This path cannot contain duplicate nodes and must be a valid simple path in the graph.If it is impossible to force all edge weights to be even, print "NO" on the first line and the minimum number of added queries on the second line.

Note: Here is what the queries look like for the first test case (red corresponds to the 1st query, blue 2nd query, and green 3rd query):    Notice that every edge in the graph is part of either $$$0$$$ or $$$2$$$ colored query edges.The graph in the second test case looks like this:    There does not exist an assignment of paths that will force all edges to have even weights with the given queries. One must add at least $$$2$$$ new queries to obtain a set of queries that can satisfy the condition.

Sample Inputs:
6 7
2 1
2 3
3 5
1 4
6 1
5 6
4 5
3
1 4
5 1
4 5

5 7
4 3
4 5
2 1
1 4
1 3
3 5
3 2
4
4 2
3 5
5 1
4 5

Sample Outputs:
YES
2
1 4
4
5 3 2 1
5
4 1 2 3 5

NO
2

Solution (Python):
import sys
input = sys.stdin.readline

def unionfind(u):
    v = u
    while u != parent[u]:
        u = parent[u]
    while v != u:
        w = parent[v]
        parent[v] = u
        v = parent[w]
    return u

def path(u, v):
    s = [u]
    pre = [-1] * (n + 1)
    pre[u] = u
    while s:
        x = s.pop()
        for y in g[x]:
            if pre[y] >= 0:
                continue
            pre[y] = x
            s.append(y)
    ans = [v]
    while ans[-1] != u:
        ans.append(pre[ans[-1]])
    return ans[::-1]
(n, m) = map(int, input().split())
g = [[] for i in range(n + 1)]
parent = [i for i in range(n + 1)]
for i in range(m):
    (u, v) = map(int, input().split())
    (root1, root2) = (unionfind(u), unionfind(v))
    if root1 == root2:
        continue
    parent[max(root1, root2)] = min(root1, root2)
    g[u].append(v)
    g[v].append(u)
l = len(g)
q = int(input())
query = []
d = {}
for i in range(q):
    (a, b) = map(int, input().split())
    query.append([a, b])
    if a in d:
        del d[a]
    else:
        d[a] = 1
    if b in d:
        del d[b]
    else:
        d[b] = 1
if len(d) > 0:
    print('NO')
    print(len(d) // 2)
else:
    print('YES')
    for i in range(q):
        ans = path(query[i][0], query[i][1])
        print(len(ans))
        print(' '.join(map(str, ans)))

Solution (Python):
(standard_input, packages, output_together) = (1, 1, 1)
(dfs, hashing, read_from_file) = (0, 0, 0)
de = 1
if 1:
    if standard_input:
        import io, os, sys
        input = lambda : sys.stdin.readline().strip()
        inf = float('inf')

        def I():
            return input()

        def II():
            return int(input())

        def MII():
            return map(int, input().split())

        def LI():
            return list(input().split())

        def LII():
            return list(map(int, input().split()))

        def LFI():
            return list(map(float, input().split()))

        def GMI():
            return map(lambda x: int(x) - 1, input().split())

        def LGMI():
            return list(map(lambda x: int(x) - 1, input().split()))
    if packages:
        from io import BytesIO, IOBase
        import math
        import random
        import os
        import bisect
        import typing
        from collections import Counter, defaultdict, deque
        from copy import deepcopy
        from functools import cmp_to_key, lru_cache, reduce
        from heapq import merge, heapify, heappop, heappush, heappushpop, nlargest, nsmallest
        from itertools import accumulate, combinations, permutations, count, product
        from operator import add, iand, ior, itemgetter, mul, xor
        from string import ascii_lowercase, ascii_uppercase, ascii_letters
        from typing import *
        BUFSIZE = 4096
    if output_together:

        class FastIO(IOBase):
            newlines = 0

            def __init__(self, file):
                self._fd = file.fileno()
                self.buffer = BytesIO()
                self.writable = 'x' in file.mode or 'r' not in file.mode
                self.write = self.buffer.write if self.writable else None

            def read(self):
                while True:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    if not b:
                        break
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines = 0
                return self.buffer.read()

            def readline(self):
                while self.newlines == 0:
                    b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
                    self.newlines = b.count(b'\n') + (not b)
                    ptr = self.buffer.tell()
                    (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
                self.newlines -= 1
                return self.buffer.readline()

            def flush(self):
                if self.writable:
                    os.write(self._fd, self.buffer.getvalue())
                    (self.buffer.truncate(0), self.buffer.seek(0))

        class IOWrapper(IOBase):

            def __init__(self, file):
                self.buffer = FastIO(file)
                self.flush = self.buffer.flush
                self.writable = self.buffer.writable
                self.write = lambda s: self.buffer.write(s.encode('ascii'))
                self.read = lambda : self.buffer.read().decode('ascii')
                self.readline = lambda : self.buffer.readline().decode('ascii')
        sys.stdout = IOWrapper(sys.stdout)
    if dfs:
        from types import GeneratorType

        def bootstrap(f, stack=[]):

            def wrappedfunc(*args, **kwargs):
                if stack:
                    return f(*args, **kwargs)
                else:
                    to = f(*args, **kwargs)
                    while True:
                        if type(to) is GeneratorType:
                            stack.append(to)
                            to = next(to)
                        else:
                            stack.pop()
                            if not stack:
                                break
                            to = stack[-1].send(to)
                    return to
            return wrappedfunc
    if hashing:
        RANDOM = random.getrandbits(20)

        class Wrapper(int):

            def __init__(self, x):
                int.__init__(x)

            def __hash__(self):
                return super(Wrapper, self).__hash__() ^ RANDOM
    if read_from_file:
        file = open('input.txt', 'r').readline().strip()[1:-1]
        fin = open(file, 'r')
        input = lambda : fin.readline().strip()
        output_file = open('output.txt', 'w')

        def fprint(*args, **kwargs):
            print(*args, **kwargs, file=output_file)
    if de:

        def debug(*args, **kwargs):
            print('\x1b[92m', end='')
            print(*args, **kwargs)
            print('\x1b[0m', end='')

class UnionFind:

    def __init__(self, n):
        self.parent = list(range(n))

    def find(self, a):
        a = self.parent[a]
        acopy = a
        while a != self.parent[a]:
            a = self.parent[a]
        while acopy != a:
            (self.parent[acopy], acopy) = (a, self.parent[acopy])
        return a

    def merge(self, a, b):
        (pa, pb) = (self.find(a), self.find(b))
        if pa == pb:
            return False
        self.parent[pb] = pa
        return True

def main():
    (n, m) = MII()
    union = UnionFind(n)
    path = [[] for _ in range(n)]
    for _ in range(m):
        (u, v) = GMI()
        if union.merge(u, v):
            path[u].append(v)
            path[v].append(u)
    queries = []
    degs = [0] * n
    q = II()
    for _ in range(q):
        (u, v) = GMI()
        queries.append((u, v))
        degs[u] ^= 1
        degs[v] ^= 1
    tot = sum(degs)
    if tot:
        print('NO')
        print(tot // 2)
    else:
        print('YES')
        for (u, v) in queries:
            stack = [v]
            parent = [-1] * n
            while stack:
                x = stack.pop()
                for y in path[x]:
                    if y != parent[x]:
                        parent[y] = x
                        stack.append(y)
            res = [u]
            while res[-1] != v:
                res.append(parent[res[-1]])
            print(len(res))
            print(*(x + 1 for x in res))
    return
t = 1
for _ in range(t):
    main()

Solution (Python):
import sys
input = sys.stdin.buffer.readline

def process(n, G, Q):
    g = [[] for i in range(n + 1)]
    m = len(G)
    for i in range(m):
        (x, y) = G[i]
        g[x].append(y)
        g[y].append(x)
    parent = [None for i in range(n + 1)]
    start = [1]
    parent[1] = -1
    while True:
        next_s = []
        for x in start:
            for y in g[x]:
                if parent[y] is None:
                    parent[y] = x
                    next_s.append(y)
        if len(next_s) == 0:
            break
        start = next_s
    counts = [0 for i in range(n + 1)]
    q = len(Q)
    answer = ['NO', None, []]
    for i in range(q):
        (a, b) = Q[i]
        counts[a] += 1
        counts[b] += 1
        path1 = [a]
        path2 = [b]
        while path1[-1] != 1:
            a2 = path1[-1]
            path1.append(parent[a2])
        while path2[-1] != 1:
            b2 = path2[-1]
            path2.append(parent[b2])
        while len(path2) > 0 and len(path1) > 0 and (path1[-1] == path2[-1]):
            c = path1.pop()
            path2.pop()
        path1.append(c)
        while len(path2) > 0:
            c = path2.pop()
            path1.append(c)
        answer[2].append(path1)
    odd_count = 0
    for i in range(1, n + 1):
        if counts[i] % 2 == 1:
            odd_count += 1
    answer[1] = odd_count // 2
    if odd_count == 0:
        answer[0] = 'YES'
    return answer
(n, m) = [int(x) for x in input().split()]
G = []
for i in range(m):
    (x, y) = [int(x) for x in input().split()]
    G.append([x, y])
q = int(input())
Q = []
for i in range(q):
    (a, b) = [int(x) for x in input().split()]
    Q.append([a, b])
(a1, a2, a3) = process(n, G, Q)
print(a1)
if a1 == 'YES':
    for row in a3:
        print(len(row))
        sys.stdout.write(' '.join(map(str, row)) + '\n')
else:
    print(a2)