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

Solution (Python):
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')

Solution (Python):
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')

Solution (Python):
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')

Solution (Python):
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')

Solution (Python):
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)


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

Solution (Python):



from collections import deque
def diameter(g):
    def bfs(start): 
        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 
                q.append(c) 
        return (rv,v)

    d0,v0 = bfs(0)
    d1,v1 = bfs(v0)
    return d1 





import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())

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

Solution (Python):



from collections import deque
def diameter(g):
    def bfs(start): 
        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)) 
        return (d,v)

    d0,v0 = bfs(0)
    d1,v1 = bfs(v0)
    return d1 





import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())

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

Solution (Python):



def diameter(g):
    def dfs(v,p): 
        m = 0
        i = v
        for c in g[v]:
            if c == p: continue
            mc,ic = dfs(c,v)
            mc += 1  
            if m < mc:
                m = mc
                i = ic
        return (m,i)

    m0,i0 = dfs(0,-1)
    m1,i1 = dfs(i0,-1)
    
    return m1




import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())

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

Solution (Python):
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()

Solution (Python):
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')

Solution (Python):
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")

Solution (Python):
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")

Solution (Python):
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")

Solution (Python):
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")

Solution (Python):
import sys
sys.setrecursionlimit(10**6)

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:
  
  v,_ = f(0)
  _,max_dist = f(v)

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

Solution (Python):
from heapq import heappush, heappop
def dijkstra(graph:list, node:int, start:int) -> list:
    
    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')

Solution (Python):
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])

Solution (Python):
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])

Solution (Python):
import sys, collections
def single_input(F): return F.readline().strip("\n")
def line_input(F): return F.readline().strip("\n").split()

def bfs(initialnode, edge, nodeNum):
    visited = [False] * nodeNum
    dist = []
    search_que = collections.deque()
    search_que.append((0, initialnode))
    count = 0
    while count < nodeNum:
        nowDist, nowNode = search_que.popleft()
        if not visited[nowNode]:
            visited[nowNode] = True
            dist.append((nowDist, nowNode))
            count += 1
            for nextNode in edge[nowNode]:
                if not visited[nextNode]:
                    search_que.append((nowDist+1, nextNode))
    return dist[-1]

def solve():
    F = sys.stdin
    N = int(single_input(F))
    Edge = [[] for i in range(N)]
    for _ in range(N-1):
        a, b = map(int, line_input(F))
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)

    most_far_from_zero = bfs(0, Edge, N)
    tree_d, node_on_otherside = bfs(most_far_from_zero[1], Edge, N)

    if tree_d % 3 == 1: print("Second")
    else: print("First")
    return 0
  
if __name__ == "__main__":
    solve()

Solution (Python):
import sys, math, collections, heapq, itertools
sys.setrecursionlimit(100000000)
F = sys.stdin
def single_input(): return F.readline().strip("\n")
def line_input(): return F.readline().strip("\n").split()
def gcd(a, b):
    a, b = max(a, b), min(a, b)
    while a % b > 0: a, b = b, a % b
    return b

def bfs(initialnode, edge, nodeNum):
    visited = [False] * nodeNum
    dist = []
    search_que = collections.deque()
    search_que.append((0, initialnode))
    count = 0
    while count < nodeNum:
        nowDist, nowNode = search_que.popleft()
        if not visited[nowNode]:
            visited[nowNode] = True
            dist.append((nowDist, nowNode))
            count += 1
            for nextNode in edge[nowNode]:
                if not visited[nextNode]:
                    search_que.append((nowDist+1, nextNode))
    return dist[-1]


def solve():
    N = int(single_input())
    Edge = [[] for i in range(N)]
    for _ in range(N-1):
        a, b = map(int, line_input())
        Edge[a-1].append(b-1)
        Edge[b-1].append(a-1)

    most_far_from_zero = bfs(0, Edge, N)
    tree_d, node_on_otherside = bfs(most_far_from_zero[1], Edge, N)

    if tree_d % 3 == 1: print("Second")
    else: print("First")
    return 0
  
if __name__ == "__main__":
    solve()

Solution (Python):
N = int(input())
A = [[] for i in range(N)]
for n in range(N-1):
    a,b = map(int, input().split())
    A[a-1].append(b-1)
    A[b-1].append(a-1)



from collections import deque
def dfs(node):
    st = deque()
    push, pop = st.append, st.popleft
    push(node)
    cnt = [0]*N
    cnt[node] = 1
    while st:
        now = pop()
        for n in A[now]:
            if cnt[n] == 0:
                push(n)
            cnt[n] = 1
    return now

def dfs_L(node):
    st = deque()
    push, pop = st.append, st.popleft
    push([node,0])
    cnt = [0]*N
    cnt[node] = 1
    L_list = []
    while st:
        [now,L] = pop()
        L_list.append(L)
        for n in A[now]:
            if cnt[n] == 0:
                push([n,L+1])
            cnt[n] = 1
    return max(L_list)
            

step1 = dfs(0)
length = dfs_L(step1)
if length%3 == 1:
    print('Second')
else:
    print('First')

Solution (Python):
N = int(input())
A = [[] for i in range(N)]
for n in range(N-1):
    a,b = map(int, input().split())
    A[a-1].append(b-1)
    A[b-1].append(a-1)



from collections import deque
def dfs(node):
    st = deque()
    push, pop = st.append, st.popleft
    push(node)
    cnt = [0]*N
    cnt[node] = 1
    while st:
        now = pop()
        for n in A[now]:
            if cnt[n] == 0:
                push(n)
            cnt[n] = 1
    return now

def dfs_L(node):
    st = deque()
    push, pop = st.append, st.popleft
    push([node,0])
    cnt = [0]*N
    cnt[node] = 1
    L_list = []
    while st:
        [now,L] = pop()
        L_list.append(L)
        for n in A[now]:
            if cnt[n] == 0:
                push([n,L+1])
            cnt[n] = 1
    return max(L_list)
            

step1 = dfs(0)
length = dfs_L(step1)
if length%3 == 1:
    print('Second')
else:
    print('First')

Solution (Python):
from collections import defaultdict

N = int(input())
abList = [list(map(int, input().split())) for _ in range(N-1)]


treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)


costDict = defaultdict(int)
treeQ = set()


for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])




node = 1
while(treeQ):
    tQ = set()
    costList = []
    for node in treeQ:
        if costDict[node] != 0: break
        decidedFlg = True
        cost = -1
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            if nextCost == 0:
                
                
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                
                cost = max(cost, nextCost + 1)

        if cost != -1:
            costList.append((node, cost))
        if qNode != -1:
            tQ.add(qNode)

    for cost in costList:
        costDict[cost[0]] = cost[1]
    treeQ = tQ



firstLen, secondLen = 0, 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

diameter = firstLen + secondLen + 1
ans = "First" if diameter % 3 != 2 else "Second"
print(ans)

Solution (Python):
from collections import defaultdict
import sys
input = sys.stdin.readline


N = int(input())

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

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

def longest_path(tree, from_node=1):
    cnt = 1

    nearest_nodes = list(tree[from_node])
    while len(nearest_nodes) > 0:
        for one_step_node in nearest_nodes:
            for two_step_node in tree[one_step_node]:
                if two_step_node != from_node:
                    tree[two_step_node].remove(one_step_node)
                    tree[two_step_node].add(from_node)
                    tree[from_node].add(two_step_node)
            tree[from_node].remove(one_step_node)
        cnt += 1
        nearest_nodes = list(tree[from_node])

    return one_step_node, cnt


far, _ = longest_path(tree)
_, n = longest_path(tree_main, far)
print("Second" if n % 3 == 2 else "First")

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

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

Solution (Python):
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)

def farthest_node_and_dist(s):
    dist = [N]*N
    dist[s] = 0
    stack = [s]
    ret_node = -1
    ret_dist = 0
    while stack:
        v = stack.pop()
        d = dist[v]
        for to in es[v]:
            if d+1 < dist[to]:
                dist[to] = d+1
                stack.append(to)
                if ret_dist < d+1:
                    ret_dist = d+1
                    ret_node = to
    return (ret_node, ret_dist)

n,d = farthest_node_and_dist(0)
n,d = farthest_node_and_dist(n)
print('Second' if d%3==1 else 'First')

Solution (Python):
def diameter(N, E):
    from collections import deque
    V = [-1]*N
    V[0] = 0
    q = deque([0])
    while q:
        v = q.popleft()
        for w in E[v]:
            if V[w] == -1:
                V[w] = V[v] + 1
                q.append(w)
    s = V.index( max(V))
    p = deque([s])
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.popleft()
        for w in E[v]:
            if W[w] == -1:
                W[w] = W[v] + 1
                p.append(w)
    return max(W)

N = int( input())
E = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    E[a].append(b)
    E[b].append(a)
ans = "First"
if diameter(N, E)%3 == 1:
    ans = "Second"
print( ans)

Solution (Python):
def diameter(N, E):
    from collections import deque
    V = [-1]*N
    V[0] = 0
    q = deque([0])
    
    while q:
        v = q.popleft()
        for w in E[v]:
            if V[w] == -1:
                
                V[w] = V[v] + 1
                q.append(w)
    s = V.index( max(V))
    p = deque([s])
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.popleft()
        for w in E[v]:
            if W[w] == -1:
                W[w] = W[v] + 1
                p.append(w)
    return max(W)

N = int( input())
E = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    E[a].append(b)
    E[b].append(a)
ans = "First"
if diameter(N, E)%3 == 1:
    ans = "Second"
print( ans)

Solution (Python):
from collections import deque
def diameter(N, E):
    V = [-1]*N
    V[0] = 0
    q = deque([0])
    
    while q:
        v = q.popleft()
        for w in E[v]:
            if V[w] == -1:
                
                V[w] = V[v] + 1
                q.append(w)
    s = V.index( max(V))
    p = deque([s])
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.popleft()
        for w in E[v]:
            if W[w] == -1:
                W[w] = W[v] + 1
                p.append(w)
    return max(W)

N = int( input())
E = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    E[a].append(b)
    E[b].append(a)
ans = "First"
if diameter(N, E)%3 == 1:
    ans = "Second"
print( ans)

Solution (Python):
from collections import deque
def diameter(N, E):
    V = [-1]*N
    V[0] = 0
    q = deque([0])
    s = 0
    while q:
        v = q.popleft()
        for w in E[v]:
            if V[w] == -1:
                s = w
                V[w] = V[v] + 1
                q.append(w)
    
    p = deque([s])
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.popleft()
        for w in E[v]:
            if W[w] == -1:
                W[w] = W[v] + 1
                p.append(w)
    return max(W)

N = int( input())
E = [ [] for _ in range(N)]
for _ in range(N-1):
    a, b = map( int, input().split())
    a, b = a-1, b-1
    E[a].append(b)
    E[b].append(a)
ans = "First"
if diameter(N, E)%3 == 1:
    ans = "Second"
print( ans)

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

def bfs(i):
    global depth
    depth = [0] * N
    s = [i]
    depth[i] = 1
    while s:
        v = s.pop()
        for u in adj[v]:
            if not depth[u]:
                depth[u] = depth[v] + 1
                s.append(u)

bfs(0)
i = depth.index(max(depth))
bfs(i)

print('Second' if max(depth) % 3 == 2 else 'First')

Solution (Python):
from collections import deque

def getDiameter(adjList):
    def bfs(vSt):
        dists = [-1] * numV
        dists[vSt] = 0
        Q = deque([vSt])
        while Q:
            vNow = Q.popleft()
            distNow = dists[vNow]
            for v2 in adjList[vNow]:
                if dists[v2] == -1:
                    dists[v2] = distNow + 1
                    Q.append(v2)

        maxD = max(dists)
        vMaxD = dists.index(maxD)
        return (vMaxD, maxD)

    numV = len(adjList)
    v, d = bfs(0)
    v2, d2 = bfs(v)
    return d2


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

if getDiameter(adjL) % 3 == 1:
    print('Second')
else:
    print('First')

Solution (Python):
from collections import deque
import sys

input = sys.stdin.readline

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


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



def bfs(i):
    """
    :param i: bfsの始点, 0-indexed
    :return: (v,d), iの最遠点vまでの距離d
    """
    dist = [-1 for _ in range(N)]
    dist[i] = 0

    q = deque((i,))
    while q:
        v = q.popleft()
        d = dist[v]
        for nv in filter(lambda x: dist[x] == -1, e[v]):
            dist[nv] = d + 1
            q.append(nv)
    return v, d


x, _ = bfs(0)
_, d = bfs(x)

print('Second' if d % 3 == 1 else 'First')

Solution (Python):
from collections import deque

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


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


dist = [-1 for _ in range(N)]
dist[0] = 0

q = deque()
q.append(0)

while q:
    v = q.popleft()
    d = dist[v]
    for nv in filter(lambda x: dist[x] == -1, e[v]):
        dist[nv] = d + 1
        q.append(nv)



dist = [-1 for _ in range(N)]
dist[v] = 0

q = deque()
q.append(v)

while q:
    w = q.popleft()
    d = dist[w]
    for nw in filter(lambda x: dist[x] == -1, e[w]):
        dist[nw] = d + 1
        q.append(nw)



print('Second' if d % 3 == 1 else 'First')

Solution (Python):

from collections import deque
import numpy as np

N = int(input())
graph = {i:[] for i 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(graph,root):
    distance  = [0]*N
    visited = set()
    queue = deque([root])
    while len(queue) > 0:
        vertex = queue.popleft()
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                distance[neighbour] = distance[vertex] + 1
                visited.add(neighbour)
                queue.append(neighbour)

    farthest_node = np.argmax(distance)
    farthest_dist = distance[farthest_node]
    return farthest_node, farthest_dist

u, _ = bfs(graph, root=0)
_, diamiter = bfs(graph, root=u)

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

Solution (Python):

from collections import deque
import numpy as np

N = int(input())
graph = {i:[] for i 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(graph,root):
    distance  = [0]*N
    visited = [False]*N
    visited[root] = True
    queue = deque([root])

    while queue:
        vertex = queue.popleft()
        for neighbour in graph[vertex]:
            if not visited[neighbour]:
                distance[neighbour] = distance[vertex] + 1
                visited[neighbour] = True
                queue.append(neighbour)

    farthest_node = np.argmax(distance)
    farthest_dist = distance[farthest_node]
    return farthest_node, farthest_dist

u, _ = bfs(graph, root=0)
_, diamiter = bfs(graph, root=u)

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