Problem:


Score : 900 points

Problem Statement

There is a tree with N vertices numbered 1 through N.
The i-th of the N-1 edges connects vertices a_i and b_i.

Initially, each vertex is uncolored.

Takahashi and Aoki is playing a game by painting the vertices. In this game, they alternately perform the following operation, starting from Takahashi:

Select a vertex that is not painted yet.

If it is Takahashi who is performing this operation, paint the vertex white; paint it black if it is Aoki.

Then, after all the vertices are colored, the following procedure takes place:

Repaint every white vertex that is adjacent to a black vertex, in black.

Note that all such white vertices are repainted simultaneously, not one at a time.

If there are still one or more white vertices remaining, Takahashi wins; if all the vertices are now black, Aoki wins.
Determine the winner of the game, assuming that both persons play optimally.

Constraints

2 ≤ N ≤ 10^5

1 ≤ a_i,b_i ≤ N

a_i ≠ b_i

The input graph is a tree.

Input

Input is given from Standard Input in the following format:

N
a_1 b_1
:
a_{N-1} b_{N-1}

Output

Print First if Takahashi wins; print Second if Aoki wins.

Sample Input 1

3
1 2
2 3

Sample Output 1

First

Below is a possible progress of the game:

First, Takahashi paint vertex 2 white.

Then, Aoki paint vertex 1 black.

Lastly, Takahashi paint vertex 3 white.

In this case, the colors of vertices 1, 2 and 3 after the final procedure are black, black and white, resulting in Takahashi's victory.

Sample Input 2

4
1 2
2 3
2 4

Sample Output 2

First

Sample Input 3

6
1 2
2 3
3 4
2 5
5 6

Sample Output 3

Second



Sample input:
3
1 2
2 3


Sample output:
First

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
S=sys.stdin.readlines()
N=int(S[0])
G=[[] for i in range(N)]
a,b=0,0
for i in range(N-1):
  a,b=map(int,S[i+1].split())
  a,b=a-1,b-1
  G[a].append(b)
  G[b].append(a)
D=[-1]*N
D[0]=0
Q=deque([0])
v=0
for i in range(1,N):
  if len(Q)==0:
    break
  for j in range(len(Q)):
    v=Q.popleft()
    for k in range(len(G[v])):
      if D[G[v][k]]==-1:
        D[G[v][k]]=i
        Q.append(G[v][k])
P=0
for i in range(N):
  if D[i]&1:
    P+=1
  else:
    P-=1
if P:
  print('First')
else:
  print('Second')

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b=LI()
    G[a-1]+=[b-1]
    G[b - 1] += [a - 1]


depth = [-1] * n
v_set = set()
q = []
for i in range(n):
    if len(G[i]) == 1:
        q += [i]
        depth[i] = 0
        v_set.add(i)

qq = q
while len(v_set) != n:
    nq = []
    for u in q:
        for v in G[u]:
            if v in v_set:
                continue
            v_set.add(v)
            nq += [v]
            depth[v] = depth[u] + 1
    q = nq
    qq += q

parity = [-1] * n
for qqi in qq:
    ret = 1
    odd_cnt = 0
    for vv in G[qqi]:
        if parity[vv] != -1:
            ret ^= parity[vv]
            if parity[vv]:
                odd_cnt += 1
    if odd_cnt > 1:
        print("First")
        exit()
    parity[qqi] = ret


if parity[q[-1]] == 0:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b=LI()
    G[a-1]+=[b-1]
    G[b - 1] += [a - 1]


depth = [-1] * n
v_set = set()
q = []
for i in range(n):
    if len(G[i]) == 1:
        q += [i]
        depth[i] = 0
        v_set.add(i)

qq = q
while len(v_set) != n:
    nq = []
    for u in q:
        for v in G[u]:
            if v in v_set:
                continue
            v_set.add(v)
            nq += [v]
            depth[v] = depth[u] + 1
    q = nq
    qq += q

parity = [-1] * n
for qqi in qq:
    ret = 1
    odd_cnt = 0
    for vv in G[qqi]:
        if parity[vv] != -1:
            ret ^= parity[vv]
            if parity[vv]:
                odd_cnt += 1
    if odd_cnt > 1:
        print("First")
        exit()
    parity[qqi] = ret

ret2 = 0
for ii in q[::-1]:
    if depth[ii] != max(depth):
        break
    ret2 ^= parity[ii]


if ret2 == 0:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b=LI()
    G[a-1]+=[b-1]
    G[b - 1] += [a - 1]


par = [-1] * n

def f(u):
    ret = 1
    cnt = 0
    for v in G[u]:
        if v == par[u]:
            continue
        par[v] = u
        c = f(v)
        if c % 2:
            cnt += 1
            if cnt > 2:
                print("First")
                exit()
        ret ^= c
    return ret


if f(0) == 0:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b=LI()
    G[a-1]+=[b-1]
    G[b - 1] += [a - 1]


par = [0] * n

def f(u):
    ret = 1
    cnt = 0
    for v in G[u]:
        if v == par[u]:
            continue
        par[v] = u
        c = f(v)
        if c % 2:
            cnt += 1
            if cnt > 2:
                print("First")
                exit()
        ret ^= c
    return ret


if f(0) == 0:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b=LI()
    G[a-1]+=[b-1]
    G[b - 1] += [a - 1]


def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in G[v]:
        if memo[u]:
            continue
        if u in visited:
            continue
        visited.add(u)
        if dfs(matched[u], visited) == 0:
            memo[u] = 1
        elif matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False

cnt = 0
matched = [-1] * n
visited = set()
memo = [0] * n
for i in range(n):
    cnt += int(dfs(i, set()))

if cnt == n:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce


sys.setrecursionlimit(2147483647)
INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007

n = I()
G = [[] for _ in range(n)]
for _ in range(n-1):
    a,b=LI()
    G[a-1]+=[b-1]
    G[b - 1] += [a - 1]


def dfs(v, visited):
    if matched[v] != -1:
        return False
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in G[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            matched[v] = u
            return True
    return False

cnt = 0
matched = [-1] * n
for i in range(n):
    cnt += int(dfs(i, set())) * 2

if cnt == n:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint

sys.setrecursionlimit(2147483647)
INF = 10 ** 10
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n = I()
G = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


for i in range(n):
    one_cnt = 0
    for v in G[i]:
        if len(G[v]) == 1:
            one_cnt += 1
    if one_cnt >= 2:
        print("First")
        exit()

if max([len(G[i]) for i in range(n)]) <= 2 and n % 2:
    print("First")
    exit()

print("Second")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint

sys.setrecursionlimit(2147483647)
INF = 10 ** 10
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n = I()
G = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


for i in range(n):
    one_cnt = 0
    for v in G[i]:
        if len(G[v]) == 1:
            one_cnt += 1
    if one_cnt >= 2:
        print("First")
        exit()

print("Second")

Submission status: Wrong Answer

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
import bisect
import random
from itertools import permutations, accumulate, combinations, product
import sys
import string
from bisect import bisect_left, bisect_right
from math import factorial, ceil, floor
from operator import mul
from functools import reduce
from pprint import pprint

sys.setrecursionlimit(2147483647)
INF = 10 ** 10
def LI(): return list(map(int, sys.stdin.buffer.readline().split()))
def I(): return int(sys.stdin.buffer.readline())
def LS(): return sys.stdin.buffer.readline().rstrip().decode('utf-8').split()
def S(): return sys.stdin.buffer.readline().rstrip().decode('utf-8')
def IR(n): return [I() for i in range(n)]
def LIR(n): return [LI() for i in range(n)]
def SR(n): return [S() for i in range(n)]
def LSR(n): return [LS() for i in range(n)]
def SRL(n): return [list(S()) for i in range(n)]
def MSRL(n): return [[int(j) for j in list(S())] for i in range(n)]
mod = 1000000007



n = I()
G = [[] for _ in range(n)]
for _ in range(n-1):
    a, b = LI()
    G[a - 1] += [b - 1]
    G[b - 1] += [a - 1]


for i in range(n):
    one_cnt = 0
    for v in G[i]:
        if len(G[v]) == 1:
            one_cnt += 1
    if one_cnt >= 2:
        print("first")
        exit()

print("Second")

Submission status: Wrong Answer

Solution code:
N=int(input())
C=[0]*N
a,b=0,0
G=[[] for i in range(N)]
for i in range(N-1):
  a,b=map(int,input().split())
  a,b=a-1,b-1
  G[a].append(b)
  G[b].append(a)
  C[a]+=1
  C[b]+=1
P=[0]*N
for i in range(N):
  if C[i]==1:
    P[G[i][0]]+=1
if max(P)>=2:
  print('First')
else:
  print('Second')

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [set() for _ in [0]*n]
    [g[a-1].add(b-1) for a, b in ab]
    [g[b-1].add(a-1) for a, b in ab]
    only = []
    sign = [False]*n
    for i in range(n):
        if len(g[i]) == 1:
            only.append(i)
    while only:
        i = only.pop()
        if not g[i]:
            print("Second")
            return
        j = g[i].pop()
        g[j].remove(i)
        if sign[i] and (len(g[j]) == 0 or sign[j]):
            print("First")
            return
        sign[j] = not sign[i]
        if len(g[j]) == 1:
            only.append(j)


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    for root in range(n):
        if len(g[root]) > 2:
            break
    else:
        if n % 2:
            print("First")
        else:
            print("Second")
        return

    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d2 = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    end = [False]*n
    dp = [[] for _ in [0]*n]
    for _, i in d2:
        if len(g[i]) > 2:
            continue
        elif len(g[i]) == 1:
            dp[g[i][0]].append(1)
            if len(dp[g[i][0]]) > 1:
                end[g[i][0]] = True
        elif not end[i] and dp[i]:
            dist = dp[i][0]
            for j in g[i]:
                if d[j] < d[i]:
                    dp[j].append(dist+1)
    dp = [[j % 2 for j in i] for i in dp]
    one = set()
    for j, i in enumerate(dp):
        if i.count(1) > 1:
            print("First")
            return
        elif i.count(1) == 1:
            if len(g[j]) > 2:
                one.add(j)
    for i in one:
        q = [i]
        visited = {i}
        cnt = 1
        while q:
            qq = []
            j = q.pop()
            for k in g[j]:
                if k in visited:
                    continue
                visited.add(k)
                if len(g[k]) > 2:
                    if cnt % 2 == 0:
                        if k in one:
                            print("First")
                            return
                if k not in one:
                    qq.append(k)
            cnt += 1
            q = qq
    print("Second")


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    for root in range(n):
        if len(g[root]) > 2:
            break
    else:
        if n % 2:
            print("First")
        else:
            print("Second")
        return

    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d2 = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    end = [False]*n
    dp = [[] for _ in [0]*n]
    for _, i in d2:
        if len(g[i]) > 2:
            continue
        elif len(g[i]) == 1:
            dp[g[i][0]].append(1)
            if len(dp[g[i][0]]) > 1:
                end[g[i][0]] = True
        elif not end[i] and dp[i]:
            dist = dp[i][0]
            for j in g[i]:
                if d[j] < d[i]:
                    dp[j].append(dist+1)
    dp = [[j % 2 for j in i] for i in dp]
    one = set()
    for j, i in enumerate(dp):
        if i.count(1) > 1:
            print("First")
            return
        elif i.count(1) == 1:
            if len(g[j]) > 2:
                one.add(j)
    for i in one:
        q = [i]
        visited = {i}
        cnt = 1
        while q:
            qq = []
            j = q.pop()
            for k in g[j]:
                if k in visited:
                    continue
                visited.add(k)
                if len(g[k]) > 2:
                    if cnt % 2 == 0:
                        if k in one:
                            print("First")
                            return
                elif k not in one:
                    qq.append(k)
            cnt += 1
            q = qq
    print("Second")


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    for root in range(n):
        if len(g[root]) > 2:
            break
    else:
        if n % 2:
            print("First")
        else:
            print("Second")
        return

    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d2 = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    end = [False]*n
    dp = [[] for _ in [0]*n]
    for _, i in d2:
        if len(g[i]) > 2:
            continue
        elif len(g[i]) == 1:
            dp[g[i][0]].append(1)
            if len(dp[g[i][0]]) > 1:
                end[g[i][0]] = True
        elif not end[i] and dp[i]:
            dist = dp[i][0]
            for j in g[i]:
                if d[j] < d[i]:
                    dp[j].append(dist+1)
    dp = [[j % 2 for j in i] for i in dp]
    one = set()
    for j, i in enumerate(dp):
        if i.count(1) > 1:
            print("First")
            return
        elif i.count(1) == 1:
            if len(g[j]) > 2:
                one.add(j)
    for i in one:
        q = [i]
        visited = {i}
        cnt = 1
        while q:
            qq = []
            j = q.pop()
            for k in g[j]:
                if k in visited:
                    continue
                visited.add(k)
                if len(g[k]) > 2:
                    if cnt % 2 == 0:
                        if k in one:
                            print("First")
                            return
                elif len(g[k]) == 2:
                    qq.append(k)
            cnt += 1
            q = qq
    print("Second")


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    for root in range(n):
        if len(g[root]) > 2:
            break
    else:
        if n % 2:
            print("First")
        else:
            print("Second")
        return

    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d2 = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    end = [False]*n
    dp = [[] for _ in [0]*n]
    for _, i in d2:
        if len(g[i]) > 2:
            continue
        elif len(g[i]) == 1:
            dp[g[i][0]].append(1)
            if len(dp[g[i][0]]) > 1:
                end[g[i][0]] = True
        elif not end[i] and dp[i]:
            dist = dp[i][0]
            for j in g[i]:
                if d[j] < d[i]:
                    dp[j].append(dist+1)
    dp = [[j % 2 for j in i] for i in dp]
    one = set()
    for j, i in enumerate(dp):
        if i.count(1) > 1:
            print("First")
            return
        elif i.count(1) == 1:
            one.add(j)
    for i in one:
        q = [i]
        visited = {i}
        cnt = 1
        while q:
            qq = []
            j = q.pop()
            for k in g[j]:
                if k in visited:
                    continue
                visited.add(k)
                if len(g[k]) > 2:
                    if cnt % 2 == 0:
                        if k in one:
                            print("First")
                            return
                elif len(g[k]) == 2:
                    qq.append(k)
            cnt += 1
            q = qq
    print("Second")


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    for root in range(n):
        if len(g[root]) > 2:
            break
    else:
        if n % 2:
            print("First")
        else:
            print("Second")
        return

    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d2 = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    end = [False]*n
    dp = [[] for _ in [0]*n]
    for _, i in d2:
        if len(g[i]) > 2:
            continue
        elif len(g[i]) == 1:
            dp[g[i][0]].append(1)
            if len(dp[g[i][0]]) > 1:
                end[g[i][0]] = True
        elif not end[i] and dp[i]:
            dist = dp[i][0]
            for j in g[i]:
                if d[j] < d[i]:
                    dp[j].append(dist+1)
    dp = [[j % 2 for j in i] for i in dp]
    one = set()
    for j, i in enumerate(dp):
        if i.count(1) > 1:
            print("First")
            return
        elif i.count(1) == 1:
            one.add(j)
    for i in one:
        q = [i]
        visited = {i}
        cnt = 1
        while q:
            qq = []
            j = q.pop()
            for k in g[j]:
                if k in visited:
                    continue
                visited.add(k)
                if len(g[k]) > 2:
                    if cnt % 2 == 0:
                        if k in one:
                            print(i, k)
                            print("First")
                            return
                elif len(g[k]) == 2:
                    qq.append(k)
            cnt += 1
            q = qq
    print("Second")


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    for root in range(n):
        if len(g[root]) > 2:
            break
    else:
        if n % 2:
            print("First")
        else:
            print("Second")
        return

    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d2 = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    end = [False]*n
    dp = [[] for _ in [0]*n]
    for _, i in d2:
        if len(g[i]) > 2:
            continue
        elif len(g[i]) == 1:
            dp[g[i][0]].append(1)
            if len(dp[g[i][0]]) > 1:
                end[g[i][0]] = True
        elif not end[i] and dp[i]:
            dist = dp[i][0]
            for j in g[i]:
                if d[j] < d[i]:
                    dp[j].append(dist+1)
    dp = [[j % 2 for j in i] for i in dp]
    one = set()
    for j, i in enumerate(dp):
        if i.count(1) > 1:
            print("First")
            return
        elif i.count(1) == 1:
            one.add(j)
    for i in one:
        q = [i]
        visited = set()
        cnt = 0
        while q:
            qq = []
            j = q.pop()
            for k in g[j]:
                if k in visited:
                    continue
                visited.add(k)
                if len(g[k]) > 2:
                    if cnt % 2 == 0:
                        if k in one:
                            print("First")
                            return
                elif len(g[k]) == 2:
                    qq.append(k)
            cnt += 1
            q = qq
    print("Second")


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]

    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    for root in range(n):
        if len(g[root]) > 2:
            break
    else:
        if n % 2:
            print("First")
        else:
            print("Second")
        return

    d = [-1]*n  # 根からの距離
    d[root] = 0
    q = [root]
    cnt = 0
    while q:  # BFS
        cnt += 1
        qq = []
        while q:
            i = q.pop()
            for j in g[i]:
                if d[j] == -1:
                    d[j] = cnt
                    qq.append(j)
        q = qq
    d2 = sorted([(j, i) for i, j in enumerate(d)])[::-1]
    end = [False]*n
    dp = [[] for _ in [0]*n]
    for _, i in d2:
        if len(g[i]) > 2:
            continue
        elif len(g[i]) == 1:
            dp[g[i][0]].append(1)
            if len(dp[g[i][0]]) > 1:
                end[g[i][0]] = True
        elif not end[i] and dp[i]:
            dist = dp[i][0]
            for j in g[i]:
                if d[j] < d[i]:
                    dp[j].append(dist+1)
    dp = [[j % 2 for j in i] for i in dp]
    for i in dp:
        if i.count(1) > 1:
            print("First")
            return
    print("Second")


main()

Submission status: Wrong Answer

Solution code:
def main():
    n = int(input())
    ab = [list(map(int, input().split())) for _ in [0]*(n-1)]
    g = [[] for _ in [0]*n]
    [g[a-1].append(b-1) for a, b in ab]
    [g[b-1].append(a-1) for a, b in ab]
    for i in range(n):
        if len(g[i]) > 1:
            cnt = 0
            for j in g[i]:
                if len(g[j]) == 1:
                    cnt += 1
            if cnt > 1:
                print("First")
                return
    print("Second")


main()