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:
import sys
input = sys.stdin.readline
from collections import deque
import marshal


class Graph:
    def __init__(self, n, directed=False, decrement=True, destroy=False, edges=[]):
        self.n = n
        self.directed = directed
        self.decrement = decrement
        self.destroy = destroy
        self.edges = [set() for _ in range(self.n)]
        self.parent = [-1]*self.n
        self.info = [-1]*self.n
        for x, y in edges:
            self.add_edge(x,y)

    def add_edge(self, x, y):
        if self.decrement:
            x -= 1
            y -= 1
        self.edges[x].add(y)
        if self.directed == False:
            self.edges[y].add(x)

    def add_adjacent_list(self, i, adjacent_list):
        if self.decrement:
            self.edges[i] = set(map(lambda x: x - 1, adjacent_list))
        else:
            self.edges[i] = set(adjacent_list)

    def bfs(self, start=1, goal=-1, time=0, save=False):
        """
        :param start: スタート地点
        :param goal: ゴール地点
        :param save: True = 前回の探索結果を保持する
        :return: （ループがあっても）最短距離。存在しなければ -1
        """
        if self.decrement:
            start -= 1
            goal -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, time
        self.parent[p] = -2
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                if q == goal:
                    return t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return -1

    def connection_counter(self):
        """
        :return: 連結成分の個数。有効グラフではあまり意味がない。
        """
        cnt = 0
        self.parent = [-1] * self.n
        for start in range(self.n):
            if self.parent[start] == -1:
                cnt += 1
                self.bfs(start + self.decrement, save=True)
        return cnt

    def distance_list(self, start=1, save=False):
        """
        :param start: スタート地点
        :return: スタート地点から各点への距離のリスト
        """
        dist = [-1]*self.n
        if self.decrement:
            start -= 1
        if not save:
            self.parent = [-1] * self.n
        p, t = start, 0
        self.parent[p] = -2
        dist[p] = 0
        next_set = deque([(p, t)])

        while next_set:
            p, t = next_set.popleft()
            for q in self.edges[p]:
                if self.parent[q] != -1:
                    continue
                dist[q] = t + 1
                self.parent[q] = p
                next_set.append((q, t + 1))
        return dist

    def path_list(self, start=1):
        """
        :return: スタート地点から最短経路で進んだ時の、各頂点の一個前に訪問する頂点番号
                訪問しない場合は -1 を返す
        """
        self.distance_list(start)
        if self.decrement:
            start -= 1
        return list(p + self.decrement for p in self.parent[1:])

    def most_distant_point(self, start=1, save=False):
        """
        計算量　O(N)
        :return: (start から最も遠い頂点, 距離)
        """
        if not save:
            self.parent = [-1] * self.n
        res = (start - self.decrement, 0)
        temp = 0
        for i, dist in enumerate(self.distance_list(start, save=save)):
            if dist > temp:
                temp = dist
                res = (i + self.decrement, dist)
        return res

    def diameter(self, save=False):
        """
        計算量　O(N)
        :return:　木の直径（最も離れた二頂点間の距離）を返す
        """
        if not save:
            self.parent = [-1] * self.n
        p = self.most_distant_point(save=save)
        res = self.most_distant_point(start=p[0], save=save)
        return res[1]



##################################################################################################

N = int(input())
M = N-1
graph = Graph(N, directed=False, decrement=True, destroy=False)
for _ in range(M):
    x, y = map(int, input().split())
    graph.add_edge(x, y)

print("First" if graph.diameter()%3==2 else "Second")

Submission status: Wrong Answer

Solution code:
import sys
from collections import *
import heapq
import math
import bisect
from itertools import permutations
from itertools import accumulate
from fractions import gcd
def input():
    return sys.stdin.readline()[:-1]
def rinsetsudic(lst):
    dic=defaultdict(list)
    for a,b in lst:
        dic[a].append(b)
        dic[b].append(a)
    return dic
mod=10**9+7

n=int(input())
ab=[list(map(int,input().split())) for i in range(n-1)]

F,S="First","Second"

dic=rinsetsudic(ab)
# print(dic)
cnt=0
for i in range(n):
    if len(dic[i+1])==1:
        itta=[0]*(n+1)
        d=deque([(i+1,0)])
        while d:
            now=d.popleft()
            if itta[now[0]]==1:
                continue
            itta[now[0]]=1
            cnt=now[1]
            for j in dic[now[0]]:
                d.append((j,now[1]+1))
        break
# print(cnt)
if cnt%3==1:
    print(S)
else:
    print(F)

Submission status: Wrong Answer

Solution code:
n=int(input())
tr=[[] for _ in range(n)]
for _ in range(n-1):
    x,y=map(int,input().split())
    x,y=x-1,y-1
    tr[x].append(y)
    tr[y].append(x)
from collections import deque
seen=[-1]*n
todo=deque([0])
while todo:
    v=todo.popleft()
    seen[v]=1
    for nv in tr[v]:
        if seen[nv]==-1:
            todo.append(nv)
v0=v
seen=[-1]*n
todo=deque([v])
seen[v]=0
while todo:
    v=todo.popleft()
    for nv in tr[v]:
        if seen[nv]==-1:
            todo.append(nv)
            seen[nv]=seen[v]+1
c=seen[v]
c+=1
if c%3==2:
    print('Secound')
else:
    print('First')

Submission status: Wrong Answer

Solution code:
#Solve this by Rerooting
import sys
from itertools import accumulate
input = sys.stdin.buffer.readline

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


dfs_order = []
parent = [-1] * N
root = 0
stack = [root]
while stack:
    node = stack.pop()
    dfs_order.append(node)
    for next_node in adj[node]:
        if next_node != parent[node]:
            parent[next_node] = node
            stack.append(next_node)

dp1 = [1] * N
for node in reversed(dfs_order):
    for next_node in adj[node]:
        if next_node != parent[node]:
            dp1[node] = max(dp1[node], dp1[next_node] + 1)

dp2 = [1] * N
for node in dfs_order:
    around = [dp1[next_node] if next_node != parent[node] else dp2[node] for next_node in adj[node]]
    from_left = [1] + list(accumulate(around, max))
    from_right = list(accumulate(reversed(around), max))[-2::-1] + [1]
    without = [max(l, r) for l, r in zip(from_left, from_right)]
    for next_node, value in zip(adj[node], without):
        if next_node != parent[node]:
            dp2[next_node] = value + 1

dp = [max(v1, v2) + 1 for v1, v2 in zip(dp1, dp2)]

length = max(dp)

if length % 3 == 2:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

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

from collections import deque
def bfs(s):
    dist = [None]*n
    que = deque([s])
    dist[s] = 0
    while que:
        v = que.popleft()
        d = dist[v]
        for w in link[v]:
            if dist[w] is not None:
                continue
            dist[w] = d + 1
            que.append(w)
    d = max(dist)
    return dist.index(d), d
u, _ = bfs(0)
v, d = bfs(u)

if (d-2)%3!=0:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
n = int(input())

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

d = [-1]*n
d[0] = 0
stack = [0]
m = [0,-1]
while stack:
    p = stack.pop()
    if m[0] < d[p]:
        m[0] = d[p]
        m[1] = p 
    for nxt in path[p]:
        if d[nxt] == -1:
            d[nxt] = d[p] + 1
            stack.append(nxt)

d = [-1]*n
d[m[1]] = 0
stack = [m[1]]
m = 0
while stack:
    p = stack.pop()
    m = max(m,d[p])
    for nxt in path[p]:
        if d[nxt] == -1:
            d[nxt] = d[p] + 1
            stack.append(nxt)
m += 1
dp = [-1]*(m+1)
dp[0] = 0
dp[1] = 1
for i in range(2,m+1):
    dp[i] = 1 - min(dp[i-1],dp[i-2])
if 1 - dp[m]:
    print('First')
else:
    print('Second')

Submission status: Wrong Answer

Solution code:
import sys
import queue
from heapq import nlargest

input = sys.stdin.buffer.readline
INF = 10 ** 9

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

#find the longest path by trying BFS for several starts.
starts = [i for i in range(N) if len(path[i]) == 1]

q = queue.Queue()
depth = [INF] * N
for start in starts:
    q.put(start)
    depth[start] = 1

while not q.empty():
    node = q.get()
    for next_node in path[node]:
        if depth[next_node] > depth[node] + 1:
            depth[next_node] = depth[node] + 1
            q.put(next_node)
        
length = sum(nlargest(2, depth))

if length % 3 == 2:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
import sys
import queue

input = sys.stdin.buffer.readline
INF = 10 ** 9

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

#find the longest path by trying BFS for several starts.
starts = [i for i in range(N) if len(path[i]) == 1]

q = queue.Queue()
depth = [INF] * N
for start in starts:
    q.put(start)
    depth[start] = 0

max_depth = 0
max_num = 0
while not q.empty():
    node = q.get()
    for next_node in path[node]:
        if depth[next_node] > depth[node] + 1:
            depth[next_node] = depth[node] + 1
            q.put(next_node)
            if depth[next_node] > max_depth:
                max_depth = depth[next_node]
                max_num = 1
            elif depth[next_node] == max_depth:
                max_num += 1

length = max_depth * 2 + max_num

if length % 3 == 2:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
def distance_from(x, N, adj):
    ret = [-1] * N
    ret[x] = 0
    q = [x]
    while len(q):
        cur = q.pop()
        for nxt in adj[cur]:
            if ret[nxt] != -1:
                continue
            ret[nxt] = ret[cur] + 1
            q.append(nxt)
    return ret


def main():
    N = int(input())
    adj = [set() for _ in range(N)]
    for _ in range(N-1):
        a, b = map(int, input().split())
        adj[a-1].add(b-1)
        adj[b-1].add(a-1)
    dist = distance_from(0, N, adj)
    idx = 0
    for i in range(N):
        if dist[i] > idx:
            idx = i
    diameter = max(distance_from(idx, N, adj))
    if diameter % 3 == 1:
        print("Second")
    else:
        print("First")


if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
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)

# 木の直径を求める
start = 0
for i in range(N):
  if len(tree[i]) == 1: # リーフ
    start = i
    break

dist = [0] * N
d = [[start, -1]]
while d:
  node, par = d.pop()
  children = tree[node]
  for child in children:
    if child == par:
      continue
    dist[child] = dist[node] + 1
    d.append([child, node])

R = max(dist) + 1
if (R+1) % 3 == 0:
  print('Second')
else:
  print('First')

Submission status: Wrong Answer

Solution code:
from collections import deque
import sys
sys.setrecursionlimit(10**6)
n = int(input())
adjacent_list = [[] for i in range(n+1)]
for i in range(n-1):
    a,b = map(int, input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
dist = [0 for i in range(n+1)]
def bfs(node,pre_node):
    que = deque([(node, pre_node)])
    while que:
        node, pre_node = que.popleft()
        for i in adjacent_list[node]:
            if i != pre_node:
                dist[i] = dist[node] + 1
                que.append([i,node])
bfs(1,0)
index = dist.index(max(dist))
dist = [0 for i in range(n+1)]
bfs(index,0)
print(dist)
l = max(dist)
#一回の操作というのは,木の直径を1or2減らすことになる
if l % 3 != 1:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
N=int(input())

L=[[]for i in range(N+1)]
for i in range(N-1):
    a,b=map(int,input().split())
    L[a].append(b)
    L[b].append(a)
#print(L)
C=[0 for i in range(N+1)]

D=[10000 for i in range(N+1)]
D[1]=0
Q=[1]
for i in range(10**6):
    if i==N:
        break
    for j in L[Q[i]]:
        if D[j]==10000:
            Q.append(j)
            D[j]=D[Q[i]]+1
#print(D)
F=0
cnt=0
for i in range(1,N+1):
    if D[i]>cnt:
        cnt=D[i]
        F=i
d=[10000 for i in range(N+1)]
d[F]=0
Q=[F]
for i in range(10**6):
    if i==N:
        break
    for j in L[Q[i]]:
        if d[j]==10000:
            Q.append(j)
            d[j]=d[Q[i]]+1
#print(d)
ans=0
for i in range(1,N+1):
    if d[i]>ans:
        ans=d[i]
if ans%3==1:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
def dfs(root):
  dist = [-1]*(n+1)
  dist[root] = 0
  stack = [root]
  while stack:
    x = stack.pop()
    for y in graph[x]:
      if dist[y] == -1:
        dist[y] = dist[x]+1
        stack.append(y)
  return dist
d = dfs(1)
far = d.index(max(d))
diam = max(dfs(far))
if diam%3:
  print("First")
else:
  print("Second")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
n = int(input())
ab = [list(map(int,input().split())) for i in range(n-1)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
def dfs(root):
  dist = [-1]*(n+1)
  dist[root] = 0
  stack = [root]
  while stack:
    x = stack.pop()
    for y in graph[x]:
      if dist[y] == -1:
        dist[y] = dist[x]+1
        stack.append(y)
  return dist
d = dfs(1)
far = d.index(max(d))
diam = max(dfs(far))
if diam%4 in (1,2):
  print("First")
else:
  print("Second")

Submission status: Wrong Answer

Solution code:
from collections import deque


def dfs(start, graph):
    n = len(graph)
    dist = [-1] * n
    dist[start] = 0
    q = deque([start])
    while q:
        v = q.pop()
        for nxt_v, cost in graph[v]:
            if dist[v] != -1:
                continue
            dist[nxt_v] = d + dist[v]
            q.append(nxt_v)
    d = max(dist)
    return dist.index(d), d

def tree_diameter(graph):
    ind, _ = dfs(0, graph)
    ind2, d = dfs(ind, graph)
    return d

n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
graph = [[] for i in range(n)]
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    cost = 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))
 
 
if tree_diameter(graph) % 3 == 1:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

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

N = int(input())
edges = [[] for _ in range(N)]

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

def calcDist(fr):
    minDist = [10**18] * N
    que = deque([(fr, 0)])

    while que:
        now, dist = que.pop()

        if minDist[now] < dist:
            continue
        minDist[now] = dist

        for to in edges[now]:
            if minDist[to] > dist + 1:
                minDist[to] = dist + 1
                que.append((to, dist + 1))

    return minDist

D0 = calcDist(0)
R = max(calcDist(D0.index(max(D0)))) + 1

print('First' if R % 3 == 0 else 'Second')

Submission status: Wrong Answer

Solution code:
print("SFeicrosntd"[int(input())%2::2])

Submission status: Wrong Answer

Solution code:
n,*L=map(int,open(0).read().split())
con=[[]for _ in range(n)]
for a,b in zip(*[iter(L)]*2):
	con[a-1].append(b-1)
	con[b-1].append(a-1)
dist=[-1]*n
dist[0]=0
farthest=0
q=[0]
while q:
	cur=q.pop()
	for nxt in con[cur]:
		if dist[nxt]<0:
			dist[nxt]=dist[cur]+1
			if dist[farthest]>dist[nxt]:
				farthest=nxt
			q.append(nxt)
dist=[-1]*n
dist[farthest]=0
diameter=0
q=[farthest]
while q:
	cur=q.pop()
	for nxt in con[cur]:
		if dist[nxt]<0:
			dist[nxt]=dist[cur]+1
			diameter=max(diameter,dist[nxt])
			q.append(nxt)
print("Second" if diameter%3==1 else "First")

Submission status: Wrong Answer

Solution code:
n,*L=map(int,open(0).read().split())
con=[[]for _ in range(n)]
for a,b in zip(*[iter(L)]*2):
	con[a-1].append(b-1)
	con[b-1].append(a-1)
dist=[-1]*n
dist[0]=0
farthest=0
q=[0]
while q:
	cur=q.pop()
	for nxt in con[cur]:
		if dist[nxt]<0:
			dist[nxt]=dist[cur]+1
			farthest=max(farthest,dist[nxt])
			q.append(nxt)
dist=[-1]*n
dist[farthest]=0
diameter=0
q=[farthest]
while q:
	cur=q.pop()
	for nxt in con[cur]:
		if dist[nxt]<0:
			dist[nxt]=dist[cur]+1
			diameter=max(diameter,dist[nxt])
			q.append(nxt)
print("Second" if diameter%3==1 else "First")

Submission status: Wrong Answer

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

def main():
    N = int(input())
    if N == 1:
        print("First")
        exit()
    edge = [[] for _ in range(N)]
    
    for _ in range(N-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        
    for i in range(N):
        if len(edge[i]) == 1:
            st = i
            break
    dep = [-1 for _ in range(N)]
    dep[st] = 0
    
    q = deque([st])
    while q:
        now = q.popleft()
        for fol in edge[now]:
            if dep[fol] == -1:
                dep[fol] = dep[now]+1
                q.append(fol)
    
    if max(dep)%3 == 1:
        print("Second")
    else:
        print("First")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

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

def main():
    N = int(input())
    if N == 1:
        print("First")
        exit()
    edge = [[] for _ in range(N)]
    
    for _ in range(N-1):
        a,b = map(int,input().split())
        edge[a-1].append(b-1)
        edge[b-1].append(a-1)
        
    for i in range(N):
        if len(edge[i]) == 1:
            st = i
            break
    dep = [-1 for _ in range(N)]
    dep[st] = 0
    
    q = deque([st])
    while q:
        now = q.pop()
        for fol in edge[now]:
            if dep[fol] == -1:
                dep[fol] = dep[now]+1
                q.append(fol)
    
    if max(dep)%3 == 1:
        print("Second")
    else:
        print("First")

if __name__ == "__main__":
    main()

Submission status: Wrong Answer

Solution code:
import sys
from collections import defaultdict as dd
input = sys.stdin.readline
N = int(input())
e = dd(list)
if N == 1:
  print("First")
  exit(0)
for _ in range(N - 1):
  u, v = map(int, input().split())
  e[u].append((v, 1))
  e[v].append((u, 1))
import heapq
class dijkstra:
  def __init__(self, n, e):
    self.e = e
    self.n = n
  def path(self, s, t):
    d = [float("inf")] * (self.n + 1)
    vis = set()
    d[s] = 0
    h = [s]
    while not t in vis and len(h):
      v = heapq.heappop(h)
      v1 = v % (10 ** 6)
      v0 = v // (10 ** 6)
      if v1 in vis: continue
      vis.add(v1)
      for p in self.e[v1]:
        d[p[0]] = min(d[p[0]], d[v1] + p[1])
        if p[0] in vis: continue
        heapq.heappush(h, d[p[0]] * (10 ** 6) + p[0])
    return d
dij = dijkstra(N, e)
s = 0
d = 0
p = dij.path(1, 0)
for i in range(1, N + 1):
  if p[i] > d:
    s = i
    d = p[i]
p = dij.path(s, 0)
mx = max(p[1: ])
dp = [-1] * (mx + 1)
dp[0] = 1
for i in range(mx):
  if i + 1 <= mx:
    if dp[i + 1] == -1 or (dp[i + 1] == ((dp[i] + 1) % 2)):
      dp[i + 1] = (dp[i] + 1) % 2
  if i + 2 <= mx:
    if dp[i + 2] == -1 or (dp[i + 2] == ((dp[i] + 1) % 2)):
      dp[i + 2] = (dp[i] + 1) % 2
if dp[-1]: print("Second")
else: print("First")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
N = int(input())
if N % 2: print("First")
else: print("Second")

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
for _ in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

if N == 1:
    print('First')
    exit()

# 葉ではない頂点数を数える
cnt = 0
for i in range(N):
    if len(nodes[i]) != 1:
        cnt += 1
if cnt % 3 != 0:
    print('First')
else:
    print('Second')

Submission status: Wrong Answer

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = 10 ** 19
MOD = 10 ** 9 + 7

N = INT()
nodes = [[] for i in range(N)]
for _ in range(N-1):
    a, b = MAP()
    a -= 1; b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

# 葉ではない頂点数を数える
cnt = 0
for i in range(N):
    if len(nodes[i]) != 1:
        cnt += 1
if cnt % 3 != 0:
    print('First')
else:
    print('Second')

Submission status: Wrong Answer

Solution code:
import sys
from collections import deque

def ni():
    return int(sys.stdin.readline())


def nia():
    data = sys.stdin.readline().split(' ')
    return [int(g) for g in data]

n = ni()
graph = []
for i in range(0, n):
    graph.append([])

for i in range(1, n):
    a, b = nia()
    a = a - 1
    b = b - 1

    graph[a].append(b)
    graph[b].append(a)


q = deque()
q.append(0)
visited = set()
visited.add(0)
last = 0
while not q:
    n = q.popleft()
    last = n
    for nb in graph[n]:
        if nb not in visited:
            visited.add(nb)
            q.append(nb)

diam = 0
visited = set()
next = [(last, 0)]
while next:
    ind, x = next.pop()
    diam = max(diam, x)
    for nb in graph[ind]:
        if nb not in visited:
            visited.add(nb)
            next.append((nb, x + 1))


if (diam + 1) % 3 == 2:
    print 'Second'
else:
    print 'First'

Submission status: Wrong Answer

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

que = [(0, -1, 0)]
Mi, Mv = 0, 0
while que :
  cur, pre, dist = que.pop()
  if dist > Mv :
    Mi, Mv = cur, dist
  for nex in vec[cur] :
    if nex == pre :
      continue
    que.append((nex, cur, dist + 1))

que = [(Mi, -1, 1)]
Mi, Mv = 0, 0
while que :
  cur, pre, dist = que.pop()
  if dist > Mv :
    Mi, Mv = cur, dist
  for nex in vec[cur] :
    if nex == pre :
      continue
    que.append((nex, cur, dist + 1))
    
if Mv == 2 or (Mv != 1 and Mv % 4 == 1) :
  print('Second')
else :
  print('First')

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

def bfs(v0):
    dist = [-1]*N
    que = deque([v0])
    dist[v0] = 0
    while que:
        v = que.pop()
        d = dist[v]
        for nv in edges[v]:
            if dist[nv] < 0:
                que.append(nv)
                dist[nv] = d+1
    m = max(dist)
    v = dist.index(d)
    return v, m
u, _ = bfs(0)
_, dia = bfs(u)
if N == 1:
    print('First')
elif (dia+1-2)%3 == 0:
    print('Second')
else:
    print('First')

Submission status: Wrong Answer

Solution code:
from collections import deque
N = int(input())
edges = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)

def bfs(v0):
    dist = [-1]*N
    que = deque([v0])
    dist[v0] = 0
    while que:
        v = que.pop()
        d = dist[v]
        for nv in edges[v]:
            if dist[nv] < 0:
                que.append(nv)
                dist[nv] = d+1
    m = max(dist)
    v = dist.index(d)
    return v, m
u, _ = bfs(0)
_, dia = bfs(u)
if (dia+1-2)%3 == 0:
    print('Second')
else:
    print('First')

Submission status: Wrong Answer

Solution code:
N = int(input())
E = [[] for _ in range(N)]
for _ in range(N - 1):
  a, b = map(int, input().split())
  E[a - 1].append(b - 1)
  E[b - 1].append(a - 1)
def dijkstra(s):
  D = [-1] * N
  D[s] = s
  Q = [0] * N
  Q[0] = s
  pos = 1
  for i in range(N):
    v = Q[i]
    for adj in E[v]:
      if D[adj] >= 0:
        continue
      Q[pos] = adj
      pos += 1
      D[adj] = D[v] + 1
  return D
D = dijkstra(0)
_, s = max([[D[i], i] for i in range(N)])
D = dijkstra(s)
L = max(D)
print('First' if L % 3 != 1 else 'Second')

Submission status: Wrong Answer

Solution code:
# coding: utf-8
# Your code here!

from collections import deque
def diameter(g):
    def bfs(start): # v からの最長点と距離を求める
        res = [-1]*(len(g))
        q = deque([start])
        res[start] = 0
        while q:
            v = q.popleft()
            for c in g[v]:
                if res[c] >= 0: continue
                res[c] = res[v] + 1 #重みつきのときは+1でなく +cost(v,c)
                q.append(c) 
        return (res[v],v)

    d0,v0 = bfs(0)
    d1,v1 = bfs(v0)
    return d1 # i0, i1 が最遠頂点対


##################################################
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())
#n,q = [int(i) for i in readline().split()]
 
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

d = diameter(g)
if d%3 != 1:
    print("First")
else:
    print("Second")
    
if n==6: print("WA")

Submission status: Wrong Answer

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(pow(10, 6))

edges = []

from collections import deque
def diam_bfs(i):
  que = deque([i])
  dist = {i: 0}
  prev = {i: -1}
  while que:
    u = que.popleft()
    d = dist[u]
    for w in edges[u]:
      if w in dist:
        continue
      dist[w] = d + 1
      prev[w] = u
      que.append(w)
  w = u
  D = []
  while w != -1:
    D.append(w)
    w = prev[w]
  return u, D


def main():
  global edges
  n = int(input())
  edges = [[] for _ in range(n)]
  for _ in range(n-1):
    a, b = map(int, input().split())
    edges[a-1].append(b-1)
    edges[b-1].append(a-1)
  _, path = diam_bfs(diam_bfs(0)[0])
  if len(path) % 3 == 0:
    print('First')
  else:
    print('Second')


if __name__ == '__main__':
  main()

Submission status: Wrong Answer

Solution code:
n=int(input())
p=[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 p]
[g[b-1].append(a-1) for a,b in p]

memo=[False for _ in [0]*n]
q=[0]
memo[0]=True
last=0
while(q):
	qq=[]
	for i in q:
		for j in g[i]:
			if memo[j]==False:
				memo[j]=True
				last=j
				qq.append(j)
	q=qq

memo=[False for _ in [0]*n]
q=[last]
memo[0]=True
cnt=1
while(q):
	cnt+=1
	qq=[]
	for i in q:
		for j in g[i]:
			if memo[j]==False:
				memo[j]=True
				qq.append(j)
	q=qq
	
if cnt%3==2:
	print('Second')
else:
	print('First')

Submission status: Wrong Answer

Solution code:
n=int(input())
p=[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 p]
[g[b-1].append(a-1) for a,b in p]

memo=[False for _ in [0]*n]
q=[0]
memo[0]=True
last=0
while(q):
	qq=[]
	for i in q:
		for j in g[i]:
			if memo[j]==False:
				memo[j]=True
				last=j
				qq.append(j)
	q=qq

memo=[False for _ in [0]*n]
q=[last]
memo[0]=True
cnt=0
while(q):
	cnt+=1
	qq=[]
	for i in q:
		for j in g[i]:
			if memo[j]==False:
				memo[j]=True
				qq.append(j)
	q=qq
	
if cnt%3==2:
	print('Second')
else:
	print('First')

Submission status: Wrong Answer

Solution code:
import queue
n = int(input())

tree = {i: [] for i in range(n)}

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

a = 0
q = queue.Queue()
q.put(a)
v = [0 for _ in range(n)]
v[a] = 1

while (not q.empty()):
    a = q.get()
    for b in tree[a]:
        if (v[b] == 0):
            q.put(b)
            v[b] = 1

s = a
q = queue.Queue()
q.put([a, 0])
v = [0 for _ in range(n)]
v[a] = 1

while (not q.empty()):
    a = q.get()
    for b in tree[a[0]]:
        if (v[b] == 0):
            q.put([b, a[1] + 1])
            v[b] = 1

l = a[1]
if l%3 == 2:
    print("Second")
else:
    print("First")