Problem:


Score : 800 points

Problem Statement

Takahashi and Aoki will play a game on a tree.
The tree has N vertices numbered 1 to N, and the i-th of the N-1 edges connects Vertex a_i and Vertex b_i.

At the beginning of the game, each vertex contains a coin.
Starting from Takahashi, he and Aoki will alternately perform the following operation:

Choose a vertex v that contains one or more coins, and remove all the coins from v.

Then, move each coin remaining on the tree to the vertex that is nearest to v among the adjacent vertices of the coin's current vertex.

The player who becomes unable to play, loses the game.
That is, the player who takes his turn when there is no coin remaining on the tree, loses the game.
Determine the winner of the game when both players play optimally.

Constraints

1 \leq N \leq 2 \times 10^5

1 \leq a_i, b_i \leq N

a_i \neq b_i

The graph given as input is a tree.

Input

Input is given from Standard Input in the following format:

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

Output

Print First if Takahashi will win, and print Second if Aoki will win.

Sample Input 1

3
1 2
2 3

Sample Output 1

First

Here is one possible progress of the game:

Takahashi removes the coin from Vertex 1. Now, Vertex 1 and Vertex 2 contain one coin each.

Aoki removes the coin from Vertex 2. Now, Vertex 2 contains one coin.

Takahashi removes the coin from Vertex 2. Now, there is no coin remaining on the tree.

Aoki takes his turn when there is no coin on the tree and loses.

Sample Input 2

6
1 2
2 3
2 4
4 6
5 6

Sample Output 2

Second

Sample Input 3

7
1 7
7 4
3 4
7 5
6 3
2 1

Sample Output 3

First



Sample input:
3
1 2
2 3


Sample output:
First

Submission status: Wrong Answer

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline

N = int(input())

if (N == 1):
    print("First")
    quit()

tree = defaultdict(list)
nodes_len = defaultdict(list)
for i in range(N):
    nodes_len[i+1] = [0, 0]

for i in range(N-1):
    a, b = tuple(map(int, input().split()))
    tree[a].append(b)
    tree[b].append(a)

while len(tree) > 1:
    del_nodes = []
    for from_node, to_nodes in tree.items():
        # dictのサイズが1なら
        if len(to_nodes) == 1:
            to_node = to_nodes[0]

            # そのノードが持つ隣接ノード長を追加する
            nodes_len[to_node].append(nodes_len[from_node][0]+1)

            # 長さが2以上のみ保持する
            nodes_len[to_node].sort(reverse=True)
            nodes_len[to_node] = nodes_len[to_node][:2]

            # treeのto_nodeの部分から削除する
            tree[to_node].remove(from_node)

            del_nodes.append(from_node)

    for node in del_nodes:
        del tree[node]
    print(tree)

n = list(tree.keys())[0]
print("Second" if (nodes_len[n][0] + nodes_len[n][1]+1) % 3 == 2 else "First")

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
inarr=[[int(j) for j in input().split()] for i in range(N-1)]
nodes={}
if N == 1:
    print("First")
    exit()
class Node:
    def __init__(self, parent, children, value):
        self.parent = parent
        self.children = children
        self.value = value
    
    def __str__(self):
        return "NODE[v={},par={},chld={}]".format(self.value,self.parent.value if self.parent else "none",list(map(lambda x: x.value, self.children)))

for i,j in inarr:
    if not i in nodes:
        nodes[i] = Node(None, [], i)
        if not j in nodes:
            nodes[j] = Node(nodes[i], [], j)
            nodes[i].children.append(nodes[j])
        else:
            nodes[i].parent = nodes[j]
            nodes[j].children.append(nodes[i])
    else:
        if not j in nodes:
            nodes[j] = Node(nodes[i], [], j)
            nodes[i].children.append(nodes[j])
        else:
            if not nodes[i].parent:
                nodes[i].parent = nodes[j]
                nodes[j].children.append(nodes[i])
            else:
                nodes[j].parent = nodes[i]
                nodes[i].children.append(nodes[j])
                

visited = {1: True}
queue = collections.deque([[1, 0]])
while queue:
    i, d = queue.popleft()
    for node in nodes[i].children:
        if not node.value in visited:
            visited[node.value] = True
            queue += [[node.value, d + 1]]
    if nodes[i].parent and not nodes[i].parent.value in visited:
        visited[nodes[i].parent.value] = True
        queue += [[nodes[i].parent.value, d + 1]]

# print("i: {} d: {}".format(i,d))

visited = {i: True}
queue = collections.deque([[i, 0]])
while queue:
    i, d = queue.popleft()
    for node in nodes[i].children:
        if not node.value in visited:
            visited[node.value] = True
            queue += [[node.value, d + 1]]
    if nodes[i].parent and not nodes[i].parent.value in visited:
        visited[nodes[i].parent.value] = True
        queue += [[nodes[i].parent.value, d + 1]]

# print(list(map(str,nodes.values())))
# print("i: {} d: {}".format(i,d))
print('Second' if (d + 1) % 3 == 2 else 'First')

Submission status: Wrong Answer

Solution code:
import collections
N=int(input())
inarr=[[int(j) for j in input().split()] for i in range(N-1)]
nodes={}
if N == 1:
    print("First")
    exit()
class Node:
    def __init__(self, parent, children, value):
        self.parent = parent
        self.children = children
        self.value = value
    
    def __str__(self):
        return "NODE[v={},par={},chld={}]".format(self.value,self.parent.value if self.parent else "none",list(map(lambda x: x.value, self.children)))

for i,j in inarr:
    if not i in nodes:
        nodes[i] = Node(None, [], i)
        if not j in nodes:
            nodes[j] = Node(nodes[i], [], j)
            nodes[i].children.append(nodes[j])
        else:
            nodes[i].parent = nodes[j]
            nodes[j].children.append(nodes[i])
    else:
        if not j in nodes:
            nodes[j] = Node(nodes[i], [], j)
            nodes[i].children.append(nodes[j])
        else:
            if not nodes[i].parent:
                nodes[i].parent = nodes[j]
                nodes[j].children.append(nodes[i])
            elif not nodes[j].parent:
                nodes[j].parent = nodes[i]
                nodes[i].children.append(nodes[j])
            else:
                print("error")

visited = {1: True}
queue = collections.deque([[1, 0]])
while queue:
    i, d = queue.popleft()
    for node in nodes[i].children:
        if not node.value in visited:
            visited[node.value] = True
            queue += [[node.value, d + 1]]
    if nodes[i].parent and not nodes[i].parent.value in visited:
        visited[nodes[i].parent.value] = True
        queue += [[nodes[i].parent.value, d + 1]]

# print("i: {} d: {}".format(i,d))

visited = {i: True}
queue = collections.deque([[i, 0]])
while queue:
    i, d = queue.popleft()
    for node in nodes[i].children:
        if not node.value in visited:
            visited[node.value] = True
            queue += [[node.value, d + 1]]
    if nodes[i].parent and not nodes[i].parent.value in visited:
        visited[nodes[i].parent.value] = True
        queue += [[nodes[i].parent.value, d + 1]]

# print(list(map(str,nodes.values())))
# print("i: {} d: {}".format(i,d))
print('Second' if (d + 1) % 3 == 2 else 'First')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-
import collections


class Node(object):

  def __init__(self):
    self.edges = set()
    self.distance = 1


def main():
  N = int(input())
  nodes = [Node() for _ in range(N)]

  if N == 0:
    print('Second', flush=True)
    return
  elif N == 1:
    print('First', flush=True)
    return

  for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].edges.add(nodes[b - 1])
    nodes[b - 1].edges.add(nodes[a - 1])

  leaves = collections.deque(n for n in nodes if len(n.edges) == 1)

  while True:
    leaf = leaves.pop()
    parent = leaf.edges.pop()

    if len(parent.edges) == 1:
      size = leaf.distance + parent.distance
      break

    parent.distance = max(parent.distance, leaf.distance + 1)
    parent.edges.remove(leaf)

    if len(parent.edges) == 1:
      leaves.append(parent)

  if size % 3 == 2:
    print('Second', flush=True)
  else:
    print('First', flush=True)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
N = int(input())
E = [[] for _ in range(N)]
for i in range(N - 1):
	a, b = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)


visited = [False] * N

stack = [
	i
	for i in range(N)
	if len(E[i]) == 1
]

max_d = 0
cnt = 0
while stack:
	nexts = []
	cnt = 0
	for i in stack:
		if not visited[i]:
			visited[i] = True
			cnt += 1
		nexts.extend(v for v in E[i] if not visited[v])
	max_d += 1
	stack = nexts

Rx2 = max_d * 2 if 1 < cnt else max_d * 2 - 1
print('First' if (Rx2 % 3 != 2) else 'Second')

Submission status: Wrong Answer

Solution code:
N = int(input())
E = [[] for _ in range(N)]
for i in range(N - 1):
	a, b = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)


visited = [False] * N

stack = [
	i
	for i in range(N)
	if len(E[i]) == 1
]

max_d = 0
cnt = 0
while stack:
	nexts = []
	cnt = 0
	for i in stack:
		if not visited[i]:
			visited[i] = True
			cnt += 1
		nexts.extend(v for v in E[i] if not visited[v])
	max_d += 1
	stack = nexts

Rx2 = max_d * 2 if 1 < cnt else max_d * 2 - 1
print(Rx2)
print('First' if (Rx2 % 3 != 2) else 'Second')

Submission status: Wrong Answer

Solution code:
N = int(input())
E = [[] for _ in range(N)]
for i in range(N - 1):
	a, b = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)


INF = N + 1
D = [INF] * N

stack = [
	i
	for i in range(N)
	if len(E[i]) == 1
]

for i in stack:
	D[i] = 0

max_d = 0
cnt = 0
while stack:
	nexts = []
	for i in stack:
		if D[i] > max_d:
			D[i] = max_d
		nexts.extend(v for v in E[i] if D[v] == INF)
	max_d += 1
	cnt = len(stack)
	stack = nexts

Rx2 = max_d * 2 if 1 < cnt else max_d * 2 - 1
print('First' if (Rx2 % 3 != 2) else 'Second')

Submission status: Wrong Answer

Solution code:
import numpy as np

N = int(input())
E = [[] for _ in range(N)]
for i in range(N - 1):
	a, b = map(int, input().split())
	E[a - 1].append(b - 1)
	E[b - 1].append(a - 1)


INF = N + 1
D = [INF] * N

stack = [
	i
	for i in range(N)
	if len(E[i]) == 1
]

for i in stack:
	D[i] = 0

max_d = 0
while stack:
	nexts = []
	for i in stack:
		if D[i] > max_d:
			D[i] = max_d
		nexts.extend(v for v in E[i] if D[v] == INF)
	max_d += 1
	stack = nexts

print('First' if not (max_d & 1) else 'Second')

Submission status: Wrong Answer

Solution code:
import sys
range = xrange
input = sys.stdin.readline

n = int(input())
coupl = [[] for _ in range(n)]
for _ in range(n-1):
    u,v = [int(x)-1 for x in input().split()]
    
    coupl[u].append(v)
    coupl[v].append(u)

root = 0
for _ in range(2):
    depth = [-1]*n
    depth[root] = 1
    Q = [root]
    for node in Q:
        d = depth[node]
        for nei in coupl[node]:
            if depth[nei]==-1:
                depth[nei] = d+1
                Q.append(nei)

    root = max(range(n), key = lambda i:depth[i])
dia = depth[root]
print dia

if dia%3!=2:
    print 'First'
else:
    print 'Second'

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

if N == 1:
    print("First")
    exit()
conn = [len(v) for v in adj]
min_ind = conn.index(1)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1 and prev in adj[cur]:
        return dist
    else:
        ret = 0
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = max(ret, dfs(n, cur, dist+1))
        return ret


D = dfs(min_ind, -1, 0)
if D % 3 == 1:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

if N == 1:
    print("First")
    exit()
conn = [len(v) for v in adj]
min_ind = conn.index(1)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1 and prev in adj[cur]:
        return dist
    else:
        ret = 0
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = max(ret, dfs(n, cur, dist+1))
        return ret


D = dfs(min_ind, -1, 0)
if D % 3 != 1:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

if N == 1:
    print("First")
    exit()
conn = [len(v) for v in adj]
min_ind = conn.index(1)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1 and prev in adj[cur]:
        return dist
    else:
        ret = 0
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = max(ret, dfs(n, cur, dist+1))
        return ret


D = dfs(min_ind, -1, 0)+1
if D % 3 != 1:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

if N == 1:
    print("First")
    exit()
conn = [len(v) for v in adj]
min_ind = conn.index(1)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1 and prev in adj[cur]:
        return dist
    else:
        ret = 0
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = max(ret, dfs(n, cur, dist+1))
        return ret


D = dfs(min_ind, -1, 0)+1
if D % 3 != 2:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

if N == 1:
    print("First")
    exit()
conn = [len(v) for v in adj]
min_ind = conn.index(1)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1 and prev in adj[cur]:
        return dist
    else:
        ret = 0
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = max(ret, dfs(n, cur, dist+1))
        return ret


D = dfs(min_ind, -1, 0)+1
print(D)
if D % 3 == 2:
    print("First")
else:
    print("Second")

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

if N == 1:
    print("First")
    exit()
conn = [len(v) for v in adj]
min_ind = conn.index(1)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1 and prev in adj[cur]:
        return dist
    else:
        ret = 0
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = max(ret, dfs(n, cur, dist+1))
        return ret


D = dfs(min_ind, -1, 0)
print(D)
if D % 3 != 1:
    print("First")
else:
    print("Second")

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

if N == 1:
    print("First")
    exit()
conn = [len(v) for v in adj]
min_ind = conn.index(1)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1 and prev in adj[cur]:
        return dist
    else:
        ret = 0
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = max(ret, dfs(n, cur, dist+1))
        return ret


D = dfs(min_ind, -1, 0)+1
print(D)
if D % 3 != 2:
    print("First")
else:
    print("Second")

Submission status: Wrong Answer

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

if N == 1:
    print("First")
    exit()
conn = [len(v) for v in adj]
min_ind = conn.index(1)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1 and prev in adj[cur]:
        return dist
    else:
        ret = 0
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = max(ret, dfs(n, cur, dist+1))
        return ret


D = dfs(min_ind, -1, 0)+1
if D % 3 != 1:
    print("First")
else:
    print("Second")

Submission status: Wrong Answer

Solution code:
print "First" if input()%3 else "Second"

Submission status: Wrong Answer

Solution code:
print "First" if input()%3-1 else "Second"

Submission status: Wrong Answer

Solution code:

import unittest

import random

def main():
    N = int(input())
    tree = [[] for i in range(N)]
    for _ in range(N-1):
        a,b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)

    print(solve(N, tree))

def solve(n, tree):
    if first_win(n, tree):
        return 'First'
    else:
        return 'Second'
    
def first_win(n, tree):
    res = [False, True,False,True,True,False]
    for i in range(6,n):
        res.append(not res[-2] or not res[-1])

    cnt_leaf = 0
    leafs = []
    for i in range(n):
        if len(tree[i]) == 1:
            cnt_leaf += 1
            leafs.append(i)
    return res[n-cnt_leaf] or res[n-cnt_leaf+1]

            
    

            



if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
a = [input().split() for _ in range(n-1)]

counter = {}
o_count = 0
e_count = 0

for i in range(n-1):
    for cell in a[i]:
        if cell in counter:
            counter[cell] += 1
        else:
            counter[cell] = 1

for v in counter.values():
    if v % 2 == 0:
        e_count += 1
    else:
        o_count += 1

print('First' if e_count % 2 != 0 else 'Second')

Submission status: Wrong Answer

Solution code:
from functools import reduce
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

conn = [len(v) for v in adj]
max_val = max(conn)
max_ind = []
for i, v in enumerate(conn):
    if v == max_val:
        max_ind.append(i)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1:
        return dist
    else:
        ret = float('inf')
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = min(ret, dfs(n, cur, dist+1))
        return ret


def xor(x, y):
    return x ^ y


for max_node in max_ind:
    dist = 0
    for nex in adj[max_node]:
        ret = dfs(nex, max_node, 1)
        dist ^= ret
    if dist % 2 != 0:
        ans = "Second"
        print(ans)
        exit()


print("First")

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[0 for i in range(n)]
L=[list(map(int,input().split())) for i in range(n-1)]
ct=0
for i in range(n-1):
  l[L[i][0]-1]+=1
  l[L[i][1]-1]+=1
for i in range(n):
  if l[i]>=3:ct+=1
if ct%2==0:print('First')
else:print('Second')

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[0 for i in range(n)]
L=[list(map(int,input().split())) for i in range(n-1)]
ct=0
for i in range(n-1):
  l[L[i][0]-1]+=1
  l[L[i][1]-1]+=1
for i in range(n):
  if l[i]>=3:ct+=1
if ct>2 or ct==0:print('First')
else:print('Second')

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self):
    self.edges = []
    self.distance = 1


def main():
  N = int(input())
  nodes = [Node() for _ in range(N)]

  if N == 0:
    print('Second', flush=True)
    return
  elif N == 1:
    print('First', flush=True)
    return

  for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].edges.append(nodes[b - 1])
    nodes[b - 1].edges.append(nodes[a - 1])

  leaves = [n for n in nodes if len(n.edges) == 1]
  nodes = [n for n in nodes if len(n.edges) != 1]

  if N % 3 == 2:
    print('Second', flush=True)
  else:
    print('First', flush=True)


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
from functools import reduce
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

conn = [len(v) for v in adj]
max_val = max(conn)
max_ind = []
for i, v in enumerate(conn):
    if v == max_val:
        max_ind.append(i)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1:
        return dist
    else:
        ret = float('inf')
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = min(ret, dfs(n, cur, dist+1))
        return ret


def xor(x, y):
    return x ^ y


for max_node in max_ind:
    dist = 0
    for nex in adj[max_node]:
        ret = dfs(nex, max_node, 1)
        dist ^= ret
    if dist != 0:
        ans = "Second"
        print(ans)
        exit()


print("First")

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[0 for i in range(n)]
L=[list(map(int,input().split())) for i in range(n-1)]
ct=0
for i in range(n-1):
  l[L[i][0]-1]+=1
  l[L[i][1]-1]+=1

if max(l)>4:print('First')
else:print('Second')

Submission status: Wrong Answer

Solution code:
N = int(input())
for _ in range(N - 1):
	input()
print('First' if N & 1 else 'Second')

Submission status: Wrong Answer

Solution code:
from functools import reduce
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

conn = [len(v) for v in adj]
max_val = max(conn)
max_ind = []
for i, v in enumerate(conn):
    if v == max_val:
        max_ind.append(i)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1:
        return dist
    else:
        ret = 0
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = max(ret, dfs(n, cur, dist+1))
        return ret


def xor(x, y):
    return x ^ y


for max_node in max_ind:
    dist = 0
    for nex in adj[max_node]:
        ret = dfs(nex, max_node, 1)
        dist ^= ret
    if dist != 0:
        ans = "Second"
        print(ans)
        exit()


print("First")

Submission status: Wrong Answer

Solution code:

import unittest

import random

def main():
    N = int(input())
    tree = [[] for i in range(N)]
    for i in range(N-1):
        a,b = map(int, input().split())
        tree[a-1].append(b-1)
        tree[b-1].append(a-1)


    print(solve(N, tree))

def solve(n, tree):
    if first_win(n, tree):
        return 'First'
    else:
        return 'Second'
    
def first_win(n, tree):

    if n == 1:
        return True
    elif n == 2:
        return False
    elif n == 3:
        return True
    elif n == 4:
        return True
    elif n == 5:
        return False
    elif n == 6:
        return False
    elif n == 7:
        return True
    else:
        return random.choice([True, False])




if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(10**7)

N = int(input())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)

if all(len(e)<=2 for e in es):
    print('First' if N%2 else 'Second')
    exit()

centroid = []
size = [0] * N
def dfs(v,prev):
    size[v] = 1
    is_centroid = True
    for to in es[v]:
        if to == prev: continue
        dfs(to,v)
        size[v] += size[to]
        if size[to] > N//2: is_centroid = False
    if N - size[v] > N//2: is_centroid = False
    if is_centroid:
        centroid.append(v)
dfs(0,-1)

print('First' if len(centroid)%2 else 'Second')

Submission status: Wrong Answer

Solution code:
from functools import reduce
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

conn = [len(v) for v in adj]
# print(conn)
max_val = max(conn)
max_ind = []
for i, v in enumerate(conn):
    if v == max_val:
        max_ind.append(i)
#print("max_ind->", max_ind)
# max_node = conn.index(max(conn))
# print(max_node)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1:
        return dist
    else:
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                return dfs(n, cur, dist+1)


# print("dist")
def xor(x, y):
    return x ^ y


for max_node in max_ind:
    dist = 0
    for nex in adj[max_node]:
        ret = dfs(nex, max_node, 1)
       # print("ret->", ret)
        dist ^= ret
        # print(dfs(nex, max_node, 1))
    if dist != 0:
        ans = "Second"
        print(ans)
        exit()


print("First")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self):
    self.edges = []
    self.distance = 1


def main():
  N = int(input())
  nodes = [Node() for _ in range(N)]

  if N == 0:
    print('Second', flush=True)
    return
  elif N == 1:
    print('First', flush=True)
    return

  for _ in range(N - 1):
    a, b = map(int, input().split())
    nodes[a - 1].edges.append(nodes[b - 1])
    nodes[b - 1].edges.append(nodes[a - 1])

  leaves = [n for n in nodes if len(n.edges) == 1]
  print('First')

Submission status: Wrong Answer

Solution code:
from functools import reduce
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

N = int(input())
adj = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    adj[a].append(b)
    adj[b].append(a)

conn = [len(v) for v in adj]
# print(conn)
max_val = max(conn)
max_ind = []
for i, v in enumerate(conn):
    if v == max_val:
        max_ind.append(i)
# max_node = conn.index(max(conn))
# print(max_node)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1:
        return dist
    else:
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                return dfs(n, cur, dist+1)


# print("dist")
def xor(x, y):
    return x ^ y


for max_node in max_ind:
    dist = 0
    for nex in adj[max_node]:
        dist ^= dfs(nex, max_node, 1)
        # print(dfs(nex, max_node, 1))
        if dist != 0:
            ans = "Second"
            print(ans)
            exit()


print("First")

Submission status: Wrong Answer

Solution code:
#!/usr/bin/env python3
import sys

def dfs(idx, con, visited):
    visited[idx] = True
    max_depth = 0
    max_len = 0
    depths = []
    return 0, 0
    for v in con[idx]:
        if not visited[v]:
            max_d, max_l = dfs(v, con, visited)
            max_len = max(max_len, max_l)
            depths.append(max_d + 1)
    if len(depths) > 0:
        depths.sort(reverse=True)
        max_depth = depths[0]
        if len(depths) > 1:
            max_len = max(max_len, depths[0] + depths[1])
        else:
            max_len = max(max_len, depths[0])
    return max_depth, max_len


def solve(N: int, A: "List[int]", B: "List[int]"):
    con = [[] for _ in range(N)]
    for i in range(len(A)):
        a = A[i] - 1
        b = B[i] - 1
        con[a].append(b)
        con[b].append(a)
    #print(con)
    visited = [False] * N
    max_depth, max_len = dfs(0, con, visited)
    #print(max_len)
    if (max_len + 1) % 3 == 2:
        ret = 'Second'
    else:
        ret = 'First'
    print(ret)
    return


def main():
    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]" 
    b = [int()] * (N-1)  # type: "List[int]" 
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
n = int(input())
arr = [0] * 200200
for i in range(n - 1):
    a,b = map(int,input().split())
    arr[a] += 1
    arr[b] += 1
res = n
for i in range(n + 10):
    res ^= arr[i]
print('First' if res % 2 else 'Second')

Submission status: Wrong Answer

Solution code:
def solve():
  n = int(input())
  a = [0]*n
  for i in range(n-1):
    c,d = (int(i) for i in input().split())
    a[c-1] += 1
    a[d-1] += 1
  od = 0
  ev = 0
  for i in range(n):
     if a[i]%2 == 0:
          ev += 1
     else:
          od += 1
  if (n+od)%2 == 1:
    print("First")
  else:
    print("Second")
solve()

Submission status: Wrong Answer

Solution code:
def getlist():
	return list(map(int, input().split()))

N = int(input())
for i in range(N - 1):
	a, b = getlist()


if N % 2 == 1:
	print("First")
else:
	print("Second")

Submission status: Wrong Answer

Solution code:
print('First')

Submission status: Wrong Answer

Solution code:
print("First")

Submission status: Wrong Answer

Solution code:
n=int(input())
for i in range(n-1):
  a,b=map(int,input().split())
if n%2==1:print('First')
else:print('Second')

Submission status: Wrong Answer

Solution code:
n = int(input())
if n%2 == 0:
  print("Second")
else:
  print("First")

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[0 for i in range(n)]
ct=0
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1]+=1
  l[b-1]+=1
if max(l)<4:print('First')
else:print('Second')

Submission status: Wrong Answer

Solution code:
n=int(input())
l=[0 for i in range(n)]
ct=0
for i in range(n-1):
  a,b=map(int,input().split())
  l[a-1]+=1
  l[b-1]+=1
for i in range(n):
  if l[i]%2==0:ct+=1
if ct%2==1:print('First')
else:print('Second')

Submission status: Wrong Answer

Solution code:
N = int(input())
A = [list(map(int,input().split())) for i in range(N-1)]
if N % 2 != 0 :
    print("First")
else :
    print("Second")

Submission status: Wrong Answer

Solution code:
n=int(input())
for i in range(n-1):
  input()
if n%2==0:
  print('Second')
else:
  print('First')