Day 173-Q3 — 2026-10-09 | 無向頂点ジオグラフィ（勝敗は「全ての最大マッチングに入るか」で決まる）

📋 コピーimport sys
from collections import deque


def hopcroft_karp(nl, nr, adj):
    INF = 1 << 30
    ml = [-1] * nl
    mr = [-1] * nr
    while True:
        dist = [INF] * nl
        q = deque()
        for u in range(nl):
            if ml[u] < 0:
                dist[u] = 0
                q.append(u)
        found = False
        while q:
            u = q.popleft()
            for v in adj[u]:
                w = mr[v]
                if w < 0:
                    found = True
                elif dist[w] == INF:
                    dist[w] = dist[u] + 1
                    q.append(w)
        if not found:
            return ml, mr
        it = [0] * nl
        for s in range(nl):                      # 反復 DFS で増加路を探す
            if ml[s] >= 0:
                continue
            stack = [s]
            while stack:
                u = stack[-1]
                if it[u] < len(adj[u]):
                    v = adj[u][it[u]]
                    it[u] += 1
                    w = mr[v]
                    if w < 0:                    # 増加路が見つかった: スタックに沿って反転
                        while stack:
                            uu = stack.pop()
                            vv = adj[uu][it[uu] - 1]
                            ml[uu] = vv
                            mr[vv] = uu
                        break
                    if dist[w] == dist[u] + 1:
                        stack.append(w)
                else:
                    dist[u] = INF
                    stack.pop()


def main():
    data = sys.stdin.buffer.read().split()
    nl, nr, m = int(data[0]), int(data[1]), int(data[2])
    adj = [[] for _ in range(nl)]
    radj = [[] for _ in range(nr)]
    p = 3
    for _ in range(m):
        a, b = int(data[p]) - 1, int(data[p + 1]) - 1
        p += 2
        adj[a].append(b)
        radj[b].append(a)
    ml, mr = hopcroft_karp(nl, nr, adj)
    # 左の頂点 u が「ある最大マッチングで使われない」
    #   ⇔ 左の自由頂点から 交互路（左→右は非マッチ辺、右→左はマッチ辺）で偶数歩で着く
    freeL = [False] * nl
    q = deque(u for u in range(nl) if ml[u] < 0)
    for u in q:
        freeL[u] = True
    while q:
        u = q.popleft()
        for v in adj[u]:
            w = mr[v]
            if w >= 0 and not freeL[w]:
                freeL[w] = True
                q.append(w)
    freeR = [False] * nr
    q = deque(v for v in range(nr) if mr[v] < 0)
    for v in q:
        freeR[v] = True
    while q:
        v = q.popleft()
        for u in radj[v]:
            w = ml[u]
            if w >= 0 and not freeR[w]:
                freeR[w] = True
                q.append(w)
    out = ['Second' if f else 'First' for f in freeL]
    out += ['Second' if f else 'First' for f in freeR]
    sys.stdout.write('\n'.join(out) + '\n')


if __name__ == "__main__":
    main()