"""
Find maximum cardinality matching in general undirected graph
# D. Eppstein, UC Irvine, 6 Sep 2003
https://github.com/ActiveState/code/tree/master/recipes/Python/221251_Maximum_cardinality_matching_general
"""

if "True" not in globals():
    globals()["True"] = not None
    globals()["False"] = not True


class UnionFind:
    """Union Find data structure. Modified from Josiah Carlson's code,
http://aspn.activestate.com/ASPN/Cookbook/Python/Recipe/215912
to allow arbitrarily many arguments in unions, use [] syntax for finds,
and eliminate unnecessary code."""

    def __init__(self):
        self.weights = {}
        self.parents = {}

    def __getitem__(self, object):
        """Find the root of the set that an object is in.
Object must be hashable; previously unknown objects become new singleton sets."""

        # check for previously unknown object
        if object not in self.parents:
            self.parents[object] = object
            self.weights[object] = 1
            return object

        # find path of objects leading to the root
        path = [object]
        root = self.parents[object]
        while root != path[-1]:
            path.append(root)
            root = self.parents[root]

        # compress the path and return
        for ancestor in path:
            self.parents[ancestor] = root
        return root

    def union(self, *objects):
        """Find the sets containing the given objects and merge them all."""
        roots = [self[x] for x in objects]
        heaviest = max([(self.weights[r], r) for r in roots])[1]
        for r in roots:
            if r != heaviest:
                self.weights[heaviest] += self.weights[r]
                self.parents[r] = heaviest


def matching(G, initial_matching=None):
    """Find a maximum cardinality matching in a graph G.
G is represented in modified GvR form: iter(G) lists its vertices;
iter(G[v]) lists the neighbors of v; w in G[v] tests adjacency.
The output is a dictionary mapping vertices to their matches;
unmatched vertices are omitted from the dictionary.

We use Edmonds' blossom-contraction algorithm, as described e.g.
in Galil's 1986 Computing Surveys paper."""

    # Copy initial matching so we can use it nondestructively
    if initial_matching is None:
        initial_matching = {}
    a_matching = {}
    for x in initial_matching:
        a_matching[x] = initial_matching[x]

    # Form greedy matching to avoid some iterations of augmentation
    for v in G:
        if v not in a_matching:
            for w in G[v]:
                if w not in a_matching:
                    a_matching[v] = w
                    a_matching[w] = v
                    break

    def augment():
        """Search for a single augmenting path.
Return value is true if the matching size was increased, false otherwise."""

        # Data structures for augmenting path search:
        #
        # leader: union-find structure; the leader of a blossom is one
        # of its vertices (not necessarily topmost), and leader[v] always
        # points to the leader of the largest blossom containing v
        #
        # S: dictionary of leader at even levels of the structure tree.
        # Dictionary keys are names of leader (as returned by the union-find
        # data structure) and values are the structure tree parent of the blossom
        # (a T-node, or the top vertex if the blossom is a root of a structure tree).
        #
        # T: dictionary of vertices at odd levels of the structure tree.
        # Dictionary keys are the vertices; T[x] is a vertex with an unmatched
        # edge to x.  To find the parent in the structure tree, use leader[T[x]].
        #
        # unexplored: collection of unexplored vertices within leader of S
        #
        # base: if x was originally a T-vertex, but becomes part of a blossom,
        # base[t] will be the pair (v,w) at the base of the blossom, where v and t
        # are on the same side of the blossom and w is on the other side.

        leader = UnionFind()
        S = {}
        T = {}
        unexplored = []
        base = {}

        # Subroutines for augmenting path search.
        # Many of these are called only from one place, but are split out
        # as subroutines to improve modularization and readability.

        def blossom(v, w, a):
            """Create a new blossom from edge v-w with common ancestor a."""

            def find_side(v, w):
                path = [leader[v]]
                b = (v, w)  # new base for all T nodes found on the path
                while path[-1] != a:
                    tnode = S[path[-1]]
                    path.append(tnode)
                    base[tnode] = b
                    unexplored.append(tnode)
                    path.append(leader[T[tnode]])
                return path

            a = leader[a]  # sanity check
            path1, path2 = find_side(v, w), find_side(w, v)
            leader.union(*path1)
            leader.union(*path2)
            S[leader[a]] = S[a]  # update structure tree

        topless = object()  # should be unequal to any graph vertex

        def alternating_path(start, goal=topless):
            """Return sequence of vertices on alternating path from start to goal.
Goal must be a T node along the path from the start to the root of the structure tree.
If goal is omitted, we find an alternating path to the structure tree root."""
            path = []
            while 1:
                while start in T:
                    v, w = base[start]
                    vs = alternating_path(v, start)
                    vs.reverse()
                    path += vs
                    start = w
                path.append(start)
                if start not in a_matching:
                    return path  # reached top of structure tree, done!
                tnode = a_matching[start]
                path.append(tnode)
                if tnode == goal:
                    return path  # finished recursive subpath
                start = T[tnode]

        def pairs(L):
            """Utility to partition list into pairs of items.
If list has odd length, the final pair is omitted silently."""
            i = 0
            while i < len(L) - 1:
                yield L[i], L[i + 1]
                i += 2

        def alternate(v):
            """Make v unmatched by alternating the path to the root of its structure tree."""
            path = alternating_path(v)
            path.reverse()
            for x, y in pairs(path):
                a_matching[x] = y
                a_matching[y] = x

        def add_match(v, w):
            """Here with an S-S edge vw connecting vertices in different structure trees.
Find the corresponding augmenting path and use it to augment the matching."""
            alternate(v)
            alternate(w)
            a_matching[v] = w
            a_matching[w] = v

        def ss(v, w):
            """Handle detection of an S-S edge in augmenting path search.
Like augment(), returns true iff the matching size was increased."""

            if leader[v] == leader[w]:
                return False  # self-loop within blossom, ignore

            # parallel search up two branches of structure tree
            # until we find a common ancestor of v and w
            path1, head1 = {}, v
            path2, head2 = {}, w

            def step(path, head):
                head = leader[head]
                parent = leader[S[head]]
                if parent == head:
                    return head  # found root of structure tree
                path[head] = parent
                path[parent] = leader[T[parent]]
                return path[parent]

            while 1:
                head1 = step(path1, head1)
                head2 = step(path2, head2)

                if head1 == head2:
                    blossom(v, w, head1)
                    return False

                if leader[S[head1]] == head1 and leader[S[head2]] == head2:
                    add_match(v, w)
                    return True

                if head1 in path2:
                    blossom(v, w, head1)
                    return False

                if head2 in path1:
                    blossom(v, w, head2)
                    return False

                    # Start of main augmenting path search code.

        for v in G:
            if v not in a_matching:
                S[v] = v
                unexplored.append(v)

        current = 0  # index into unexplored, in FIFO order so we get short paths
        while current < len(unexplored):
            v = unexplored[current]
            current += 1

            for w in G[v]:
                if leader[w] in S:  # S-S edge: blossom or augmenting path
                    if ss(v, w):
                        return True

                elif w not in T:  # previously unexplored node, add as T-node
                    T[w] = v
                    u = a_matching[w]
                    if leader[u] not in S:
                        S[u] = w  # and add its match as an S-node
                        unexplored.append(u)

        return False  # ran out of graph without finding an augmenting path

    # augment the matching until it is maximum
    while augment():
        pass

    return a_matching
