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: Accepted

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 % 3 != 2 :
  print('First')
else :
  print('Second')

Submission status: Accepted

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

def dfs(p):
  dep = [None]*n
  dep[p] = 0
  q = [p]
  while q:
    v = q.pop()
    for x in l[v]:
      if dep[x] is None:
        dep[x] = dep[v] + 1
        q.append(x)
  return dep
      
dep = dfs(0)
p = dep.index(max(dep))
dep = dfs(p)
q = max(dep)-1
print("First" if q%3 else "Second")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(2147483647)
INF=float("inf")
MOD=10**9+7
input=lambda:sys.stdin.readline().rstrip()
from collections import deque
def resolve():
    n=int(input())
    E=[[] for _ in range(n)]
    for i in range(n-1):
        a,b=map(int,input().split())
        a-=1; b-=1
        E[a].append(b)
        E[b].append(a)

    # double sweepで直径を求める
    dist=[INF]*n
    dist[0]=0
    Q=deque([0])
    while(Q):
        v=Q.popleft()
        for nv in E[v]:
            if(dist[nv]!=INF): continue
            dist[nv]=dist[v]+1
            Q.append(nv)

    v=max((dist[v],v) for v in range(n))[1]
    dist=[INF]*n
    dist[v]=0
    Q=deque([v])
    while(Q):
        v=Q.popleft()
        for nv in E[v]:
            if(dist[nv]!=INF): continue
            dist[nv]=dist[v]+1
            Q.append(nv)

    dia=max(dist)
    print("Second" if(dia%3==1) else "First")
resolve()

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = 10 ** 13
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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 = 10 ** 9 + 7



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


def bfs(root):
    que = deque([root])
    dist = [INF] * n
    dist[root] = 0
    while que:
        u = que.popleft()
        for v in G[u]:
            if dist[u] + 1 < dist[v]:
                dist[v] = dist[u] + 1
                que += [v]
    return dist



def double_sweep():
    dist = bfs(0)
    ret = -1
    for u in range(n):
        if dist[u] > ret:
            ret = dist[u]
            v = u
    return max(bfs(v))



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

Submission status: Accepted

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

def bfs(start):
    checked = [False]*N
    q = [start]
    c = -1
    while q:
        qq = []
        c += 1
        for p in q:
            for np in graph[p]:
                if not checked[np]:
                    checked[np] = True
                    qq.append(np)
        if not qq:
            break
        q = qq
    return c, q

_, q = bfs(0)
d, _ = bfs(q[0])
if d%3 == 1:
    print('Second')
else:
    print("First")

Submission status: Accepted

Solution code:
from collections import deque
import sys

N = int(input())

if N == 1:
    print ("First")
    sys.exit()


dic = {}

for  i in range(N-1):

    a,b = map(int,input().split())
    a-=1
    b-=1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

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

for xxx in range(1):

    lis = [float("inf")] * N
    lis[0] = 0
    maxind = 0
    q = deque([0])

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:

            if lis[nex] > lis[now] + 1:
                lis[nex] = lis[now] + 1
                q.append(nex)
                maxind = nex

    lis = [float("inf")] * N
    lis[maxind] = 1
    q = deque([maxind])
    L = 0

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:

            if lis[nex] > lis[now] + 1:
                lis[nex] = lis[now] + 1
                q.append(nex)
                L = lis[nex]

    #print (lis)
    #print (L)

    if L == 1 or L % 3 != 2:

        print ("First")

    else:

        print ("Second")

Submission status: Accepted

Solution code:
from collections import defaultdict, deque, Counter
from heapq import heappush, heappop, heapify
import math
from bisect import bisect_left, bisect_right
import random
from itertools import permutations, accumulate, combinations
import sys
import string



INF = float('inf')
def LI(): return list(map(int, sys.stdin.readline().split()))
def I(): return int(sys.stdin.readline())
def LS(): return sys.stdin.readline().split()
def S(): return sys.stdin.readline().strip()
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 = 10 ** 9 + 7



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


def bfs(v):
    que = deque([v])
    dist = [INF] * n
    dist[v] = 0
    while que:
        cur = que.popleft()
        for nxt in graph[cur]:
            if dist[cur] + 1 < dist[nxt]:
                dist[nxt] = dist[cur] + 1
                que += [nxt]
    return dist



def double_sweep():
    dist = bfs(0)
    ret = -1
    for i in range(n):
        if dist[i] > ret:
            ret = dist[i]
            u = i
    return max(bfs(u))



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

Submission status: Accepted

Solution code:
n = int(input())
g = [[] for _ in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
s = [0]
d = [-1] * n
d[0] = 0
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            s.append(node)
            d[node] = d[p] + 1
idx = 0
for i in range(n):
    if d[i] > d[idx]:
        idx = i
s = [idx]
d = [-1] * n
d[idx] = 0
while s:
    p = s.pop()
    for node in g[p]:
        if d[node] == -1:
            s.append(node)
            d[node] = d[p] + 1
m = 0
for i in range(n):
    if d[i] > m:
        m = d[i]
if m % 3 == 1:
    print('Second')
else:
    print('First')

Submission status: Accepted

Solution code:

import sys
from collections import deque, defaultdict
import copy
import bisect
sys.setrecursionlimit(10 ** 9)
import math
import heapq
from itertools import product, permutations,combinations
import fractions
from operator import itemgetter

import sys
def input():
	return sys.stdin.readline().strip()

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

que = deque()
que.append(0)
max_length = 0
max_loc = 0
length_list = [100000000]*N
length_list[0] = 0
while len(que) > 0:
	node = que.popleft()
	for node_next in tree[node]:
		if length_list[node_next] > length_list[node]:
			length_list[node_next] = length_list[node] + 1
			if max_length < length_list[node_next]:
				max_length = length_list[node_next]
				max_loc =node_next
			que.append(node_next)

que = deque()
que.append(max_loc)
max_length = 0
length_list = [100000000]*N
length_list[max_loc] = 0
while len(que) > 0:
	node = que.popleft()
	for node_next in tree[node]:
		if length_list[node_next] > length_list[node]:
			length_list[node_next] = length_list[node] + 1
			max_length = max(max_length, length_list[node_next])
			que.append(node_next)
max_length += 1

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

Submission status: Accepted

Solution code:
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while visitct!=n:
    ct+=1
    for i in range(len(next)):
      distance[next[i]]=ct
      visited[next[i]]=1
      visitct+=1
      for j in range(len(connection[next[i]])):
        if visited[connection[next[i]][j]]==-1:
          next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
    
  return distance

n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)
 
if max(bfs(bfs(0).index(max(bfs(0)))))%3==1:
  print('Second')
else:
  print('First')

Submission status: Accepted

Solution code:
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
    
  return distance
 
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)
 
if max(bfs(bfs(0).index(max(bfs(0)))))%3==1:
  print('Second')
else:
  print('First')

Submission status: Accepted

Solution code:
def main():
  def bfs(v):
    distance=[-1]*n
    distance[v]=0
    next=connection[v]
    next2=set()
    visited=[-1]*n
    visited[v]=1
    visitct=1
    ct=0
    while len(next)!=0 and visitct!=n:
      ct+=1
      for i in range(len(next)):
        if visited[next[i]]==-1:
          distance[next[i]]=ct
          visited[next[i]]=1
          visitct+=1
          for j in range(len(connection[next[i]])):
            if visited[connection[next[i]][j]]==-1:
              next2.add(connection[next[i]][j])
      next=list(next2)
      next2=set()
      
    return distance

  n=int(input())
  l=[list(map(int,input().split())) for i in range(n-1)]
  connection=[[] for i in range(n)]
  for i in range(n-1):
    connection[l[i][0]-1].append(l[i][1]-1)
    connection[l[i][1]-1].append(l[i][0]-1)

  if max(bfs(bfs(0).index(max(bfs(0)))))%3==1:
    print('Second')
  else:
    print('First')
if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=set()
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.add(connection[next[i]][j])
    next=list(next2)
    next2=set()
    
  return distance

n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

if max(bfs(bfs(0).index(max(bfs(0)))))%3==1:
  print('Second')
else:
  print('First')

Submission status: Accepted

Solution code:
def bfs(v):
  distance=[-1]*n
  distance[v]=0
  next=connection[v]
  next2=[]
  visited=[-1]*n
  visited[v]=1
  visitct=1
  ct=0
  while len(next)!=0 and visitct!=n:
    ct+=1
    for i in range(len(next)):
      if visited[next[i]]==-1:
        distance[next[i]]=ct
        visited[next[i]]=1
        visitct+=1
        for j in range(len(connection[next[i]])):
          if visited[connection[next[i]][j]]==-1:
            next2.append(connection[next[i]][j])
    next=next2
    next2=[]
    
  return distance

n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)

if max(bfs(bfs(0).index(max(bfs(0)))))%3==1:
  print('Second')
else:
  print('First')

Submission status: Accepted

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(m)
    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: Accepted

Solution code:
from heapq import heappush, heappop
from collections import deque,defaultdict,Counter
import itertools
from itertools import permutations,combinations
import sys
import bisect
import string
#import math
#import time
#import random
def I():
    return int(input())
def MI():
    return map(int,input().split())
def LI():
    return [int(i) for i in input().split()]
def LI_():
    return [int(i)-1 for i in input().split()]
def StoI():
    return [ord(i)-97 for i in input()]
def show(*inp,end='\n'):
    if show_flg:
        print(*inp,end=end)
YN=['Yes','No']
mo=10**9+7
#ts=time.time()
#sys.setrecursionlimit(10**6)
#input=sys.stdin.readline
show_flg=False
#show_flg=True

n=I()


g=[[] for i in range(1+n)]
v=[-1]*(1+n)

for i in range(n-1):
    a,b=LI_()
    g[a].append(b)
    g[b].append(a)

def dfs(cur,dep):
    mdep=0
    end=cur
    
    q=[]
    q.append((cur,dep))

    while q:
        cur,dep=q.pop()
        v[cur]=dep
        if dep>mdep:
            mdep=dep
            end=cur

        for nb in g[cur]:
            if v[nb]==-1:
                q.append((nb,dep+1))
    return mdep,end
    
dist,end=dfs(0,0)
v=[-1]*(1+n)
diam,beg=dfs(end,0)
show(end,beg,diam)
print(['First','Second'][diam%3==1])

Submission status: Accepted

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] = 0
  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: Accepted

Solution code:
import sys
input=sys.stdin.readline
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)
 
distance1=[-1 for i in range(n)]
distance1[0]=0
next=connection[0]
next2=[]
check=[-1 for i in range(n)]
check[0]=1
checkct=1
ct=0
while len(next)!=0 and checkct!=n:
  ct+=1
  for i in range(len(next)):
    distance1[next[i]]=ct
    check[next[i]]=1
    checkct+=1
    for j in range(len(connection[next[i]])):
      if check[connection[next[i]][j]]==-1:
        next2.append(connection[next[i]][j])
  next=next2
  next2=[]

x=max(distance1)
x=distance1.index(x)

distance2=[-1 for i in range(n)]
distance2[x]=0
next=connection[x]
next2=[]
check=[-1 for i in range(n)]
check[x]=1
checkct=1
ct=0
while len(next)!=0 and checkct!=n:
  ct+=1
  for i in range(len(next)):
    distance2[next[i]]=ct
    check[next[i]]=1
    checkct+=1
    for j in range(len(connection[next[i]])):
      if check[connection[next[i]][j]]==-1:
        next2.append(connection[next[i]][j])
  next=next2
  next2=[]

if max(distance2)%3==1:
  print('Second')
else:
  print('First')

Submission status: Accepted

Solution code:
n=int(input())
l=[list(map(int,input().split())) for i in range(n-1)]
connection=[[] for i in range(n)]
for i in range(n-1):
  connection[l[i][0]-1].append(l[i][1]-1)
  connection[l[i][1]-1].append(l[i][0]-1)
 
distance1=[-1 for i in range(n)]
distance1[0]=0
next=connection[0]
next2=[]
check=[-1 for i in range(n)]
check[0]=1
checkct=1
ct=0
while len(next)!=0 and checkct!=n:
  ct+=1
  for i in range(len(next)):
    distance1[next[i]]=ct
    check[next[i]]=1
    checkct+=1
    for j in range(len(connection[next[i]])):
      if check[connection[next[i]][j]]==-1:
        next2.append(connection[next[i]][j])
  next=next2
  next2=[]

x=max(distance1)
x=distance1.index(x)

distance2=[-1 for i in range(n)]
distance2[x]=0
next=connection[x]
next2=[]
check=[-1 for i in range(n)]
check[x]=1
checkct=1
ct=0
while len(next)!=0 and checkct!=n:
  ct+=1
  for i in range(len(next)):
    distance2[next[i]]=ct
    check[next[i]]=1
    checkct+=1
    for j in range(len(connection[next[i]])):
      if check[connection[next[i]][j]]==-1:
        next2.append(connection[next[i]][j])
  next=next2
  next2=[]

if max(distance2)%3==1:
  print('Second')
else:
  print('First')

Submission status: Accepted

Solution code:
from collections import deque

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


def dfs(adj, start):
    que = deque()
    que.append(start)
    depth = [0] * len(adj)
    visited = [0] * len(adj)
    while que:
        v = que.pop()
        visited[v] = 1
        for u in adj[v]:
            if visited[u] == 0:
                que.append(u)
                depth[u] = depth[v] + 1
    return depth


depth1 = dfs(adj, 1)
temp = 0
max_i = 0
for i, x in enumerate(depth1):
    if x > temp:
        max_i = i
        temp = x
longest_path = max(dfs(adj, max_i)) + 1
if longest_path % 3 == 2:
    print('Second')
else:
    print('First')

Submission status: Accepted

Solution code:
import os
import sys
from collections import deque

if os.getenv("LOCAL"):
    sys.stdin = open("_in.txt", "r")

sys.setrecursionlimit(2147483647)
INF = float("inf")
IINF = 10 ** 18
MOD = 10 ** 9 + 7

N = int(sys.stdin.readline())
AB = [list(map(int, sys.stdin.readline().split())) for _ in range(N - 1)]

graph = [[] for _ in range(N)]
for a, b in AB:
    graph[a - 1].append(b - 1)
    graph[b - 1].append(a - 1)


def max_d(from_v):
    seen = [False] * N
    seen[from_v] = True
    v, d = from_v, 0
    que = deque([(v, d)])
    while que:
        v, d = que.popleft()
        for u in graph[v]:
            if not seen[u]:
                seen[u] = True
                que.append((u, d + 1))
    return v, d


v, _ = max_d(0)
_, diam = max_d(v)
# 直径を 1 か 2 減らせる
# 直径が 1 になったら負け
if diam % 3 == 1:
    print('Second')
else:
    print('First')

Submission status: Accepted

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()
            rv = res[v]
            for c in g[v]:
                if res[c] >= 0: continue
                res[c] = rv + 1 #重みつきのときは+1でなく +cost(v,c)
                q.append(c) 
        return (rv,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")

Submission status: Accepted

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

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

Submission status: Accepted

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

def diameter(g):
    def dfs(v,p): # v からの最長点と距離を求める
        m = 0
        i = v
        for c in g[v]:
            if c == p: continue
            mc,ic = dfs(c,v)
            mc += 1  #重みつきのときは+1でなく +cost(v,c)
            if m < mc:
                m = mc
                i = ic
        return (m,i)

    m0,i0 = dfs(0,-1)
    m1,i1 = dfs(i0,-1)
    # i0, i1 が最遠頂点対
    return m1

##################################################
# 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")

Submission status: Accepted

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 == 2:
    print('Second')
  else:
    print('First')


if __name__ == '__main__':
  main()

Submission status: Accepted

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[last]=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: Accepted

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

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

for _ in range(n-1):
  t = input().split()
  u, v = int(t[0]), int(t[1])
  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 and len(tree[b]) > 1):
            q.put(b)
            v[b] = 1

s = a
q = queue.Queue()
q.put([a, 1])
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 and len(tree[b]) > 1):
            q.put([b, a[1] + 1])
            v[b] = 1

if n <= 3:
    l = n
else:
	l = a[1] + 2

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

Submission status: Accepted

Solution code:
n = int(input())

tree = [[] for i in range(n)]

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

a = 0
idx = 0
q = []
q.append(a)
v = [0 for _ in range(n)]
v[a] = 1

while (idx != len(q)):
    a = q[idx]
    idx += 1
    for b in tree[a]:
        if (v[b] == 0):
            q.append(b)
            v[b] = 1

s = a
idx = 0
q = []
q.append([a, 1])
v = [0 for _ in range(n)]
v[a] = 1

while (idx != len(q)):
    a = q[idx]
    idx += 1
    for b in tree[a[0]]:
        if (v[b] == 0):
            q.append([b, a[1] + 1])
            v[b] = 1

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

Submission status: Accepted

Solution code:
n = int(input())

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

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

a = 0
idx = 0
q = []
q.append(a)
v = [0 for _ in range(n)]
v[a] = 1

while (idx != len(q)):
    a = q[idx]
    idx += 1
    for b in tree[a]:
        if (v[b] == 0):
            q.append(b)
            v[b] = 1

s = a
idx = 0
q = []
q.append([a, 1])
v = [0 for _ in range(n)]
v[a] = 1

while (idx != len(q)):
    a = q[idx]
    idx += 1
    for b in tree[a[0]]:
        if (v[b] == 0):
            q.append([b, a[1] + 1])
            v[b] = 1

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

Submission status: Accepted

Solution code:
import heapq
INF = 10**9

n = int(input())
edge = [[] for _ in range(n)]

class Dijkstra:
    def __init__(self, adj):
        self.adj = adj
        self.num = len(adj)
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def reset(self):
        self.dist = [INF] * self.num
        self.prev = [INF] * self.num
        self.q = []

    def calc(self, start):
        self.dist[start] = 0
        heapq.heappush(self.q, (0, start))
        while len(self.q) != 0:
            prov_cost, src = heapq.heappop(self.q)
            if self.dist[src] < prov_cost:
                continue
            for dest in self.adj[src]:
                cost = 1
                if self.dist[dest] > self.dist[src] + cost:
                    self.dist[dest] = self.dist[src] + cost
                    heapq.heappush(self.q, (self.dist[dest], dest))
                    self.prev[dest] = src
        return self.dist 

for i in range(n-1):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

dij = Dijkstra(edge)
dist = dij.calc(0)
left = dist.index(max(dist))
dij.reset()
dist = dij.calc(left)
diam = max(dist)
if diam % 3 == 1:
    print("Second")
else:
    print("First")

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
# グラフの最長経路が-1か-2かを選べる
N = int(input())
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)


def f(x):
  opposite = 0
  max_dist = 0
  # 最離点と距離とを返す
  d = [None]*N
  q = [(x,0)]
  while q:
    x,dx = q.pop()
    d[x] = dx
    if dx > max_dist:
      max_dist = dx
      opposite = x
    for y in edge[x]:
      if d[y] is None:
        q.append((y,dx+1))
  return opposite,max_dist

if N != 1:
  # 0からの距離
  v,_ = f(0)
  _,max_dist = f(v)

  ans = 'First' if max_dist%3 != 1 else 'Second'
  print(ans)
else:
  print('First')

Submission status: Accepted

Solution code:
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    # graph[node] = [(cost, to)]
    inf = float('inf')
    dist = [inf]*node

    dist[start] = 0
    heap = [(0,start)]
    while heap:
        cost,thisNode = heappop(heap)
        for NextCost,NextNode in graph[thisNode]:
            dist_cand = dist[thisNode]+NextCost
            if dist_cand < dist[NextNode]:
                dist[NextNode] = dist_cand
                heappush(heap,(dist[NextNode],NextNode))
    return dist

N = int(input())

g = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    a -= 1
    b -= 1
    g[a].append((1,b))
    g[b].append((1,a))
d = dijkstra(g,N,0)
r = 0
n = 0
for i in range(N):
    if r < d[i]:
        r = d[i]
        n = i
r = max(dijkstra(g,N,n))
if r%3==0 or r%3==2:
    print('First')
else:
    print('Second')

Submission status: Accepted

Solution code:
from collections import*
def s(s):
  f,q=[1]*-~n,deque([(s,0)])
  while q:
    t,c=q.popleft()
    for v in e[t]:
      q+=[(v,c+1)]*f[v]
      f[v]=0
  return t,c
n,*t=map(int,open(0).read().split())
e=[[]for _ in[0]*-~n]
for a,b in zip(t[::2],t[1::2]):
  e[a]+=b,
  e[b]+=a,
print('SFeicrosntd'[s(s(1)[0])[1]%3!=1::2])

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(250000)
def s(x,v,d):
  r=[d,v]
  for u in g[v]:
    if u!=x:
      t=s(v,u,d+1)
      if r[0]<t[0]:r=t
  return r
n,*t=map(int,open(0).read().split())
g=[[]for _ in range(n+1)]
for a,b in zip(t[::2],t[1::2]):
  g[a].append(b)
  g[b].append(a)
print('SFeicrosntd'[s(0,s(0,1,0)[1],0)[0]%3!=1::2])