提出 #17348313

---

ソースコード 拡げる

import sys
import numpy as np
import numba
from numba import njit, b1, i4, i8, f8

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

uf_t = numba.types.UniTuple(i8[:], 2)


@njit((uf_t, i8), cache=True)
def find_root(uf, x):
    root = uf[0]
    while root[x] != x:
        root[x] = root[root[x]]
        x = root[x]
    return x


@njit((uf_t, i8, i8), cache=True)
def merge(uf, x, y):
    root, size = uf
    x, y = find_root(uf, x), find_root(uf, y)
    if x == y:
        return False
    if size[x] < size[y]:
        x, y = y, x
    size[x] += size[y]
    root[y] = root[x]
    return True

@njit((i8, i8, i8[:]), cache=True)
def solve(N, M, AB):
    last_M = N * (N - 1) // 2
    add = last_M - M
    if N % 2 == 1:
        # 運命は決まっている
        return add % 2 == 1
    # 以下、偶数頂点
    A, B = AB[::2], AB[1::2]
    root = np.arange(N + 1, dtype=np.int64)
    size = np.ones_like(root)
    uf = (root, size)
    for i in range(len(A)):
        merge(uf, A[i], B[i])
    r0, r1 = find_root(uf, 1), find_root(uf, N)
    s0, s1 = size[r0], size[r1]
    # 先手の理想形は？
    if add % 2 == 0:
        # 先手は (od, od) を目指すことになる
        if s0 % 2 == 0 and s1 % 2 == 0:
            return False
        return True
    else:
        # 先手は (ev, ev) を目指すことになる
        if s0 % 2 == 1 and s1 % 2 == 1:
            return False
        return True

@njit((i8[:], ), cache=True)
def main(nums):
    T, nums = nums[0], nums[1:]
    for _ in range(T):
        N, M = nums[:2]
        nums = nums[2:]
        AB = nums[:M + M]
        nums = nums[M + M:]
        print('First' if solve(N, M, AB) else 'Second')

nums = np.array(read().split(), np.int64)

main(nums)

提出情報

ジャッジ結果