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:
class Tree():
    def __init__(self, n, decrement=1):
        self.n = n
        self.edges = [[] for _ in range(n)]
        self.root = None
        self.depth = [-1]*n
        self.size = [1]*n       # 部分木のノードの数
        self.decrement = decrement

    def add_edge(self, u, v):
        u, v = u-self.decrement, v-self.decrement
        self.edges[u].append(v)
        self.edges[v].append(u)

    def add_edges(self, edges):
        for u, v in edges:
            u, v = u-self.decrement, v-self.decrement
            self.edges[u].append(v)
            self.edges[v].append(u)

    def set_root(self, root):
        root -= self.decrement
        self.root = root
        self.par = [-1]*self.n
        self.depth[root] = 0
        self.order = [root]     # 帰りがけに使う
        next_set = [root]
        while next_set:
            p = next_set.pop()
            for q in self.edges[p]:
                if self.depth[q] != -1: continue
                self.par[q] = p
                self.depth[q] = self.depth[p]+1
                self.order.append(q)
                next_set.append(q)
        for p in self.order[::-1]:
            for q in self.edges[p]:
                if self.par[p] == q: continue
                self.size[p] += self.size[q]

    def diameter(self):
        # assert self.root is not None
        u = self.depth.index(max(self.depth))
        dist = [-1]*self.n
        dist[u] = 0
        prev = [-1]*self.n
        next_set = [u]
        while next_set:
            p = next_set.pop()
            for q in self.edges[p]:
                if dist[q] != -1: continue
                dist[q] = dist[p]+1
                prev[q] = p
                next_set.append(q)
        d = max(dist)
        v = w = dist.index(d)
        path = [v+1]
        while w != u:
            w = prev[w]
            path.append(w+self.decrement)
        return d, v+self.decrement, u+self.decrement, path

    def heavy_light_decomposition(self):
        """
        heavy edge を並べてリストにした物を返す (1-indexed if decrement=True)
        """
        # assert self.root is not None
        self.vid = [-1]*self.n
        self.hld = [-1]*self.n
        self.head = [-1]*self.n
        self.head[self.root] = self.root
        self.heavy_node = [-1]*self.n
        next_set = [self.root]
        for i in range(self.n):
            """ for tree graph, dfs ends in N times """
            p = next_set.pop()
            self.vid[p] = i
            self.hld[i] = p+self.decrement
            maxs = 0
            for q in self.edges[p]:
                """ encode direction of Heavy edge into heavy_node """
                if self.par[p] == q: continue
                if maxs < self.size[q]:
                    maxs = self.size[q]
                    self.heavy_node[p] = q
            for q in self.edges[p]:
                """ determine "head" of heavy edge """
                if self.par[p] == q or self.heavy_node[p] == q: continue
                self.head[q] = q
                next_set.append(q)
            if self.heavy_node[p] != -1:
                self.head[self.heavy_node[p]] = self.head[p]
                next_set.append(self.heavy_node[p])
        return self.hld

    def lca(self, u, v):
        # assert self.head is not None
        u, v = u-self.decrement, v-self.decrement
        while True:
            if self.vid[u] > self.vid[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                v = self.par[self.head[v]]
            else:
                return u + self.decrement

    def path(self, u, v):
        """ u-v 間の最短経路をリストで返す """
        p = self.lca(u, v)
        u, v, p = u-self.decrement, v-self.decrement, p-self.decrement
        R = []
        while u != p:
            yield u+self.decrement
            u = self.par[u]
        yield p+self.decrement
        while v != p:
            R.append(v)
            v = self.par[v]
        for v in reversed(R):
            yield v+self.decrement

    def distance(self, u, v):
        # assert self.head is not None
        p = self.lca(u, v)
        u, v, p = u-self.decrement, v-self.decrement, p-self.decrement
        return self.depth[u] + self.depth[v] - 2*self.depth[p]

    def find(self, u, v, x):
        return self.distance(u,x)+self.distance(x,v)==self.distance(u,v)

    def path_to_list(self, u, v, edge_query=False):
        """
        パス上の頂点の集合を self.hld 上の開区間の集合として表す
        ここで、self.hld は heavy edge を並べて数列にしたものである
        """
        # assert self.head is not None
        u, v = u-self.decrement, v-self.decrement
        while True:
            if self.vid[u] > self.vid[v]: u, v = v, u
            if self.head[u] != self.head[v]:
                yield self.vid[self.head[v]], self.vid[v] + 1
                v = self.par[self.head[v]]
            else:
                yield self.vid[u] + edge_query, self.vid[v] + 1
                return

    def point(self, u):
        return self.vid[u-self.decrement]

    def subtree_query(self, u):
        u -= self.decrement
        return self.vid[u], self.vid[u] + self.size[u]

##################################################################################################
import sys
input = sys.stdin.readline

N = int(input())
T = Tree(N)
for _ in range(N-1):
    x, y = map(int, input().split())
    T.add_edge(x, y)
T.set_root(1)


print("Second" if (T.diameter()[0]+1)%3==2 else "First")

Submission status: Accepted

Solution code:
from collections import defaultdict as dd
N = int(input())
Es = dd(dict)
for _ in range(N-1):
    a, b = map(int, input().split())
    Es[a-1][b-1] = Es[b-1][a-1] = 1

# もっとも長いパスを見つける
q = [0]
visited = [False] * N
last = None
while q:
    nq = []
    for node in q:
        last = node
        visited[node] = True
        for to in Es[node]:
            if visited[to]:
                continue
            nq.append(to)
    q = nq

q = [last]
visited = [False] * N
n = 0
while q:
    n += 1
    nq = []
    for node in q:
        visited[node] = True
        for to in Es[node]:
            if visited[to]:
                continue
            nq.append(to)
    q = nq

if n % 3 == 2:
    print('Second')
else:
    print('First')

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**8)
N = int(input())
AB = [tuple(map(int,input().split())) for i in range(N-1)]
es = [[] for _ in range(N)]
for a,b in AB:
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

depth = [0] * N
def dfs(v,p=-1):
    for to in es[v]:
        if to==p: continue
        depth[to] = depth[v] + 1
        dfs(to,v)
dfs(0)
mxd = max(depth)
i = depth.index(mxd)
depth = [0] * N
dfs(i)

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

Submission status: Accepted

Solution code:
from itertools import count

def furthest(v0,N,adj):
    q = [v0]
    visited = [False]*N
    visited[v0] = True
    x = -1

    for dist in count():
        if not q:
            break
        x = q[0]
        nq = []
        for v in q:
            for u in adj[v]:
                if not visited[u]:
                    visited[u] = True
                    nq.append(u)
        q = nq
    return dist, x

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)

d,v = furthest(0,N,adj)
# print(d,v)
d,v = furthest(v,N,adj)
# print(d,v)
# print(d)

print('First' if d != 0 and d%3 != 2 else 'Second')

Submission status: Accepted

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("Second" if (graph.diameter()+1)%3==2 else "First")

Submission status: Accepted

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)
last=0
for i in range(n):
    if len(dic[i+1])==1:
        itta=[0]*(n+1)
        d=deque([i+1])
        while d:
            now=d.popleft()
            if itta[now]==1:
                continue
            itta[now]=1
            last=now
            for j in dic[now]:
                d.append(j)
        break
itta=[0]*(n+1)
cnt=0
d=deque([(last,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))
# print(cnt)
if cnt%3==1:
    print(S)
else:
    print(F)

Submission status: Accepted

Solution code:
'''
研究室PCでの解答
'''
import math
#import numpy as np
import queue
import bisect
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)
mod = 10**9+7 #998244353
dir = [(-1,0),(1,0),(0,-1),(0,1)]
alp = "abcdefghijklmnopqrstuvwxyz"


def main():
    n = int(ipt())
    way = [[] for i in range(n+1)]
    for i in range(n-1):
        a,b = map(int,ipt().split())
        way[a].append(b)
        way[b].append(a)

    d = [-1]*(n+1)
    d[1] = 0
    q = [1]
    while q:
        qi = q.pop()
        dqi = d[qi]
        for i in way[qi]:
            if d[i] == -1:
                d[i] = dqi+1
                q.append(i)
    mi = -1
    ma = 0
    for i,di in enumerate(d):
        if ma < di:
            mi = i
            ma = di

    d = [-1]*(n+1)
    d[mi] = 0
    q = [mi]
    while q:
        qi = q.pop()
        dqi = d[qi]
        for i in way[qi]:
            if d[i] == -1:
                d[i] = dqi+1
                q.append(i)
    mi = -1
    ma = 0
    for i,di in enumerate(d):
        if ma < di:
            mi = i
            ma = di
    ma += 1
    if ma%3 == 2:
        print("Second")
    else:
        print("First")
    return None

if __name__ == '__main__':
    main()

Submission status: Accepted

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

def bfs(s):
    dist = [-1]*N
    dist[s] = 0
    q = deque([s])
    
    while q:
        v = q.popleft()
        
        for nv in G[v]:
            if dist[nv]==-1:
                dist[nv] = dist[v]+1
                q.append(nv)
    
    return dist

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

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

dist = bfs(0)
M = -1

for i in range(N):
    if dist[i]>M:
        M = dist[i]
        s = i

d = max(bfs(s))+1
dp = [False]*(d+1)
dp[1] = True

for i in range(3, d+1):
    dp[i] |= not dp[i-1]
    dp[i] |= not dp[i-2]

if dp[d]:
    print('First')
else:
    print('Second')

Submission status: Accepted

Solution code:
from collections import deque
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(b)
    G[b].append(a)


import numpy as np
def bfs(i):
    dist=[-1]*n
    dist[i]=0
    queue=deque([[i,j] for j in G[i]])
    while queue:
        now,to=queue.pop()
        if dist[to]!=-1 : continue
        dist[to]=dist[now]+1
        for p in G[to]:
            queue.appendleft([to,p])
    return np.argmax(dist), np.max(dist)

v,_ = bfs(0)
u,R= bfs(v)
R+=1

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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
input = sys.stdin.readline
input = sys.stdin.buffer.readline

#sys.setrecursionlimit(10**9)
#from functools import lru_cache

def RD(): return sys.stdin.read()
def II(): return int(input())
def MI(): return map(int,input().split())
def MF(): return map(float,input().split())
def LI(): return list(map(int,input().split()))
def LF(): return list(map(float,input().split()))
def TI(): return tuple(map(int,input().split()))
# rstrip().decode('utf-8')

from collections import deque

def main():
	n=II()
	G=[[] for _ in range(n+1)]
	
	for _ in range(n-1):
		a,b=MI()
		G[a].append(b)
		G[b].append(a)
	#print(G)
	
	Q=deque()
	Q.append([1,0])
	l=0
	v=0
	sumi=set()
	
	while Q:
		#print(Q)
		now,d=Q.popleft()
		sumi.add(now)
		if d>l:
			v=now
			l=d
		for i in G[now]:
			if i not in sumi:
				Q.append([i,d+1])
	#print(v,l)
	
	Q=deque()
	Q.append([v,0])
	l=0
	sumi=set()
	while Q:
		#print(Q)
		now,d=Q.popleft()
		sumi.add(now)
		if d>l:
			l=d
		for i in G[now]:
			if i not in sumi:
				Q.append([i,d+1])
	#print(l)
	
	if l%3==1:
		print("Second")
	else:
		print("First")

	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	
	









if __name__ == "__main__":
	main()

Submission status: Accepted

Solution code:
N=int(input())
AB=[list(map(int,input().split())) for i in range(N-1)]
c=[[] for i in range(N)]
for i,j in AB:
    c[i-1].append(j-1)
    c[j-1].append(i-1)
from collections import deque
def bfs(c,N,s):
    d=[-1]*N
    d[s]=0
    q=deque([s])
    while q:
        i=q.popleft()
        for j in c[i]:
            if d[j]<0:
                d[j]=d[i]+1
                q.append(j)
    return d
d=bfs(c,N,0)
r=max(bfs(c,N,d.index(max(d))))
print(['First','Second'][r%3==1])

Submission status: Accepted

Solution code:
from collections import deque
printn = lambda x: print(x,end='')
inn = lambda : int(input())
inl   = lambda: list(map(int, input().split()))
inm   = lambda:      map(int, input().split())
ins = lambda : input().strip()
DBG = True # and False
BIG = 10**18
R = 10**9 + 7

def ddprint(x):
  if DBG:
    print(x)

n = inn()
if n==1:
    print('First')
    exit()
dst = [{} for i in range(n+1)]
for i in range(n-1):
    u,v = inm()
    dst[u][v] = dst[v][u] = 1
s = 1
d1 = [-1]*(n+1)
d1[s] = 0
q = deque([s])
while len(q)>0:
    x = q.popleft()
    d = d1[x]
    for u in dst[x]:
        if d1[u]<0:
            d1[u] = d+1
            q.append(u)
mx = 0
for i in range(1,n+1):
    if d1[i]>mx:
        mx = d1[i]
        mxi = i

s = mxi
d1 = [-1]*(n+1)
d1[s] = 0
q = deque([s])
while len(q)>0:
    x = q.popleft()
    d = d1[x]
    for u in dst[x]:
        if d1[u]<0:
            d1[u] = d+1
            q.append(u)
if max(d1)%3==1:
    print('Second')
else:
    print('First')

Submission status: Accepted

Solution code:
#Solve this by Rerooting
import sys
from itertools import accumulate
import queue
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)


#bfs、直すの面倒なので読み替えて。
dfs_order = []
parent = [-1] * N
root = 0
#queue
stack = queue.Queue()
stack.put(root)
while not stack.empty():
    node = stack.get()
    dfs_order.append(node)
    for next_node in adj[node]:
        if next_node != parent[node]:
            parent[next_node] = node
            stack.put(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]+1 if next_node != parent[node] else dp2[node] for next_node in adj[node]]
    from_left = [1] + list(accumulate(around, max))[:-1]
    from_right = list(accumulate(reversed(around), max))[-2::-1] + [1]
    without = [max(l, r) + 1 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

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

length = max(dp)

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

Submission status: Accepted

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]+1 if next_node != parent[node] else dp2[node] for next_node in adj[node]]
    from_left = [1] + list(accumulate(around, max))[:-1]
    from_right = list(accumulate(reversed(around), max))[-2::-1] + [1]
    without = [max(l, r) + 1 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

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

length = max(dp)

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

Submission status: Accepted

Solution code:
import sys
read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

n = int(readline())
ab = list(map(int,read().split()))

links = [[] for _ in range(n+1)]
it = iter(ab)
for a,b in zip(it,it):
    links[a].append(b)
    links[b].append(a)

def bfs(root):
    depth = [-1] * (n+1)
    depth[root] = 0
    stack = [root]
    for i in range(1,n+1):
        next = []
        if(len(stack)==0):
            break
        while(stack):
            parent = stack.pop()
            for j in links[parent]:
                if(depth[j] == -1):
                    depth[j] = i
                    next.append(j)
        stack = next[::]

    return depth,parent

depth,root2 = bfs(1)
depth,root2 = bfs(root2)
r = max(depth)

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

Submission status: Accepted

Solution code:
from collections import deque
n=int(input())
l=[[]for i in range(n+1)]
for i in range(n-1):
 a,b=map(int,input().split())
 l[a-1].append(b-1)
 l[b-1].append(a-1)
def bfs(j):
 dl=[-1]*n
 dl[j]=0
 que=deque([j])
 while que:
  p=que.popleft();d=dl[p]+1
  for u in l[p]:
   if dl[u]>=0:continue
   dl[u]=d;que.append(u)
 return dl.index(max(dl)),max(dl)
m,_=bfs(0)
_,L=bfs(m)
print("Second"if L%3==1else"First")

Submission status: Accepted

Solution code:
import sys

sys.setrecursionlimit(10 ** 8)
ini = lambda: int(sys.stdin.readline())
inm = lambda: map(int, sys.stdin.readline().split())
inl = lambda: list(inm())
ins = lambda: sys.stdin.readline().rstrip()
# debug = lambda *a, **kw: print(*a, **kw, file=sys.stderr)

N = ini()
adj = [[] for _ in range(N)]

for i in range(N - 1):
    a, b = [x - 1 for x in inm()]
    adj[a].append(b)
    adj[b].append(a)

depth = [(0, 0) for _ in range(N)]


def solve():
    stk = [(0, -1, False)]
    while stk:
        node, p, agg = stk.pop()
        if not agg:
            stk.append((node, p, True))
        md1, md2 = 0, 0
        for x in adj[node]:
            if x == p:
                continue
            if agg:
                dx, _ = depth[x]
                dx += 1
                if md1 < dx:
                    md2 = md1
                    md1 = dx
                elif md2 < dx:
                    md2 = dx
            else:
                stk.append((x, node, False))
        if agg:
            depth[node] = (md1, md2)

    stk = [(0, -1)]
    max_len = 0
    while stk:
        node, p = stk.pop()
        d1, d2 = depth[node]
        if p >= 0:
            pd1, pd2 = depth[p]
            if pd1 == 1 + d1:
                pd1 = pd2
            if d2 < pd1 + 1:
                d2 = pd1 + 1
        if max_len < d1 + d2 + 1:
            max_len = d1 + d2 + 1
        for x in adj[node]:
            if x != p:
                stk.append((x, node))

    if max_len == 1:
        return True
    if max_len == 2:
        return False
    return (max_len + 1) % 3 != 0


print("First" if solve() else "Second")

Submission status: Accepted

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
Q = deque()
Q.append([0,0])
visited=[-1]*n
visited[0]=0
mx_dist=0
mx_ind=0
while Q:
    now,cnt = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=cnt+1
        Q.append([nxt,cnt+1])
        if mx_dist < cnt+1:
            mx_dist=cnt+1
            mx_ind = nxt

Q = deque()
Q.append([mx_ind,0])
visited=[-1]*n
visited[mx_ind]=0
mx_dist=0
while Q:
    now,cnt = Q.popleft()
    for nxt in link[now]:
        if visited[nxt]!=-1:
            continue
        visited[nxt]=cnt+1
        Q.append([nxt,cnt+1])
        if mx_dist < cnt+1:
            mx_dist=cnt+1
            mx_ind = nxt

if (mx_dist-1)%3==0:
    print("Second")
else:
    print("First")

Submission status: Accepted

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-1)%3==0:
    print("Second")
else:
    print("First")

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import sys
sys.setrecursionlimit(10**9)
INF=10**18
MOD=10**9+7
input=lambda: sys.stdin.readline().rstrip()
YesNo=lambda b: bool([print('Yes')] if b else print('No'))
YESNO=lambda b: bool([print('YES')] if b else print('NO'))
int1=lambda x:int(x)-1

N=int(input())
edge=[[] for _ in range(N)]
for _ in range(N-1):
    a,b=map(int1,input().split())
    edge[a].append(b)
    edge[b].append(a)
stack=[0]
for _ in range(2):
    d=[INF]*N
    d[stack[0]]=0
    MAX=(0,-1)
    while stack:
        v=stack.pop()
        for nv in edge[v]:
            if d[nv]==INF:
                d[nv]=d[v]+1
                MAX=max(MAX,(d[nv],nv))
                stack.append(nv)
    stack.append(MAX[1])
if MAX[0]%3==1:
    print('Second')
else:
    print('First')

Submission status: Accepted

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

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


def dfs(V, start):
    q = [(start, 0)]
    used = [False] * (n+1)
    farthest = 0
    pos = 0

    while q:
        s, cost = q.pop()
        if farthest < cost:
            pos = s
            farthest = cost
        used[s] = True
        for t, c in V[s].items():
            if used[t]:
                continue
            q.append((t, cost + c))
    
    return farthest, pos


if __name__ == "__main__":
    n = int(input())
    V = {i:dict() for i in range(1, n+1)}

    for _ in range(n - 1):
        s, t = map(int, input().split())
        V[s][t] = 1
        V[t][s] = 1

    if n==1:
        print("First")
    else:
        d = dfs(V, dfs(V, 1)[1])[0]
        if d==1:
            print("Second")
        elif d==2:
            print("First")
        elif (d-1)%3==0:
            print("Second")
        else:
            print("First")

Submission status: Accepted

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10 ** 6)

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

def dfs(cur, par):
    dist, ter = 0, cur
    for nxt in E[cur]:
        if nxt == par:
            continue
        d, t = dfs(nxt, cur)
        if dist < d + 1:
            dist, ter = d + 1, t
    return (dist, ter)

L, _ = dfs(dfs(1, -1)[1], -1)

if L % 3 != 1:
    print("First")
else:
    print("Second")

Submission status: Accepted

Solution code:
from collections import deque

N, *AB = map(int, open(0).read().split())

E = [[] for _ in range(N + 1)]
for a, b in zip(*[iter(AB)] * 2):
    E[a].append(b)
    E[b].append(a)

def bfs(s):
    dist = [-1] * (N + 1)
    dist[s] = 0
    Q = deque([s])
    while Q:
        v = Q.popleft()
        d = dist[v] + 1
        for u in E[v]:
            if dist[u] >= 0:
                continue
            dist[u] = d
            Q.append(u)

    ma = max(dist)
    return dist.index(ma), ma

i, _ = bfs(1)
_, L = bfs(i)

if L % 3 != 1:
    print("First")
else:
    print("Second")