# ===== BEGIN: /Suzlib/python/graph/BipartiteMatching.py =====
# competitive-verifier: TITLE 最大二部マッチング

from random import shuffle


class BipartiteMatching:
    """Kuhn 法を前処理に用いた Hopcroft--Karp 法。初回 solve の計算量は O((V + E) sqrt(V))。

    辺番号を維持するため、削除済み辺も内部に保持する。
    累積追加辺数を A とすると、辺情報の保持には O(A) の空間を使い、
    edges は O(A)、matching_edge_ids は solve 後に O(V + A)、
    CSR の再構築は O(V + A) 時間を要する。
    """

    def __init__(self, n_left: int, n_right: int) -> None:
        """左右の頂点数を設定し、辺のない二部グラフと空のマッチングを作る。"""
        assert 0 <= n_left
        assert 0 <= n_right
        self.n_left = n_left
        self.n_right = n_right
        self.g: list[list[int]] | None = None
        self.mate_left = [-1] * n_left
        self.mate_right = [-1] * n_right
        self.size = 0
        self._edge_shift = max(1, (n_right - 1).bit_length())
        self._edge_mask = (1 << self._edge_shift) - 1
        self._edges: list[int] = []
        self._removed_edges: set[int] = set()
        self._start: list[int] = []
        self._to: list[int] = []
        self._csr_built = False
        self._solved = False

    def add_edge(self, left: int, right: int) -> int:
        """solve 前に左頂点 left と右頂点 right を結ぶ辺を追加し、辺番号を返す。"""
        if self._solved:
            raise RuntimeError("call add_edge() before solve()")
        assert 0 <= left < self.n_left
        assert 0 <= right < self.n_right
        edge_id = len(self._edges)
        self._edges.append((left << self._edge_shift) | right)
        return edge_id

    def edge_count(self) -> int:
        """これまでに発行した辺番号の個数を返す。削除済み辺も数える。"""
        return len(self._edges)

    def edges(self) -> list[tuple[int, int, int]]:
        """現在存在する辺を (edge_id, left, right) で返す。"""
        shift = self._edge_shift
        mask = self._edge_mask
        removed = self._removed_edges
        return [
            (edge_id, edge >> shift, edge & mask)
            for edge_id, edge in enumerate(self._edges)
            if edge_id not in removed
        ]

    def _build_csr(self) -> None:
        """現在の辺を左頂点ごとの CSR にまとめる。再構築は累積追加辺数 A に対し O(V + A)。"""
        if self._csr_built:
            return

        removed = self._removed_edges
        if removed:
            edges = [
                edge
                for edge_id, edge in enumerate(self._edges)
                if edge_id not in removed
            ]
        else:
            edges = self._edges.copy()
        shuffle(edges)

        shift = self._edge_shift
        mask = self._edge_mask
        start = [0] * (self.n_left + 1)
        for edge in edges:
            start[(edge >> shift) + 1] += 1
        for left in range(self.n_left):
            start[left + 1] += start[left]

        to = [0] * len(edges)
        pos = start[:-1]
        for edge in edges:
            left = edge >> shift
            to[pos[left]] = edge & mask
            pos[left] += 1

        self._start = start
        self._to = to
        self._csr_built = True

    def _materialize_adjacency(self) -> None:
        """更新操作のため、必要になった時だけ可変な隣接リストを生成する。"""
        if self.g is not None:
            return
        self._build_csr()
        start = self._start
        to = self._to
        self.g = [
            to[start[left]:start[left + 1]]
            for left in range(self.n_left)
        ]

    def _degree_greedy(self) -> int:
        """左右両側の CSR を用いて低次数頂点を優先した初期マッチングを構成する。"""
        start = self._start
        to = self._to
        mate_left = self.mate_left
        mate_right = self.mate_right
        n_left = self.n_left
        n_right = self.n_right

        rstart = [0] * (n_right + 1)
        for right in to:
            rstart[right + 1] += 1
        for right in range(n_right):
            rstart[right + 1] += rstart[right]

        rto = [0] * len(to)
        pos = rstart[:-1]
        for left in range(n_left):
            for i in range(start[left], start[left + 1]):
                right = to[i]
                rto[pos[right]] = left
                pos[right] += 1

        degree_left = [start[left + 1] - start[left] for left in range(n_left)]
        degree_right = [rstart[right + 1] - rstart[right] for right in range(n_right)]

        leaves = [left for left in range(n_left) if degree_left[left] == 1]
        leaves += [n_left + right for right in range(n_right) if degree_right[right] == 1]
        twos = [left for left in range(n_left) if degree_left[left] == 2]
        twos += [n_left + right for right in range(n_right) if degree_right[right] == 2]

        added = 0
        scan = 0
        m = len(to)
        while True:
            while leaves:
                v = leaves[-1]
                degree = degree_left[v] if v < n_left else degree_right[v - n_left]
                if degree == 1:
                    break
                leaves.pop()

            if leaves:
                v = leaves.pop()
                if v < n_left:
                    left = v
                    right = -1
                    for i in range(start[left], start[left + 1]):
                        w = to[i]
                        if degree_right[w]:
                            right = w
                            break
                else:
                    right = v - n_left
                    left = -1
                    for i in range(rstart[right], rstart[right + 1]):
                        w = rto[i]
                        if degree_left[w]:
                            left = w
                            break
            else:
                while scan < n_left and degree_left[scan] == 0:
                    scan += 1
                if scan == n_left:
                    break

                while twos:
                    v = twos[-1]
                    degree = degree_left[v] if v < n_left else degree_right[v - n_left]
                    if degree == 2:
                        break
                    twos.pop()
                v = twos.pop() if twos else scan

                if v < n_left:
                    left = v
                    right = -1
                    best = m + 1
                    for i in range(start[left], start[left + 1]):
                        w = to[i]
                        degree = degree_right[w]
                        if 0 < degree < best:
                            right = w
                            best = degree
                else:
                    right = v - n_left
                    left = -1
                    best = m + 1
                    for i in range(rstart[right], rstart[right + 1]):
                        w = rto[i]
                        degree = degree_left[w]
                        if 0 < degree < best:
                            left = w
                            best = degree

            if left == -1 or right == -1:
                continue

            mate_left[left] = right
            mate_right[right] = left
            added += 1
            degree_left[left] = 0
            degree_right[right] = 0

            for i in range(start[left], start[left + 1]):
                w = to[i]
                if degree_right[w]:
                    degree_right[w] -= 1
                    if degree_right[w] == 1:
                        leaves.append(n_left + w)
                    elif degree_right[w] == 2:
                        twos.append(n_left + w)
            for i in range(rstart[right], rstart[right + 1]):
                w = rto[i]
                if degree_left[w]:
                    degree_left[w] -= 1
                    if degree_left[w] == 1:
                        leaves.append(w)
                    elif degree_left[w] == 2:
                        twos.append(w)

        return added

    def solve(self) -> int:
        """現在のグラフの最大マッチング数を返す。"""
        if self._solved:
            return self.size

        self._build_csr()
        start = self._start
        to = self._to
        mate_left = self.mate_left
        mate_right = self.mate_right

        if self.size == 0:
            self.size = self._degree_greedy()

            if self.size == 0:
                self._solved = True
                return 0
            if self.size == min(self.n_left, self.n_right):
                self._solved = True
                return self.size

        parent = [-1] * self.n_left
        root = [-1] * self.n_left
        queue = [0] * self.n_left

        def kuhn_phase() -> int:
            """全未マッチ左頂点から交互森を伸ばし、増大路を貪欲に反転する。"""
            q_tail = 0

            for left in range(self.n_left):
                parent[left] = -1
                if mate_left[left] == -1:
                    parent[left] = -2
                    root[left] = left
                    queue[q_tail] = left
                    q_tail += 1

            added = 0
            q_front = 0
            while q_front < q_tail:
                left = queue[q_front]
                q_front += 1

                if mate_left[root[left]] != -1:
                    continue

                matched_right = mate_left[left]
                for i in range(start[left], start[left + 1]):
                    right = to[i]
                    if right == matched_right:
                        continue
                    next_left = mate_right[right]

                    if next_left == -1:
                        while left >= 0:
                            mate_right[right] = left
                            right, mate_left[left] = mate_left[left], right
                            left = parent[left]
                        added += 1
                        break

                    if parent[next_left] == -1:
                        parent[next_left] = left
                        root[next_left] = root[left]
                        queue[q_tail] = next_left
                        q_tail += 1

            return added

        for _ in range(128):
            added = kuhn_phase()
            self.size += added
            if added == 0 or self.size == min(self.n_left, self.n_right):
                self._solved = True
                return self.size

        del parent, root, queue
        inf = self.n_left + 1
        dist = [inf] * self.n_left
        current_edge: list[int] = []

        def bfs() -> int:
            """未マッチ左頂点から BFS し、最短増大路の長さを返す。"""
            queue: list[int] = []
            for left in range(self.n_left):
                if mate_left[left] == -1:
                    dist[left] = 0
                    queue.append(left)
                else:
                    dist[left] = inf

            q_front = 0
            while q_front < len(queue):
                left = queue[q_front]
                q_front += 1
                next_dist = dist[left] + 1
                for i in range(start[left], start[left + 1]):
                    right = to[i]
                    next_left = mate_right[right]
                    if next_left == -1:
                        return next_dist
                    if dist[next_left] == inf:
                        dist[next_left] = next_dist
                        queue.append(next_left)
            return inf

        def dfs(start_left: int, shortest: int) -> bool:
            """BFS 層に沿って最短増大路を1本探し、見つかれば反転する。"""
            left = start_left
            left_stack: list[int] = []
            while True:
                i = current_edge[left]
                end = start[left + 1]
                target = dist[left] + 1

                while i < end:
                    right = to[i]
                    i += 1
                    next_left = mate_right[right]

                    if next_left == -1:
                        if target != shortest:
                            continue
                        current_edge[left] = i
                        while True:
                            mate_right[right] = left
                            right, mate_left[left] = mate_left[left], right
                            if right == -1:
                                return True
                            left = left_stack.pop()

                    if dist[next_left] == target:
                        current_edge[left] = i
                        left_stack.append(left)
                        left = next_left
                        break
                else:
                    current_edge[left] = i
                    dist[left] = inf
                    if not left_stack:
                        return False
                    left = left_stack.pop()

        while True:
            shortest = bfs()
            if shortest == inf:
                break
            current_edge = start[:-1]
            for left in range(self.n_left):
                if mate_left[left] == -1 and dfs(left, shortest):
                    self.size += 1

        self._solved = True
        return self.size

    def _augment_once(self) -> bool:
        """全ての未マッチ左頂点から交互 BFS を1回だけ行い、増大路を1本だけ反転する。"""
        self._materialize_adjacency()
        assert self.g is not None
        g = self.g
        mate_left = self.mate_left
        mate_right = self.mate_right

        queue: list[int] = []
        parent = [-1] * self.n_left
        seen = [False] * self.n_left
        for left in range(self.n_left):
            if mate_left[left] == -1:
                seen[left] = True
                queue.append(left)

        q_front = 0
        while q_front < len(queue):
            left = queue[q_front]
            q_front += 1
            matched_right = mate_left[left]
            for right in g[left]:
                if right == matched_right:
                    continue
                next_left = mate_right[right]
                if next_left == -1:
                    while right != -1:
                        mate_right[right] = left
                        right, mate_left[left] = mate_left[left], right
                        left = parent[left]
                    self.size += 1
                    return True
                if not seen[next_left]:
                    seen[next_left] = True
                    parent[next_left] = left
                    queue.append(next_left)
        return False

    def increment_edge(self, left: int, right: int) -> bool:
        """最大マッチング構築後に辺を1本追加し、サイズが増えたかを返す。"""
        if not self._solved:
            raise RuntimeError("call solve() before increment_edge()")
        assert 0 <= left < self.n_left
        assert 0 <= right < self.n_right
        self._materialize_adjacency()
        assert self.g is not None
        self._edges.append((left << self._edge_shift) | right)
        self.g[left].append(right)
        self._csr_built = False

        if self.size == min(self.n_left, self.n_right):
            return False
        if self.mate_left[left] == -1 and self.mate_right[right] == -1:
            self.mate_left[left] = right
            self.mate_right[right] = left
            self.size += 1
            return True
        return self._augment_once()

    def increment_edges_from_left(self, left: int, rights: list[int]) -> bool:
        """最大マッチング構築後に一つの左頂点から複数辺を追加し、サイズが増えたかを返す。"""
        if not self._solved:
            raise RuntimeError("call solve() before increment_edges_from_left()")
        assert 0 <= left < self.n_left
        for right in rights:
            assert 0 <= right < self.n_right
        self._materialize_adjacency()
        assert self.g is not None
        base = left << self._edge_shift
        self._edges.extend(base | right for right in rights)
        self.g[left].extend(rights)
        self._csr_built = False

        if self.size == min(self.n_left, self.n_right):
            return False
        if self.mate_left[left] == -1:
            for right in rights:
                if self.mate_right[right] == -1:
                    self.mate_left[left] = right
                    self.mate_right[right] = left
                    self.size += 1
                    return True
        return self._augment_once()

    def increment_edges_from_right(self, right: int, lefts: list[int]) -> bool:
        """最大マッチング構築後に一つの右頂点へ複数辺を追加し、サイズが増えたかを返す。"""
        if not self._solved:
            raise RuntimeError("call solve() before increment_edges_from_right()")
        assert 0 <= right < self.n_right
        for left in lefts:
            assert 0 <= left < self.n_left
        self._materialize_adjacency()
        assert self.g is not None
        for left in lefts:
            self._edges.append((left << self._edge_shift) | right)
            self.g[left].append(right)
        self._csr_built = False

        if self.size == min(self.n_left, self.n_right):
            return False
        if self.mate_right[right] == -1:
            for left in lefts:
                if self.mate_left[left] == -1:
                    self.mate_left[left] = right
                    self.mate_right[right] = left
                    self.size += 1
                    return True
        return self._augment_once()

    def remove_edge(self, edge_id: int) -> bool:
        """最大マッチング構築後に辺番号 edge_id の辺を削除し、最大マッチング数が減ったかを返す。"""
        if not self._solved:
            raise RuntimeError("call solve() before remove_edge()")
        assert 0 <= edge_id < len(self._edges)
        if edge_id in self._removed_edges:
            raise ValueError("edge is already removed")

        self._materialize_adjacency()
        assert self.g is not None
        edge = self._edges[edge_id]
        left = edge >> self._edge_shift
        right = edge & self._edge_mask
        self._removed_edges.add(edge_id)
        self.g[left].remove(right)
        self._csr_built = False

        if self.mate_left[left] != right:
            return False

        self.mate_left[left] = -1
        self.mate_right[right] = -1
        self.size -= 1
        return not self._augment_once()

    def matching_edges(self) -> list[tuple[int, int]]:
        """最大マッチングに使われる (左頂点, 右頂点) を返す。"""
        self.solve()
        return [
            (left, right)
            for left, right in enumerate(self.mate_left)
            if right != -1
        ]

    def matching_edge_ids(self) -> list[int]:
        """最大マッチングに対応する入力辺番号を返す。多重辺では最初の辺を選ぶ。"""
        self.solve()
        edge_for_left = [-1] * self.n_left
        shift = self._edge_shift
        mask = self._edge_mask
        removed = self._removed_edges
        for edge_id, edge in enumerate(self._edges):
            if edge_id in removed:
                continue
            left = edge >> shift
            if edge_for_left[left] != -1:
                continue
            right = edge & mask
            if self.mate_left[left] == right:
                edge_for_left[left] = edge_id
        return [edge_id for edge_id in edge_for_left if edge_id != -1]

    def mates(self) -> tuple[list[int], list[int]]:
        """左から右、右から左への対応をそれぞれ返す。未対応は -1。"""
        self.solve()
        return self.mate_left.copy(), self.mate_right.copy()

    def _reachable_sets(self) -> tuple[list[bool], list[bool]]:
        """未マッチ左頂点から交互路で到達可能な左右の頂点集合を返す。"""
        self.solve()
        self._build_csr()
        start = self._start
        to = self._to
        seen_left = [False] * self.n_left
        seen_right = [False] * self.n_right
        queue: list[int] = []
        for left in range(self.n_left):
            if self.mate_left[left] == -1:
                seen_left[left] = True
                queue.append(left)

        q_front = 0
        while q_front < len(queue):
            left = queue[q_front]
            q_front += 1
            matched_right = self.mate_left[left]
            for i in range(start[left], start[left + 1]):
                right = to[i]
                if right == matched_right or seen_right[right]:
                    continue
                seen_right[right] = True
                next_left = self.mate_right[right]
                if next_left != -1 and not seen_left[next_left]:
                    seen_left[next_left] = True
                    queue.append(next_left)
        return seen_left, seen_right

    def min_vertex_cover(self) -> tuple[list[int], list[int]]:
        """最小頂点被覆を (左頂点列, 右頂点列) で返す。"""
        seen_left, seen_right = self._reachable_sets()
        left = [v for v in range(self.n_left) if not seen_left[v]]
        right = [v for v in range(self.n_right) if seen_right[v]]
        return left, right

    def max_independent_set(self) -> tuple[list[int], list[int]]:
        """最大独立集合を (左頂点列, 右頂点列) で返す。"""
        seen_left, seen_right = self._reachable_sets()
        left = [v for v in range(self.n_left) if seen_left[v]]
        right = [v for v in range(self.n_right) if not seen_right[v]]
        return left, right


class GeneralBipartiteMatching:
    """頂点を一つの整数空間で与え、自動で二部彩色する最大二部マッチング。"""

    def __init__(self, n: int) -> None:
        """n 頂点の空の辺列と、未彩色・未マッチの状態を初期化する。"""
        assert 0 <= n
        self.n = n
        self.edges: list[tuple[int, int]] = []
        self.color = [-1] * n
        self.toL = [-1] * n
        self.toR = [-1] * n
        self.fromL: list[int] = []
        self.fromR: list[int] = []
        self.mateL: list[int] = []
        self.mateR: list[int] = []
        self.mate = [-1] * n
        self.size = 0
        self._matching: BipartiteMatching | None = None
        self._solved = False

    def add_edge(self, u: int, v: int) -> int:
        """頂点 u, v を結ぶ辺を追加し、辺番号を返す。solve 後は彩色を含めて再構築する。"""
        assert 0 <= u < self.n
        assert 0 <= v < self.n
        edge_id = len(self.edges)
        self.edges.append((u, v))
        self._solved = False
        return edge_id

    def _bipartition(self) -> None:
        """現在の辺集合を二部彩色し、各頂点の色を self.color に保存する。"""
        graph = [[] for _ in range(self.n)]
        for u, v in self.edges:
            graph[u].append(v)
            graph[v].append(u)

        color = [-1] * self.n
        for start in range(self.n):
            if color[start] != -1:
                continue
            color[start] = 1
            queue = [start]
            q_front = 0
            while q_front < len(queue):
                u = queue[q_front]
                q_front += 1
                next_color = color[u] ^ 1
                for v in graph[u]:
                    if color[v] == -1:
                        color[v] = next_color
                        queue.append(v)
                    elif color[v] != next_color:
                        raise ValueError("graph is not bipartite")
        self.color = color

    def _build_lr(self) -> None:
        """二部彩色を左右に圧縮し、内部の BipartiteMatching を構築する。"""
        self._bipartition()
        self.fromL = [v for v in range(self.n) if self.color[v] == 0]
        self.fromR = [v for v in range(self.n) if self.color[v] == 1]
        self.toL = [-1] * self.n
        self.toR = [-1] * self.n
        for left, v in enumerate(self.fromL):
            self.toL[v] = left
        for right, v in enumerate(self.fromR):
            self.toR[v] = right

        matching = BipartiteMatching(len(self.fromL), len(self.fromR))
        packed_edges: list[int] = []
        shift = matching._edge_shift
        for u, v in self.edges:
            if self.color[u] == 0:
                left = self.toL[u]
                right = self.toR[v]
            else:
                left = self.toL[v]
                right = self.toR[u]
            packed_edges.append((left << shift) | right)

        matching._edges = packed_edges
        self._matching = matching

    def solve(self) -> int:
        """現在のグラフの最大マッチング数を返す。非二部グラフなら ValueError。"""
        if self._solved:
            return self.size
        self._build_lr()
        assert self._matching is not None
        self.size = self._matching.solve()
        self.mateL = self._matching.mate_left
        self.mateR = self._matching.mate_right
        self.mate = [-1] * self.n
        for left, right in enumerate(self.mateL):
            if right == -1:
                continue
            u = self.fromL[left]
            v = self.fromR[right]
            self.mate[u] = v
            self.mate[v] = u
        self._solved = True
        return self.size

    def matching_edges(self) -> list[tuple[int, int]]:
        """最大マッチングを (色0の頂点, 色1の頂点) の組で返す。"""
        self.solve()
        return [
            (self.fromL[left], self.fromR[right])
            for left, right in enumerate(self.mateL)
            if right != -1
        ]

    def matching_edge_ids(self) -> list[int]:
        """最大マッチングに対応する入力辺番号を返す。多重辺では最初の辺を選ぶ。"""
        self.solve()
        assert self._matching is not None
        return self._matching.matching_edge_ids()

    def mates(self) -> list[int]:
        """各頂点の対応先を返す。未対応は -1。"""
        self.solve()
        return self.mate.copy()

    def min_vertex_cover(self) -> list[int]:
        """元の頂点番号で最小頂点被覆を返す。"""
        self.solve()
        assert self._matching is not None
        left, right = self._matching.min_vertex_cover()
        return [self.fromL[v] for v in left] + [self.fromR[v] for v in right]

    def max_independent_set(self) -> list[int]:
        """元の頂点番号で最大独立集合を返す。"""
        self.solve()
        assert self._matching is not None
        left, right = self._matching.max_independent_set()
        return [self.fromL[v] for v in left] + [self.fromR[v] for v in right]
# ===== END: /Suzlib/python/graph/BipartiteMatching.py =====

# ===== BEGIN: /Suzlib/python/graph/SCC.py =====
# competitive-verifier: TITLE 強連結成分分解 (SCC)


def find_SCC(g):
    """
    グラフ g の SCC、各頂点の SCC 番号、縮約 DAG を返す。
    SCC 番号はトポロジカル順で、縮約 DAG の多重辺は除く。
    Gabow の path-based SCC algorithm を用いる。
    """
    n = len(g)

    SCC = []
    S = []  # Gabow の active stack
    P = []  # Gabow の root stack。S 上の根候補の位置を持つ
    pos = [0] * n  # 0: 未訪問, >0: S 上での位置, -1: SCC 確定済み
    comp = [-1] * n

    for i in range(n):
        if comp[i] != -1:
            continue

        st = [i]
        while st:
            v = st.pop()

            if v < 0:  # 帰りがけ
                v = ~v
                d = pos[v] - 1
                if P[-1] > d:  # v が根候補として残っている
                    SCC.append(S[d:])
                    P.pop()
                    del S[d:]

                    c = len(SCC) - 1
                    for u in SCC[-1]:
                        pos[u] = -1
                        comp[u] = c

            elif pos[v] > 0:  # SCC 未確定の頂点への辺
                while P[-1] > pos[v]:
                    P.pop()

            elif pos[v] == 0:  # 初訪問
                S.append(v)
                P.append(len(S))
                pos[v] = len(S)
                st.append(~v)
                st += g[v]

    k = len(SCC)
    groups = SCC[::-1]
    comp = [k - 1 - c for c in comp]

    return groups, comp, condensation_graph(g, groups, comp)


def condensation_graph(g, groups, comp):
    """
    SCC を縮約し、多重辺を除いた DAG の隣接リストを返す。
    """
    k = len(groups)
    dag = [[] for _ in range(k)]
    seen = [-1] * k  # seen[d] == c: SCC c から d への辺を追加済み

    for c, vs in enumerate(groups):
        for u in vs:
            for v in g[u]:
                d = comp[v]
                if d != c and seen[d] != c:
                    seen[d] = c
                    dag[c].append(d)

    return dag
# ===== END: /Suzlib/python/graph/SCC.py =====

# ===== BEGIN: /Suzlib/python/graph/BipartiteMatchingStructure.py =====
# competitive-verifier: TITLE 二部マッチングの構造

"""
DM分解、マッチングに使う辺・頂点
"""

# [bundled] from python.graph.BipartiteMatching import BipartiteMatching
# [bundled] from python.graph.SCC import find_SCC


REMOVED = -1
NEVER = 0
SOMETIMES = 1
ALWAYS = 2


def matching_structure(matching: BipartiteMatching) -> tuple[list[int], list[int], list[int]]:
    """
    各辺・左頂点・右頂点が最大マッチングで
    NEVER / SOMETIMES / ALWAYS のどれかを返す。

    戻り値は (edge_status, left_status, right_status)。
    edge_status は辺番号をそのまま添字に使い、削除済み辺は REMOVED とする。
    """
    matching.solve()

    n_left = matching.n_left
    n_right = matching.n_right
    s = n_left + n_right
    t = s + 1

    edges = matching.edges()
    mate_left, mate_right = matching.mates()
    matching_edge_ids = set(matching.matching_edge_ids())

    g = [[] for _ in range(t + 1)]

    # s -> left は容量 1。
    for left, right in enumerate(mate_left):
        if right == -1:
            g[s].append(left)
        else:
            g[left].append(s)

    # left -> right も容量 1。
    # 現在のマッチング辺だけ逆向き、それ以外は順向きが残余辺になる。
    for edge_id, left, right in edges:
        r = n_left + right
        if edge_id in matching_edge_ids:
            g[r].append(left)
        else:
            g[left].append(r)

    # right -> t は容量 1。
    for right, left in enumerate(mate_right):
        r = n_left + right
        if left == -1:
            g[r].append(t)
        else:
            g[t].append(r)

    _, comp, _ = find_SCC(g)

    edge_status = [REMOVED] * matching.edge_count()
    for edge_id, left, right in edges:
        r = n_left + right
        if comp[left] == comp[r]:
            edge_status[edge_id] = SOMETIMES
        elif edge_id in matching_edge_ids:
            edge_status[edge_id] = ALWAYS
        else:
            edge_status[edge_id] = NEVER

    left_status = [NEVER] * n_left
    for left, right in enumerate(mate_left):
        if comp[s] == comp[left]:
            left_status[left] = SOMETIMES
        elif right != -1:
            left_status[left] = ALWAYS

    right_status = [NEVER] * n_right
    for right, left in enumerate(mate_right):
        r = n_left + right
        if comp[r] == comp[t]:
            right_status[right] = SOMETIMES
        elif left != -1:
            right_status[right] = ALWAYS

    return edge_status, left_status, right_status


class DulmageMendelsohn:
    """
    二部マッチングを容量 1, inf, 1 の s-t フローに読み替え、
    全最小カットの構造から Dulmage--Mendelsohn 分解を求める。

    頂点番号は左 0..n_left-1、右 n_left..n_left+n_right-1、
    その後に s, t を置く。

    DM 分解は
      V0     : s から残余路で到達可能な固定領域
      blocks : V0, Vinf の外側にある SCC
      Vinf   : t へ残余路で到達可能な固定領域
    からなる。

    groups = [V0] + blocks + [Vinf] とし、comp, dag もこの番号を使う。
    残余グラフ自体の細かい SCC は scc_groups, scc_comp, scc_dag に残す。
    """

    SOURCE = 0
    FREE = 1
    SINK = 2

    def __init__(self, matching: BipartiteMatching) -> None:
        """最大マッチングから容量 1, inf, 1 の残余グラフを作り、DM 分解を求める。"""
        matching.solve()

        self.n_left = matching.n_left
        self.n_right = matching.n_right
        self.n = self.n_left + self.n_right
        self.s = self.n
        self.t = self.s + 1

        self.edges = matching.edges()
        self.mate_left, self.mate_right = matching.mates()

        g = [[] for _ in range(self.t + 1)]

        # s -> left は容量 1。
        for left, right in enumerate(self.mate_left):
            if right == -1:
                g[self.s].append(left)
            else:
                g[left].append(self.s)

        # left -> right は容量 inf なので、マッチング辺でも順向き残余辺が残る。
        # マッチング辺にはさらに逆向き残余辺がある。
        matched = set(matching.matching_edge_ids())
        for edge_id, left, right in self.edges:
            r = self.n_left + right
            g[left].append(r)
            if edge_id in matched:
                g[r].append(left)

        # right -> t は容量 1。
        for right, left in enumerate(self.mate_right):
            r = self.n_left + right
            if left == -1:
                g[r].append(self.t)
            else:
                g[self.t].append(r)

        self.residual_graph = g
        self.scc_groups, self.scc_comp, self.scc_dag = find_SCC(g)

        k_scc = len(self.scc_groups)
        s_scc = self.scc_comp[self.s]
        t_scc = self.scc_comp[self.t]

        # 最大流後なので s から t への残余路はない。
        assert s_scc != t_scc

        source_reachable = [False] * k_scc
        stack = [s_scc]
        source_reachable[s_scc] = True
        while stack:
            c = stack.pop()
            for d in self.scc_dag[c]:
                if not source_reachable[d]:
                    source_reachable[d] = True
                    stack.append(d)

        rev = [[] for _ in range(k_scc)]
        for c in range(k_scc):
            for d in self.scc_dag[c]:
                rev[d].append(c)

        sink_reachable = [False] * k_scc
        stack = [t_scc]
        sink_reachable[t_scc] = True
        while stack:
            c = stack.pop()
            for d in rev[c]:
                if not sink_reachable[d]:
                    sink_reachable[d] = True
                    stack.append(d)

        scc_state = [self.FREE] * k_scc
        for c in range(k_scc):
            if source_reachable[c]:
                scc_state[c] = self.SOURCE
            elif sink_reachable[c]:
                scc_state[c] = self.SINK
        self.scc_state = scc_state

        # V0, Vinf は固定領域全体として一つにまとめ、自由領域だけ SCC を保つ。
        free_scc = [c for c in range(k_scc) if scc_state[c] == self.FREE]
        free_id = [-1] * k_scc
        for i, c in enumerate(free_scc):
            free_id[c] = i

        self.V0 = [v for v in range(self.n) if scc_state[self.scc_comp[v]] == self.SOURCE]
        self.blocks = [
            [v for v in self.scc_groups[c] if v < self.n]
            for c in free_scc
        ]
        self.Vinf = [v for v in range(self.n) if scc_state[self.scc_comp[v]] == self.SINK]

        k = len(self.blocks)
        self.groups = [self.V0] + self.blocks + [self.Vinf]
        self.s_comp = 0
        self.t_comp = k + 1

        dm_of_scc = [-1] * k_scc
        for c in range(k_scc):
            if scc_state[c] == self.SOURCE:
                dm_of_scc[c] = self.s_comp
            elif scc_state[c] == self.SINK:
                dm_of_scc[c] = self.t_comp
            else:
                dm_of_scc[c] = 1 + free_id[c]

        self.comp = [dm_of_scc[self.scc_comp[v]] for v in range(self.n)]

        # V0 と Vinf をそれぞれ一頂点に縮約した DM の DAG。
        dag = [[] for _ in range(k + 2)]
        seen = [set() for _ in range(k + 2)]
        for c in range(k_scc):
            a = dm_of_scc[c]
            for d in self.scc_dag[c]:
                b = dm_of_scc[d]
                if a != b and b not in seen[a]:
                    seen[a].add(b)
                    dag[a].append(b)
        self.dag = dag

        self.state = [self.SOURCE] + [self.FREE] * k + [self.SINK]
        self.left_state = [self.state[self.comp[left]] for left in range(self.n_left)]
        self.right_state = [
            self.state[self.comp[self.n_left + right]]
            for right in range(self.n_right)
        ]
# ===== END: /Suzlib/python/graph/BipartiteMatchingStructure.py =====


import sys
readline = sys.stdin.readline

# def solve():
#     return
#
# T = int(readline())
# for _ in range(T):
#     a = [int(i) for i in readline().split()]
#     ans = solve()
#     print(ans)

#n = int(readline())
#a = [int(i) for i in readline().split()]
#ab = [[int(i) for i in readline().split()] for _ in range()]
#S = readline().strip()
#b = [readline().strip() for _ in range()]



n,m,L = [int(i) for i in readline().split()]
G = BipartiteMatching(n,m)

for _ in range(L):
    a,b = [int(i) for i in readline().split()]
    a -= 1
    b -= 1
    G.add_edge(a,b)

res = G.solve() # 最大マッチング


edge_status, left_status, right_status = matching_structure(G)

#print(edge_status)
#NEVER / SOMETIMES / ALWAYS 
for v in edge_status:
    if v == 0:
        print("No")
    else:
        print("Yes")