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:
# AGC033C

import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


from collections import defaultdict
n = int(input())
ns = defaultdict(set)
for _ in range(n-1):
    u,v = map(int, input().split())
    ns[u-1].add(v-1)
    ns[v-1].add(u-1)

def bfs(start):
    from queue import deque
    q = deque([start])
    seen = [None] * n
    seen[start] = 0
    dd = 0
    target = start
    while q:
        u = q.pop()
        d = seen[u]
        if d>dd:
            dd = d
            target = u
        for v in ns[u]:
            if seen[v] is None:
                seen[v] = d + 1
                q.appendleft(v)
    return target, dd
target, tmp = bfs(0)
_, d = bfs(target)
if (d-1)%3!=0:
    print("First")
else:
    print("Second")

Submission status: Accepted

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


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

# 木の直径を求める
dist = calc_dist(0)
end = 0
max_dist = 0
for i, di in enumerate(dist):
  if max_dist < di:
    max_dist = di
    end = i

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

Submission status: Accepted

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

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

INF = 10**18

def dfs(s):
    dist = [INF] * (N+1)
    dist[s] = 0
    stack = [s]
    while stack:
        v = stack.pop()
        for c in G[v]:
            if dist[c] == INF:
                dist[c] = dist[v] + 1
                stack.append(c)
    return dist

d1 = dfs(1)
v = max(range(1, N+1), key=lambda x: d1[x])
d2 = dfs(v)
diameter = max(d2[1:]) + 1
if (diameter - 2) % 3 == 0:
    print('Second')
else:
    print('First')

Submission status: Accepted

Solution code:
class Tree():
    def __init__(self, n, edge):
        self.n = n
        self.tree = [[] for _ in range(n)]
        for e in edge:
            self.tree[e[0] - 1].append(e[1] - 1)
            self.tree[e[1] - 1].append(e[0] - 1)

    def setroot(self, root):
        self.root = root
        self.parent = [None for _ in range(self.n)]
        self.parent[root] = -1
        self.depth = [None for _ in range(self.n)]
        self.depth[root] = 0
        self.order = []
        self.order.append(root)
        self.size = [1 for _ in range(self.n)]
        stack = [root]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if self.parent[adj] is None:
                    self.parent[adj] = node
                    self.depth[adj] = self.depth[node] + 1
                    self.order.append(adj)
                    stack.append(adj)
        for node in self.order[::-1]:
            for adj in self.tree[node]:
                if self.parent[node] == adj:
                    continue
                self.size[node] += self.size[adj]

    def diam(self):
        u = self.depth.index(max(self.depth))
        dist_u = [None for _ in range(N)]
        dist_u[u] = 0
        stack = [u]
        while stack:
            node = stack.pop()
            for adj in self.tree[node]:
                if dist_u[adj] is None:
                    dist_u[adj] = dist_u[node] + 1
                    stack.append(adj)
        d = max(dist_u)
        v = dist_u.index(d)
        return d, u, v

import sys
input = sys.stdin.readline

N = int(input())
E = [tuple(map(int, input().split())) for _ in range(N - 1)]
T = Tree(N, E)
T.setroot(0)
d, _, _ = T.diam()

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

Submission status: Accepted

Solution code:
from collections import deque
N,*L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
for a,b in zip(*[iter(L)]*2):
  dic[a].append(b)
  dic[b].append(a)
q = deque([1])
dist = [-1]*(N+1)
dist[1] = 0
while q:
  p = q.popleft()
  for v in dic[p]:
    if dist[v]==-1:
      q.append(v)
      dist[v] = dist[p]+1
u = max(range(1,N+1),key=lambda x:dist[x])
q = deque([u])
dist = [-1]*(N+1)
dist[u] = 0
while q:
  p = q.popleft()
  for v in dic[p]:
    if dist[v]==-1:
      q.append(v)
      dist[v] = dist[p]+1
M = max(dist)
if M%3==1:
  print('Second')
else:
  print('First')

Submission status: Accepted

Solution code:
from collections import deque
N,*L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
for i in range(N-1):
  a,b = L[2*i],L[2*i+1]
  dic[a].append(b)
  dic[b].append(a)
q = deque([1])
dist = [-1]*(N+1)
dist[1] = 0
while q:
  p = q.popleft()
  for v in dic[p]:
    if dist[v]==-1:
      q.append(v)
      dist[v] = dist[p]+1
u = max(range(1,N+1),key=lambda x:dist[x])
q = deque([u])
dist = [-1]*(N+1)
dist[u] = 0
while q:
  p = q.popleft()
  for v in dic[p]:
    if dist[v]==-1:
      q.append(v)
      dist[v] = dist[p]+1
M = max(dist)
if M%3==1:
  print('Second')
else:
  print('First')

Submission status: Accepted

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

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline
N=int(input())
edge=[[] for i in range(N)]
for i in range(N-1):
    a,b=map(int,input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

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

depth=[-1 for i in range(N)]
depth[0]=0
q=set([0])
sub=set([])
while q:
    while q:
        x=q.pop()
        for i in edge[x]:
            if depth[i]==-1:
                depth[i]=1+depth[x]
                sub.add(i)
        if not q:
            q=sub
            sub=set([])
            break

root=depth.index(max(depth))
depth=[-1 for i in range(N)]
depth[root]=0
q=set([root])
sub=set([])
while q:
    while q:
        x=q.pop()
        for i in edge[x]:
            if depth[i]==-1:
                depth[i]=1+depth[x]
                sub.add(i)
        if not q:
            q=sub
            sub=set([])
            break

dia=max(depth)
dp=[["" for i in range(0,2)] for i in range(0,dia+1)]
dp[0][0]="First"
dp[0][1]="Second"
dp[1][0]="Second"
dp[1][1]="First"
for i in range(2,dia+1):
    if dp[i-1][1]=="First" or dp[i-2][1]=="First":
        dp[i][0]="First"
    else:
        dp[i][0]="Second"

    if dp[i][0]=="First":
        dp[i][1]="Second"
    else:
        dp[i][1]="First"

print(dp[dia][0])

Submission status: Accepted

Solution code:
import sys
from collections import deque

sys.setrecursionlimit(10 ** 7)
rl = sys.stdin.readline


def solve():
    N = int(rl())
    graph = [[] for _ in range(N)]
    for _ in range(N - 1):
        a, b = map(lambda x: int(x) - 1, rl().split())
        graph[a].append(b)
        graph[b].append(a)
    
    def bfs(node):
        searched = [False] * N
        que = deque([(node, 0)])
        v, dist = 0, 0
        while que:
            v, dist = que.popleft()
            searched[v] = True
            for child in graph[v]:
                # noinspection PyTypeChecker
                if not searched[child]:
                    que.append((child, dist + 1))
        return v, dist
    
    e, _ = bfs(0)
    _, diameter = bfs(e)
    print('Second' if diameter % 3 == 1 else 'First')


if __name__ == '__main__':
    solve()

Submission status: Accepted

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

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

Submission status: Accepted

Solution code:
from sys import stdin, stdout

def main():
    N = (int)(stdin.readline())
    graph = dict()
	
    if N == 1:
      print("First")
      return
    if N == 2:
      print("Second")
      return
    
    for i in range(N-1):
        edge = stdin.readline().split()
        ai = (int)(edge[0])
        bi = (int)(edge[1])

        if ai in graph.keys():
            graph[ai].append(bi)
        else:
            graph[ai] = [bi]
        
        if bi in graph.keys():
            graph[bi].append(ai)
        else:
            graph[bi] = [ai]

    mid_node = bfs(graph, 1)[0]
    
    longest_path = bfs(graph, mid_node)[1]
    
    if longest_path % 3 == 1:
        print("Second")
    else:
        print("First")

def bfs(graph, node):

    result = -1
    last_level = set()
    visited = set()

    last_level.add(node)
    visited.add(node)

    length = 0

    while len(last_level) > 0:
        
        new_level = set()

        length += 1

        for last_node in last_level:
            result = last_node
            for neighbor in graph[last_node]:
                if neighbor not in visited:
                    new_level.add(neighbor)
                    visited.add(neighbor)
        last_level = new_level
    
    return result, length - 1

if __name__ == "__main__":
    main()

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def tree_diameter(graph): # 木の直径
    def dijkstra(start):
        INF = 10 ** 15
        dist = [INF] * (N+1)
        dist[start] = 0
        que = [(0, start)]
        length = 0; far = 0
        while que:
            d, prev = heappop(que)
            if dist[prev] < d:
                continue
            for next in graph[prev]:
                d1 = d + 1
                if dist[next] > d1:
                    dist[next] = d1
                    if d1 > length:
                        length = d1; far = next
                    heappush(que, (d1, next))
        return length, far
    _, f = dijkstra(1)
    l, f = dijkstra(f)
    return l

N = ir()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

daiameter = tree_diameter(graph)
bl = daiameter % 3 != 1
print('First' if bl else 'Second')

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
from heapq import heapify, heappop, heappush

sr = lambda: sys.stdin.readline().rstrip()
ir = lambda: int(sr())
lr = lambda: list(map(int, sr().split()))

def dijkstra(start):
    INF = 10 ** 15
    dist = [INF] * (N+1)
    dist[start] = 0
    que = [(0, start)]
    while que:
        d, prev = heappop(que)
        if dist[prev] < d:
            continue
        for next in graph[prev]:
            d1 = d + 1
            if dist[next] > d1:
                dist[next] = d1
                heappush(que, (d1, next))
    return dist

N = ir()
graph = [[] for _ in range(N+1)] # 1-indexed
for _ in range(N-1):
    a, b = lr()
    graph[a].append(b)
    graph[b].append(a)

# １を根とする
dist = dijkstra(1)
dist = sorted([(x, i) for i, x in enumerate(dist)], reverse=True)
new_root = dist[1][1]
dist = dijkstra(new_root)
diameter = max(dist[1:]) + 1
bl = diameter % 3 != 2
print('First' if bl else 'Second')
# 22

Submission status: Accepted

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

Submission status: Accepted

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

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

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

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

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

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

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

    return minDist

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

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

canFirstWin = [False] * (R + 1)
canFirstWin[1] = True
canFirstWin[2] = False

for i in range(3, R + 1):
    canFirstWin[i] = not(canFirstWin[i - 1] and canFirstWin[i - 2])

print('First' if canFirstWin[R] else 'Second')

Submission status: Accepted

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

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

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

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

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

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

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

    return minDist

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

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

Submission status: Accepted

Solution code:
from collections import deque


def bfs(start):
    distance = [None] * n
    q = deque([start])
    distance[start] = 0
    while q:
        pos = q.popleft()
        d = distance[pos]
        for next_pos, cost in graph[pos]:
            if distance[next_pos] is not None:
                continue
            distance[next_pos] = d + cost
            q.append(next_pos)
    d = max(distance)
    return distance.index(d), d
  
def tree_diameter():
    ind, _ = bfs(0)
    ind2, d = bfs(ind)
    return d

n = int(input())
info = [list(map(int, input().split())) for i in range(n - 1)]
graph = [[] for i in range(n)]
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    cost = 1
    graph[a].append((b, cost))
    graph[b].append((a, cost))


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

Submission status: Accepted

Solution code:
import sys
import math
from collections import defaultdict
from bisect import bisect_left, bisect_right

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

mod = 10**9 + 7

def I(): return int(input())
def LI(): return list(map(int, input().split()))
def LIR(row,col):
    if row <= 0:
        return [[] for _ in range(col)]
    elif col == 1:
        return [I() for _ in range(row)]
    else:
        read_all = [LI() for _ in range(row)]
        return map(list, zip(*read_all))

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

def edges_to_pt(s,t,n,directed=False):
    pt = [[] for _ in range(n)]
    for i in range(len(s)):
        pt[s[i]-1].append(t[i]-1)
        if directed == False:
            pt[t[i]-1].append(s[i]-1)
    return pt

def tree_diameter(pt):
    def bfs(pt,v):
        n = len(pt)
        visited = [False]*n
        visited[v] = True
        max_d = 0
        max_d_index = v
        q = [v]
        c = 1
        while q:
            q1 = []
            for i in q:
                for j in pt[i]:
                    if not visited[j]:
                        visited[j] = c
                        max_d = c
                        max_d_index = j
                        q1.append(j)
            q = q1
            c += 1
        return max_d, max_d_index
    
    _,index = bfs(pt,0)
    return bfs(pt,index)[0]

N = I()
a,b = LIR(N-1,2)

pt = edges_to_pt(a,b,N)
r = tree_diameter(pt)

# 木の直径 r（≥2）を -1 or -2 できる
# r = 1 をもらうと負け
if r%3 == 1:
    print('Second')
else:
    print('First')

Submission status: Accepted

Solution code:
def main():
    N = int(input())
    C = [set() for _ in range(N)]
    for _ in range(N - 1):
        a, b = list(map(int, input().split()))
        C[a - 1].add(b - 1)
        C[b - 1].add(a - 1)
    if N == 1:
        return 'First'

    prv = set()
    cur = [0]
    while cur:
        nxt = []
        for c in cur:
            nxt.extend(k for k in C[c] if k not in prv)
        prv = set(cur)
        cur = nxt
    p = prv.pop()
    prv = set()
    cur = [p]
    d = 0
    while cur:
        nxt = []
        for c in cur:
            nxt.extend(k for k in C[c] if k not in prv)
        prv = set(cur)
        cur = nxt
        d += 1

    return 'First' if d % 3 in (0, 1) else 'Second'


print(main())

Submission status: Accepted

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

n = int(input())
T = [[] for _ in range(n+1)]
for _ in range(n-1):
  a, b = map(int, input().split())
  T[a].append(b)
  T[b].append(a)
def dfs(v):
  dist = [-1]*(n+1)
  dist[v] = 0
  stack = [v]
  depth = 0
  while stack:
    nv = stack.pop()
    for i in T[nv]:
      if dist[i] != -1:
        continue
      dist[i] = dist[nv] + 1
      stack.append(i)
  return dist

D = dfs(1)
m = D.index(max(D))
dia = max(dfs(m))
if dia%3 == 1:
  print("Second")
else:
  print("First")

Submission status: Accepted

Solution code:
from collections import deque
N, *L = map(int, open(0).read().split())
dic = [[] for i in range(N+1)]
for a,b in zip(*[iter(L)]*2):
  dic[a] += [b]
  dic[b] += [a]
q = deque([1])
  
dist = [-1]*(N+1)
while q:
  v = q.popleft()
  for u in dic[v]:
    if dist[u]==-1:
      dist[u] = dist[v]+1
      q.append(u)
p = max(range(1,N+1),key=lambda x:dist[x])
dist = [-1]*(N+1)
dist[p] = 0
q = deque([p])
while q:
  v = q.popleft()
  for u in dic[v]:
    if dist[u]==-1:
      dist[u] = dist[v]+1
      q.append(u)
M = max(dist)
if M%3==1:
  print('Second')
else:
  print('First')

Submission status: Accepted

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

Submission status: Accepted

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

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

if __name__ == "__main__":
    main()

Submission status: Accepted

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

Submission status: Accepted

Solution code:
def examA():
    N = I()
    ans = 0
    print(ans)
    return

# maspyさん
def examB_maspy():
    H, W, N = LI()
    sr, sc = LI()
    S = SI()
    T = SI()
    sr = H + 1 - sr

    # ここに居たら後手の価値
    L, R = 1, W
    D, U = 1, H
    for s, t in zip(S[::-1], T[::-1]):
        if t == 'L':
            R += 1
        elif t == 'D':
            U += 1
        elif t == 'R':
            L -= 1
        elif t == 'U':
            D -= 1

        if L == 0: L = 1
        if D == 0: D = 1
        if R > W: R = W
        if U > H: U = H

        if s == 'L':
            L += 1
        elif s == 'R':
            R -= 1
        elif s == 'D':
            D += 1
        elif s == 'U':
            U -= 1

        if L > R or D > U:
            # 後手の勝てる場所が存在せず
            break

    bl = (L <= sc <= R) and (D <= sr <= U)
    answer = 'YES' if bl else 'NO'
    print(answer)
    return

#自分の H+1-Start[0]忘れ
def examB():
    H, W, N = LI()
    start = LI()
    S = SI();
    T = SI()
    for t, a in [["U", "D"], ["R", "L"]]:
        if t == "U":
            n = H
        else:
            n = W
        # 落ちないエリア
        l = 1;
        r = n
        if S[-1] == t:
            r -= 1
        elif S[-1] == a:
            l += 1
        for i in range(N - 2, -1, -1):
            if T[i] == t and l > 1:
                l -= 1
            elif T[i] == a and r < n:
                r += 1
            if S[i] == t:
                r -= 1
            elif S[i] == a:
                l += 1
            #            print(l,r)
            if l > r:
                print("NO")
                return
            if t == "U" and (r == 0 or l == n):
                print("NO")
                return
            if t == "R" and (r == 0 or l == n):
                print("NO")
                return

        if t == "U" and (not l <= H + 1 - start[0] <= r):
            print("NO")
            return
        elif t == "R" and (not l <= start[1] <= r):
            print("NO")
            return
    print("YES")
    return

def examC():
    def bfs(n, e, fordfs):
        # 点の数、スタートの点、有向グラフ
        W = [-1] * n
        # 各点の状態量、最短距離とか,見たかどうかとか
        W[e] = 0
        que = deque()
        que.append(e)
        while que:
            now = que.popleft()
            nowW = W[now]
            for ne in fordfs[now]:
                if W[ne] == -1:
                    W[ne] = nowW + 1
                    que.append(ne)
        return W
    N = I()
    V = [[]for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        a -=1; b -=1
        V[a].append(b)
        V[b].append(a)
    L = bfs(N,0,V)
    D = max(bfs(N,L.index(max(L)),V))
#    print(D)
    if D%3==1:
        print("Second")
    else:
        print("First")
    return

def examD():
    ans = 0
    print(ans)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
global mod,mod2,inf,alphabet
mod = 10**9 + 7
mod2 = 998244353
inf = 10**18
alphabet = [chr(ord('a') + i) for i in range(26)]

if __name__ == '__main__':
    examC()

"""

"""

Submission status: Accepted

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

import sys

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

def dfs(N, nodes, src):
    """ DFS(木、スタック、重みなし) """

    stack = [(src, -1, 0)]
    dist = [INF] * N
    while stack:
        u, prev, c = stack.pop()
        dist[u] = c
        for v in nodes[u]:
            if v != prev:
                stack.append((v, u, c+1))
    return dist

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

# 木の直径
dist1 = dfs(N, nodes, 0)
u = dist1.index(max(dist1))
dist2 = dfs(N, nodes, u)
L = max(dist2)

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

Submission status: Accepted

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1


def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, AB):
    g = defaultdict(set)

    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    def dfs(s):
        stack = [s]
        done = {s: 0}

        while stack:
            u = stack.pop()
            for v in g[u]:
                if v not in done:
                    done[v] = done[u] + 1
                    stack.append(v)
        l = (-0, 0)
        for k, v in done.items():
            if l[1] < v:
                l = (k, v)
        return l

    v, _ = dfs(1)
    _, l = dfs(v)
    return 'First' if l % 3 != 1 else 'Second'


def main():
    N = read_int()
    AB = [read_int_n() for _ in range(N-1)]
    print(slv(N, AB))


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
import sys
from collections import deque

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


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

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

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

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


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

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

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

Submission status: Accepted

Solution code:
N=int(input())
ab=[list(map(int,input().split())) for i in range(N-1)]
data=[[] for i in range(N+1)]
for a,b in ab:
    data[a].append(b)
    data[b].append(a)
flag=[-1]*(N+1)
flag[1]=0
que=[1]
l=1
while que:
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==-1:
                flag[v]=l
                h.append(v)
    l+=1
    que=h
ind=0
num=0
for i in range(1,N+1):
    if num<flag[i]:
        num=flag[i]
        ind=i
flag=[-1]*(N+1)
flag[ind]=0
que=[ind]
l=1
while que:
    h=[]
    for u in que:
        for v in data[u]:
            if flag[v]==-1:
                flag[v]=l
                h.append(v)
    l+=1
    que=h
num=max(flag)+1
if num%3==2:
    print("Second")
else:
    print("First")