Day 167-Q1 — 2026-10-01 | 一般グラフの Green Hackenbush（融合原理で 2 辺連結成分を縮約し、橋木の Grundy 数に落とす）

📋 コピーimport sys
def grundy(n, edges):
    # edges: list of (u,v), vertex 0 = ground. 接地成分に届かない辺は消える
    adj = [[] for _ in range(n)]
    for i,(u,v) in enumerate(edges):
        adj[u].append((v,i))
        if u != v: adj[v].append((u,i))
    # lowlink（再帰なし）。辺番号で親辺を判定（多重辺・自己ループに強い）
    order = [-1]*n; low = [0]*n; used_e = [False]*len(edges)
    bridge = [False]*len(edges)
    t = 0; order[0] = 0; low[0] = 0; t = 1
    stack = [(0, -1, 0)]
    parent_of = {}
    seq = [0]
    while stack:
        v, pe, idx = stack.pop()
        if idx < len(adj[v]):
            stack.append((v, pe, idx+1))
            w, ei = adj[v][idx]
            if ei == pe: continue
            if order[w] == -1:
                order[w] = low[w] = t; t += 1
                parent_of[w] = (v, ei)
                seq.append(w)
                stack.append((w, ei, 0))
            else:
                if order[w] < low[v]: low[v] = order[w]
        else:
            if v in parent_of:
                p, ei = parent_of[v]
                if low[v] < low[p]: low[p] = low[v]
                if low[v] > order[p]: bridge[ei] = True
    # 2 辺連結成分: 橋を使わずに到達できる頂点の塊（到達済み頂点 seq のみ）
    comp = [-1]*n; nc = 0
    for s in seq:
        if comp[s] != -1: continue
        comp[s] = nc; st = [s]
        while st:
            x = st.pop()
            for y, ei in adj[x]:
                if not bridge[ei] and comp[y] == -1:
                    comp[y] = nc; st.append(y)
        nc += 1
    par = [0]*nc          # 成分内の辺数の偶奇（自己ループ・多重辺を含む）
    kids = [[] for _ in range(nc)]
    for i,(u,v) in enumerate(edges):
        if comp[u] == -1: continue     # 接地成分の外
        if bridge[i]:
            # 橋: 根側が親。order が小さい側が親
            a, b = (u, v) if order[u] < order[v] else (v, u)
            kids[comp[a]].append(comp[b])
        else:
            par[comp[u]] ^= 1
    g = [0]*nc
    # comp 番号は発見順 → 子の番号は親より大きい。逆順に畳む
    for c in range(nc-1, -1, -1):
        x = par[c]
        for d in kids[c]: x ^= g[d] + 1
        g[c] = x
    return g[comp[0]]
def solve(n, edges):
    g = grundy(n, edges)
    cnt = 0
    for i in range(len(edges)):
        if grundy(n, edges[:i] + edges[i+1:]) == 0: cnt += 1
    return ("First" if g else "Second"), cnt
def main():
    data = sys.stdin.read().split()
    n, m = int(data[0]), int(data[1])
    edges = [(int(data[2+2*i])-1, int(data[3+2*i])-1) for i in range(m)]
    w, c = solve(n, edges)
    print(w); print(c)
if __name__ == "__main__": main()