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: Time Limit Exceeded

Solution code:
###############################################################################

from bisect import bisect_left as binl

def intin():
    input_tuple = input().split()
    if len(input_tuple) <= 1:
        return int(input_tuple[0])
    return tuple(map(int, input_tuple))


def intina():
    return [int(i) for i in input().split()]


def intinl(count):
    return [intin() for _ in range(count)]


def modadd(x, y):
    global mod
    return (x + y) % mod


def modmlt(x, y):
    global mod
    return (x * sy) % mod


def lcm(x, y):
    while y != 0:
        z = x % y
        x = y
        y = z
    return x


def make_linklist(xylist):
    linklist = {}
    for a, b in xylist:
        linklist.setdefault(a, [])
        linklist.setdefault(b, [])
        linklist[a].append(b)
        linklist[b].append(a)
    return linklist


def calc_longest_distance(linklist, v=1):
    distance_list = {}
    linklist_len = len(linklist)
    distance = 0
    vlist = set([v])

    while len(distance_list) < linklist_len:
        vlist_next = set()
        for v in vlist:
            if v not in distance_list:
                distance_list[v] = distance
                vlist_next = vlist_next | set(linklist[v])
        distance += 1
        vlist = vlist_next

    max_distance = -1
    max_v = None
    for v, distance in distance_list.items():
        if distance > max_distance:
            max_distance = distance
            max_v = v

    return (max_distance, max_v)


def calc_tree_diameter(linklist, v=1):
    _, u = calc_longest_distance(linklist, v)
    distance, _ = calc_longest_distance(linklist, u)
    return distance


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


def main():
    n = intin()
    ablist = intinl(n-1)

    linklist = make_linklist(ablist)
    diameter = calc_tree_diameter(linklist)

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


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import queue

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

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)

    def add_edge(self, a, b):
        self.graph[a].append(b)


class breadth(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0
        self.visit = ["no" for i in range(len(graph) + 1)]
        self.visit[s] = "yes"

        self.Q = queue.Queue()
        self.Q.put([self.dist[s], s])

        while not self.Q.empty():
            dist_u, u = self.Q.get()
            for v in self.g[u]:
                if self.visit[v] == "yes":
                    continue
                else:
                    self.dist[v] = dist_u + 1
                    self.visit[v] = "yes"
                    self.Q.put([self.dist[v], v])


N = int(input())
if N == 1:
	print("First")
else:
	g_a = Graph()
	for i in range(N - 1):
		a, b = getlist()
		g_a.add_edge(a, b)
		g_a.add_edge(b, a)
	
	s = 1
	E = breadth(g_a, s)
	x = 0
	for i in E.dist:
		if E.dist[i] > x:
			x = E.dist[i]
			y = i
	F = breadth(g_a, y)
	x = 0
	for i in F.dist:
		if F.dist[i] > x:
			x = F.dist[i]
			y = i

	if x % 3 == 0 or x % 3 == 2:
		print("First")
	else:
		print("Second")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)

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



def dfs(v, dist, memo):
    memo[v] = dist
    for nv in graph[v]:
        if memo[nv] >= 0:
            continue
        dfs(nv, dist+1, memo)


memo = [-1] * n
dfs(0, 0, memo)

node = 0
dist = 0
for i in range(n):
    if memo[i] > dist:
        dist = memo[i]
        node = i


memo = [-1] * n
dfs(node, 0, memo)

dist = max(memo)
count = dist + 1

dp = [0] * (count + 10)
dp[0] = 0
dp[1] = 1
dp[2] = 0
dp[3] = 1
dp[4] = 1


if count >= 5:
    for i in range(5, count+1):
        if dp[i-2] == 1 and dp[i-1] == 1:
            dp[i] = 0
        else:
            dp[i] = 1

if dp[count]:
    print("First")
else:
    print("Second")

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    sys.setrecursionlimit(10**7)
    input = sys.stdin.readline

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



    def dfs(v, dist, memo):
        memo[v] = dist
        for nv in graph[v]:
            if memo[nv] >= 0:
                continue
            dfs(nv, dist+1, memo)


    memo = [-1] * n
    dfs(0, 0, memo)

    node = 0
    dist = 0
    for i in range(n):
        if memo[i] > dist:
            dist = memo[i]
            node = i


    memo = [-1] * n
    dfs(node, 0, memo)

    dist = max(memo)
    count = dist + 1

    dp = [0] * (count + 10)
    dp[0] = 0
    dp[1] = 1
    dp[2] = 0
    dp[3] = 1
    dp[4] = 1


    if count >= 5:
        for i in range(5, count+1):
            if dp[i-2] == 1 and dp[i-1] == 1:
                dp[i] = 0
            else:
                dp[i] = 1

    if dp[count]:
        print("First")
    else:
        print("Second")

if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
input = sys.stdin.readline

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



def dfs(v, dist, memo):
    memo[v] = dist
    for nv in graph[v]:
        if memo[nv] >= 0:
            continue
        dfs(nv, dist+1, memo)


memo = [-1] * n
dfs(0, 0, memo)

node = 0
dist = 0
for i in range(n):
    if memo[i] > dist:
        dist = memo[i]
        node = i


memo = [-1] * n
dfs(node, 0, memo)

dist = max(memo)
count = dist + 1

dp = [0] * (count + 10)
dp[0] = 0
dp[1] = 1
dp[2] = 0
dp[3] = 1
dp[4] = 1


if count >= 5:
    for i in range(5, count+1):
        if dp[i-2] == 1 and dp[i-1] == 1:
            dp[i] = 0
        else:
            dp[i] = 1

if dp[count]:
    print("First")
else:
    print("Second")

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self):
    self.edges = set()
    self.distance = 1


def main():
  N = int(input())
  nodes = [Node() for _ in range(N)]

  if N == 0:
    print('Second', flush=True)
    return
  elif N == 1:
    print('First', flush=True)
    return

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

  leaves = [n for n in nodes if len(n.edges) == 1]

  while True:
    leaf = leaves.pop(0)
    parent = leaf.edges.pop()

    if len(parent.edges) == 1:
      size = leaf.distance + parent.distance
      break

    parent.distance = max(parent.distance, leaf.distance + 1)
    parent.edges.remove(leaf)

    if len(parent.edges) == 1:
      leaves.append(parent)

  if size % 3 == 2:
    print('Second', flush=True)
  else:
    print('First', flush=True)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
from heapq import heappop, heappush

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

class Graph(object):

    def __init__(self):
        self.graph = defaultdict(list)

    def __len__(self):
        return len(self.graph)
        
    def add_edge(self, a, b):
        self.graph[a].append(b)


class breadth(object):
    def __init__(self, graph, s):
        self.g = graph.graph
        self.dist = defaultdict(lambda: float('inf'))
        self.dist[s] = 0
        self.visit = ["no" for i in range(len(graph) + 1)]
        self.visit[s] = "yes"

        self.Q = []
        heappush(self.Q, (self.dist[s], s))

        while self.Q:
            dist_u, u = heappop(self.Q)
            for v in self.g[u]:
                if self.visit[v] == "yes":
                    continue
                else:
                    self.dist[v] = dist_u + 1
                    self.visit[v] = "yes"
                    heappush(self.Q, (self.dist[v], v))


N = int(input())
if N == 1:
	print("First")
else:
	g_a = Graph()
	for i in range(N - 1):
		a, b = getlist()
		g_a.add_edge(a, b)
		g_a.add_edge(b, a)
	
	s = 1
	E = breadth(g_a, s)
	x = 0
	for i in E.dist:
		if E.dist[i] > x:
			x = E.dist[i]
			y = i
	F = breadth(g_a, y)
	x = 0
	for i in F.dist:
		if F.dist[i] > x:
			x = F.dist[i]
			y = i

	if x % 3 == 0 or x % 3 == 2:
		print("First")
	else:
		print("Second")

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
import sys
# input = sys.stdin.readline
inf = 10 ** 18
 
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
 
cnct = [[] for _ in range(N)]
for ai, bi in ab:
    cnct[ai - 1].append(bi - 1)
    cnct[bi - 1].append(ai - 1)
# print("#", cnct)
 
# start from a leaf
for src in range(N):
    if len(cnct[src]) > 1: break
# print("#", src)
 
import heapq
 
len_max = 0
for i in range(2):
    q = []
    d = [inf] * N
    prev = [None] * N
    #
    heapq.heappush(q, (0, src))
    d[src] = 0
    while len(q) > 0:
        du, u = heapq.heappop(q)
        # print("#", du, u)
        for dst in cnct[u]:
            # print("##", dst)
            if d[dst] > du + 1:
                d[dst] = du + 1
                prev[dst] = u
                heapq.heappush(q, (du + 1, dst))
    #
    if len_max == max(d):
        break
    elif len_max < max(d):
        len_max = max(d)
        src = d.index(len_max)
    else:
        continue
 
# print("#", len_max)
 
if len_max % 3 == 1:
    print('Second')    
else:
    print('First')

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
import sys
# input = sys.stdin.readline
inf = 10 ** 18
 
N = int(input())
ab = [list(map(int, input().split())) for _ in range(N - 1)]
 
cnct = [[] for _ in range(N)]
for ai, bi in ab:
    cnct[ai - 1].append(bi - 1)
    cnct[bi - 1].append(ai - 1)
# print("#", cnct)
 
# start from a leaf
for src in range(N):
    if len(cnct[src]) > 1: break
# print("#", src)
 
import heapq
 
len_max = 0
for i in range(10):
    q = []
    d = [inf] * N
    prev = [None] * N
    #
    heapq.heappush(q, (0, src))
    d[src] = 0
    while len(q) > 0:
        du, u = heapq.heappop(q)
        # print("#", du, u)
        for dst in cnct[u]:
            # print("##", dst)
            if d[dst] > du + 1:
                d[dst] = du + 1
                prev[dst] = u
                heapq.heappush(q, (du + 1, dst))
    #
    if len_max == max(d):
        break
    elif len_max < max(d):
        len_max = max(d)
        src = d.index(len_max)
    else:
        continue
 
# print("#", len_max)
 
if len_max % 3 == 1:
    print('Second')    
else:
    print('First')

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
# グラフの最長経路が-1か-2かを選べる
N = int(input())
edge = [[] for _ in range(N)]
INF = 10**18
for _ in range(N-1):
  a,b = map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)


opposite = 0
max_dist = 0

def f(d,x):
  global max_dist,opposite
  dx = d[x]
  if dx > max_dist:
    opposite = x
    max_dist = dx
  for y in edge[x]:
    if d[y] == INF:
      d[y] = dx + 1
      f(d,y)


if N != 1:
  # 0からの距離
  d = [INF] * N
  d[0] = 0
  f(d,0)

  v = opposite
  d = [INF] * N
  d[v] = 0
  f(d,v)

  X = max_dist

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

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python
# -*- coding: utf-8 -*-


class Node(object):

  def __init__(self):
    self.edges = []
    self.distance = 1


def main():
  N = int(input())
  nodes = [Node() for _ in range(N)]

  if N == 0:
    print('Second', flush=True)
    return
  elif N == 1:
    print('First', flush=True)
    return

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

  leaves = [n for n in nodes if len(n.edges) == 1]

  while True:
    leaf = leaves.pop(0)
    parent = leaf.edges[0]

    if len(parent.edges) == 1:
      size = leaf.distance + parent.distance
      break

    parent.distance = max(parent.distance, leaf.distance + 1)
    parent.edges.remove(leaf)

    if len(parent.edges) == 1:
      leaves.append(parent)

  if size % 3 == 2:
    print('Second', flush=True)
  else:
    print('First', flush=True)


if __name__ == '__main__':
  main()

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())
link = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)
arr = [-1,-1]
def dfs(start,distance,value,info):
    distance[start] = value
    for w in link[start]:
        if distance[w] != -1:
            continue
        if value + 1 > info[0]:
            info[0] = value + 1
            info[1] = w
        dfs(w,distance, value+1, info)
def dfsB(start,distance,value):
    distance[start] = value
    for w in link[start]:
        if distance[w] != -1:
            continue
        dfsB(w,distance, value+1)


d = [-1 for _ in range(N)]
dfs(0,d,0,arr)
d2 = [-1 for _ in range(N)]
dfsB(arr[1],d2,0)
diameter = max(d2)
# print(diameter+1)
if (diameter+1)%3 == 2:
    print("Second")
else:
    print("First")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**7)
N = int(input())
link = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = map(int,input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)

def dfs(start,distance,value):
    distance[start] = value
    for w in link[start]:
        if distance[w] != -1:
            continue
        dfs(w,distance, value+1)

maxdist = -1
maxdistIndex = -1
d = [-1 for _ in range(N)]
dfs(0,d,0)
for i in range(N):
    if maxdist < d[i]:
        maxdistIndex = i
        maxdist = d[i]
d2 = [-1 for _ in range(N)]
dfs(maxdistIndex,d2,0)
diameter = max(d2)
# print(diameter+1)
if (diameter+1)%3 == 2:
    print("Second")
else:
    print("First")

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)
# グラフの最長経路が-1か-2かを選べる
N = int(input())
edge = [[] for _ in range(N)]
INF = 10**18
for _ in range(N-1):
  a,b = map(int,input().split())
  edge[a-1].append(b-1)
  edge[b-1].append(a-1)

opposite = 0
max_dist = 0
def f(d,x):
  global max_dist,opposite
  dx = d[x]
  if dx > max_dist:
    opposite = x
    max_dist = dx
  for y in edge[x]:
    if d[y] == INF:
      d[y] = dx + 1
      f(d,y)

# 0からの距離
d = [INF] * N
d[0] = 0
f(d,0)

v = opposite
d = [INF] * N
d[v] = 0
f(d,v)

X = max_dist

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

Submission status: Time Limit Exceeded

Solution code:
import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,random,time
sys.setrecursionlimit(10**7)
N = int(input())
link = [[] for i in range(N)]
for i in range(N-1):
    a,b = map(int,input().split())
    link[a-1].append(b-1)
    link[b-1].append(a-1)

def dfs(start,distance,value):
    distance[start] = value
    for w in link[start]:
        if distance[w] != -1:
            continue
        dfs(w,distance, value+1)

d = [-1 for i in range(N)]
dfs(0,d,0)
# print(d)
maxdist = -1
maxdistIndex = -1
for i in range(N):
    if d[i] > maxdist:
        maxdist = d[i]
        maxdistIndex = i
# print(maxdistIndex)
d2 = [-1 for i in range(N)]
dfs(maxdistIndex,d2,0)
diameter = max(d2)
# print(diameter+1)
if (diameter+1)%3 == 2:
    print("Second")
else:
    print("First")

Submission status: Time Limit Exceeded

Solution code:
# encoding: utf-8
import sys
# input = sys.stdin.readline
inf = 10 ** 18

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

cnct = [[] for _ in range(N)]
for ai, bi in ab:
    cnct[ai - 1].append(bi - 1)
    cnct[bi - 1].append(ai - 1)
# print("#", cnct)

# start from a leaf
for src in range(N):
    if len(cnct[src]) > 1: break
# print("#", src)

import heapq

len_max = 0
while True:
    q = []
    d = [inf] * N
    prev = [None] * N
    #
    heapq.heappush(q, (0, src))
    d[src] = 0
    while len(q) > 0:
        du, u = heapq.heappop(q)
        # print("#", du, u)
        for dst in cnct[u]:
            # print("##", dst)
            if d[dst] > du + 1:
                d[dst] = du + 1
                prev[dst] = u
                heapq.heappush(q, (du + 1, dst))
    #
    if len_max == max(d):
        break
    elif len_max < max(d):
        len_max = max(d)
        src = d.index(len_max)
    else:
        continue

# print("#", len_max)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(2 * 10 ** 5)


def dfs(v, p):
    farthest_d = 0
    farthest_v = v

    for u in links[v]:
        if u == p:
            continue
        res_d, res_v = dfs(u, v)
        if res_d > farthest_d:
            farthest_d = res_d
            farthest_v = res_v
    return farthest_d + 1, farthest_v


def solve():
    if n == 1:
        return True

    d, v = dfs(0, -1)
    d, v = dfs(v, -1)
    if (d + 1) % 3 == 0:
        return False
    return True


n = int(input())
links = [set() for _ in [0] * n]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)
print('First' if solve() else 'Second')

Submission status: Accepted

Solution code:
from sys import setrecursionlimit


def dfs(v):
    def dfs_rec(v):
        for nv in g[v]:
            if d[nv] >= 0:
                continue
            d[nv] = d[v] + 1
            dfs_rec(nv)

    d = [-1] * N
    d[v] = 0
    dfs_rec(v)
    return d


def get_diameter():
    d = dfs(0)
    far = max((d[i], i) for i in range(N))[1]
    return max(dfs(far))


setrecursionlimit(400_000)
N, *ab = map(int, open(0).read().split())
g = [[] for _ in range(N)]
for a, b in zip(*[iter(ab)] * 2):
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)

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

Submission status: Accepted

Solution code:
from collections import defaultdict, deque
import sys
input = sys.stdin.readline
N = int(input())
ab = [list(map(int,input().split())) for i in range(N-1)]

g = defaultdict(list)

for a,b in ab:
    g[a].append(b)
    g[b].append(a)

dq = deque([1])
d = [10**6]*(N+1)
d[1] = 0
while dq:
    v = dq.popleft()
    for nv in g[v]:
        if d[v] + 1 < d[nv]:
            d[nv] = d[v] + 1
            dq.append(nv)
m = max(d[1:])
s = d.index(m)

dq = deque([s])
d = [10**6]*(N+1)
d[s] = 0
while dq:
    v = dq.popleft()
    for nv in g[v]:
        if d[v] + 1 < d[nv]:
            d[nv] = d[v] + 1
            dq.append(nv)
diag = max(d[1:])

if diag % 3 == 1:
    print('Second')
else:
    print('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, path=False):
        # 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)
        if path:
            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
        else: return d

    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]

    def draw(self):
        import matplotlib.pyplot as plt
        import networkx as nx

        G = nx.Graph()
        for x in range(self.n):
            for y in self.edges[x]:
                G.add_edge(x + self.decrement, y + self.decrement)
        pos = nx.spring_layout(G)
        nx.draw_networkx(G, pos)
        plt.axis("off")
        plt.show()

##################################################################################################
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()+1)%3==2 else "First")