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):
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')

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

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


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

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


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

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

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

Solution (Python):
import sys
import queue

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

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


q = queue.Queue()
depth = [INF] * N
q.put(0)
depth[0] = 1
while not q.empty():
    node = q.get()
    for next_node in path[node]:
        if depth[next_node] > depth[node] + 1:
            depth[next_node] = depth[node] + 1
            q.put(next_node)


q = queue.Queue()
depth = [INF] * N
q.put(node)
depth[node] = 1
while not q.empty():
    node = q.get()
    for next_node in path[node]:
        if depth[next_node] > depth[node] + 1:
            depth[next_node] = depth[node] + 1
            q.put(next_node)

length = depth[node]

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

Solution (Python):

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

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

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

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

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

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

Solution (Python):


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

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

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

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

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

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

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

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

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

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

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

Solution (Python):
import sys
def input():
    return sys.stdin.readline()[:-1]
N=int(input())
s=[[]for i in range(N)]
for i in range(N-1):
    a,b=map(lambda x: int(x)-1,input().split())
    s[a].append(b)
    s[b].append(a)
sys.setrecursionlimit(300000)
l=[None]*N
l[0]=0
def hu(n,c):
    for i in s[n]:
        if l[i]==None:
            l[i]=c
            hu(i,c+1)
hu(0,1)
t=l.index(max(l))
l=[None]*N
l[t]=0
hu(t,1)
if max(l)%3==1:
    print("Second")
else:
    print("First")

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

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

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

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

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

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

Solution (Python):

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)] 
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')

Solution (Python):

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)] 
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')

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

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

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

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

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



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

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