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:
import sys, collections
def single_input(F): return F.readline().strip("\n")
def line_input(F): return F.readline().strip("\n").split()

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

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

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

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

Submission status: Accepted

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

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


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

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

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

Submission status: Accepted

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


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

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

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

Submission status: Accepted

Solution code:
from collections import defaultdict

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

# 木構造の関係リスト作成
treeDict = defaultdict(list)
for a, b in abList:
    treeDict[a].append(b)
    treeDict[b].append(a)

# コストの辞書と疑似キューを作成
costDict = defaultdict(int)
treeQ = set()

# 葉(端)のコストを1にし、隣接ノードをキューに格納
for node in treeDict:
    if len(treeDict[node]) == 1:
        costDict[node] = 1
        treeQ.add(treeDict[node][0])

# 1つを除く隣接ノードにコストが設定されている(!= 0)場合、
# 隣接ノードの最大コスト + 1 でコストを設定し、コスト未設定のノードをキューに格納。
# 上記をキューに値が入らなくなるまで繰り返す。
node = 1
while(treeQ):
    tQ = set()
    costList = []
    for node in treeQ:
        if costDict[node] != 0: break
        decidedFlg = True
        cost = -1
        qNode = -1
        for nextNode in treeDict[node]:
            nextCost = costDict[nextNode]
            if nextCost == 0:
                # 隣接ノードがコスト未設定ならキューに格納
                # 隣接ノードが2つコスト未設定ならbreak
                if not decidedFlg:
                    cost = -1
                    qNode = -1
                    break
                decidedFlg = False
                qNode = nextNode
            else:
                # コストが設定されていれば大きいコストで更新
                cost = max(cost, nextCost + 1)

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

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


# コストが設定されていないノードを頂点として直径を図る
firstLen, secondLen = 0, 0
for nextNode in treeDict[node]:
    cost = costDict[nextNode]
    if cost > firstLen:
        secondLen = firstLen
        firstLen = cost
    elif cost > secondLen:
        secondLen = cost

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

Submission status: Accepted

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


N = int(input())
# 例外処理
if (N == 1):
    print("First")
    quit()

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

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

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

    return one_step_node, cnt


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

Submission status: Accepted

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

Submission status: Accepted

Solution code:
N = int(input())
src = [tuple(map(lambda x:int(x)-1,input().split())) for i in range(N-1)]
es = [[] for i in range(N)]
for a,b in src:
    es[a].append(b)
    es[b].append(a)

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

Submission status: Accepted

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

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

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

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

Submission status: Accepted

Solution code:
from collections import deque

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

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

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


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

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

Submission status: Accepted

Solution code:
from collections import deque
import sys

input = sys.stdin.readline

N = int(input())
e = [[] for _ in range(N)]
# 隣接リスト

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


# BFS*2で直径を求める
def bfs(i):
    """
    :param i: bfsの始点, 0-indexed
    :return: (v,d), iの最遠点vまでの距離d
    """
    dist = [-1 for _ in range(N)]
    dist[i] = 0

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


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

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

Submission status: Accepted

Solution code:
from collections import deque

N = int(input())
e = [[] for _ in range(N)]
# 隣接リスト

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

# BFS*2で直径を求める
dist = [-1 for _ in range(N)]
dist[0] = 0

q = deque()
q.append(0)

while q:
    v = q.popleft()
    d = dist[v]
    for nv in filter(lambda x: dist[x] == -1, e[v]):
        dist[nv] = d + 1
        q.append(nv)
# 探索終了後
# (v,d)=頂点0から最遠点の頂点番号v,頂点0からの距離d

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

q = deque()
q.append(v)

while q:
    w = q.popleft()
    d = dist[w]
    for nw in filter(lambda x: dist[x] == -1, e[w]):
        dist[nw] = d + 1
        q.append(nw)
# 探索終了後
# (w,d)=頂点vから最遠点の頂点番号w,頂点vからの距離d

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

Submission status: Accepted

Solution code:

from collections import deque
import numpy as np

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

# グラフのうち最も遠い2点の距離(木の直径)を求める
# 1. 適当な点からの最も遠い点uを求める
# 2. uから最も遠い点を求める
# 全探索×2

def bfs(graph,root):
    distance  = [0]*N
    visited = set()
    queue = deque([root])
    while len(queue) > 0:
        vertex = queue.popleft()
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                distance[neighbour] = distance[vertex] + 1
                visited.add(neighbour)
                queue.append(neighbour)

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

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

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

Submission status: Accepted

Solution code:

from collections import deque
import numpy as np

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

# グラフのうち最も遠い2点の距離(木の直径)を求める
# 1. 適当な点からの最も遠い点uを求める
# 2. uから最も遠い点を求める
# 全探索×2

def bfs(graph,root):
    distance  = [0]*N
    visited = [False]*N
    visited[root] = True
    queue = deque([root])

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

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

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

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

Submission status: Accepted

Solution code:

from collections import deque
import numpy as np

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

# グラフのうち最も遠い2点の距離(木の直径)を求める
# 1. 適当な点からの最も遠い点uを求める
# 2. uから最も遠い点を求める
# 全探索×2

def bfs(graph,root):
    distance  = [0]*N
    visited = set()
    queue = deque([root])
    while queue:
        vertex = queue.popleft()
        for neighbour in graph[vertex]:
            if neighbour not in visited:
                distance[neighbour] = distance[vertex] + 1
                visited.add(neighbour)
                queue.append(neighbour)

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

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

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

Submission status: Accepted

Solution code:
import collections
N=int(input())
inarr=[[int(j) for j in input().split()] for i in range(N-1)]
nodes={}
if N == 1:
    print("First")
    exit()

for i,j in inarr:
    if not i in nodes: nodes[i] = [j]
    else: nodes[i].append(j)
    if not j in nodes: nodes[j] = [i]
    else: nodes[j].append(i)

visited = {1}
queue = collections.deque([[1, 0]])
while queue:
    i, d = queue.popleft()
    for node in nodes[i]:
        if not node in visited:
            visited.add(node)
            queue += [[node, d + 1]]

# print("i: {} d: {}".format(i,d))

visited = {i}
queue = collections.deque([[i, 0]])
while queue:
    i, d = queue.popleft()
    for node in nodes[i]:
        if not node in visited:
            visited.add(node)
            queue += [[node, d + 1]]

# print(list(map(str,nodes.values())))
# print("i: {} d: {}".format(i,d))
print('Second' if (d + 1) % 3 == 2 else 'First')

Submission status: Accepted

Solution code:
import collections
N = int(input())
AB = [[int(_) for _ in input().split()] for _ in range(N - 1)]
G = collections.defaultdict(set)
for a, b in AB:
    G[a].add(b)
    G[b].add(a)
visited = [False] * (N + 1)
visited[1] = True
Q = collections.deque([1])
while Q:
    i = Q.popleft()
    for j in G[i]:
        if not visited[j]:
            visited[j] = True
            Q += [j]
visited = [False] * (N + 1)
visited[i] = True
Q = collections.deque([[i, 0]])
while Q:
    i, d = Q.popleft()
    for j in G[i]:
        if not visited[j]:
            visited[j] = True
            Q += [[j, d + 1]]
if (d + 1) % 3 == 2:
    print('Second')
else:
    print('First')

Submission status: Accepted

Solution code:
# input
n = int(input())
edges = set(tuple(int(i) for i in input().split()) for _ in range(n-1))


from collections import deque


def make_connection(tree):
    con = [[] for _ in range(n+1)]
    for edge in tree:
        con[edge[0]].append(edge[1])
        con[edge[1]].append(edge[0])
    return con


def diameter(tree):
    c = make_connection(tree)
    _, s = farest(tree, c, 1)
    diam, _ = farest(tree, c, s)
    return diam


def farest(tree, con, i):
    dp = [None for _ in range(n+1)]
    dp[i] = 0
    cand_q = deque()
    cand_q.append(i)

    while len(cand_q) > 0:
        u = cand_q.popleft()

        for v in con[u]:
            if dp[v] is None:
                cand_q.append(v)
                dp[v] = dp[u] + 1
    max_ = max(dp[1:])
    i_max = dp.index(max_)
    return max_, i_max


d = diameter(edges)


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

Submission status: Accepted

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

from bisect import bisect_left as binl
from copy import copy, deepcopy

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 = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    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: Accepted

Solution code:
from collections import deque
from heapq import heappush,heappop
import re
def int_raw():
    return int(input())

def ss_raw():
    return input().split()

def ints_raw():
    return list(map(int, ss_raw()))

INF = 1<<29

def getDeci(tree):
    def saiki(v):
        root = [0,v,-1]
        cur = None
        qu = deque()
        qu.append(root)
        while len(qu)!=0:
            cur = qu.popleft()
            for e in tree[cur[1]]:
                if e ==cur[2]:
                    continue
                qu.append([cur[0]+1,e,cur[1]])
        return cur
    leaf = saiki(0)
    ans = saiki(leaf[1])
    return ans

    
N = int_raw()
tree = [[] for _ in range(N)]
for _ in range(N-1):
    a,b = ints_raw()
    a = a-1
    b = b-1
    tree[a].append(b)
    tree[b].append(a)



def main():
    ans = getDeci(tree)
    if (ans[0]+2)%3==0:
        return "Second"
    else:
        return "First"

print(main())

Submission status: Accepted

Solution code:
def getD(graph):
    # search edge
    origin=1
    d = 0
    queue = Queue()
    for it in graph[origin]:
        queue.enqueue((it, origin, d+1)) # next, coming from, depth

    while queue.size() > 0:
        leaf, origin, d = queue.dequeue()
        for it in graph[leaf]:
            if it != origin:
                queue.enqueue((it, leaf, d+1)) # next, coming from, depth
    # print(d, leaf)

    # search D
    origin=leaf
    d = 0
    queue = Queue()
    for it in graph[origin]:
        queue.enqueue((it, origin, d+1)) # next, coming from, depth

    while queue.size() > 0:
        leaf, origin, d = queue.dequeue()
        for it in graph[leaf]:
            if it != origin:
                queue.enqueue((it, leaf, d+1)) # next, coming from, depth
    # print(d, leaf)
    return d

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None


class Queue:
    def __init__(self):
        self.head = None
        self.last = None
        self._size = 0

    def enqueue(self, data):
        if self.last is None:
            self.head = Node(data)
            self.last = self.head
        else:
            self.last.next = Node(data)
            self.last = self.last.next
            
        self._size += 1

    def dequeue(self):
        if self.head is None:
            return None
        else:
            to_return = self.head.data
            self.head = self.head.next
            self._size -= 1
            
            if self._size == 0:
                self.head = None
                self.last = None
            return to_return
        
    def size(self):
        return self._size
    
def inside(y,x,H,W):
    if 0<=y<H and 0<=x<W:
        return True
    else:
        return False
    
def addQueueIfPossible(new_y, new_x, new_val, data, queue):
    if inside(new_y, new_x, H, W) and data[new_y][new_x]==-1:
        data[new_y][new_x] = new_val
        queue.enqueue((new_y, new_x, new_val))
        return True
    else:
        return False


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

if n==1:
    print('First')
else:
    d = getD(graph)

    if (d+2)%3==0:
        print('Second')
    else:
        print('First')

Submission status: Accepted

Solution code:
# カンニングして修正
N = int(input())
#各頂点が繋がってる辺リスト
E = [ [] for _ in range(N)]
for i in range(N-1):
    a,b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)

# #入力1
# N= 3
# E= [[1], [0, 2], [1]]

# #　入力2
# N= 6
# E= [[1], [0, 2, 3], [1], [1, 5], [5], [3, 4]]

# #　入力3
# N= 7
# E= [[6, 1], [0], [3, 5], [6, 2], [6], [2], [0, 3, 4]]


    
def farthest(s):
    visited = [False]*N
    stack = [[s,0]]
    best = [s,0]
    while len(stack)>0:
#         print("visited:",visited)
#         print("stack:",stack)
        current = stack.pop()#pop(-1)と同じ
        currentPosition = current[0] 
        currentLength = current[1]
        visited[currentPosition] = True
        # bestの更新
        if currentLength > best[1]:
            best = [currentPosition, currentLength]
        visited.append(currentPosition)
        # 繋がっているノードのうち未探索の場所を追加
        for position in E[currentPosition]:
            if not visited[position]:
                stack.append([position, currentLength+1])
    return best

# print("u,length:",farthest(0))
u = farthest(0)[0]
best = farthest(u)
# print(best)
# v = best[0]
diameter = best[1]
# print(diameter)
ans = "First"
if diameter % 3 == 1:
    ans = "Second"
print(ans)

Submission status: Accepted

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 = {}
    distance_count = 0
    distance = 0
    vlist_previous = []
    vlist = [v]
    nodecount = len(linklist)

    while distance_count < nodecount:
        vlist_next = []
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next.extend(linklist[v])
        distance += 1
        vlist_to_del = vlist_previous
        vlist_previous = vlist
        vlist = list(set(vlist_next) - set(vlist_to_del))

    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: Accepted

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


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 = collections.deque(n for n in nodes if len(n.edges) == 1)

  while True:
    leaf = leaves.popleft()
    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: Accepted

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


def farthest(s):
	visited = [False] * N
	stack = [(s, 0)]
	best = s, 0
	while stack:
		i, d = stack.pop()
		visited[i] = True
		if best[1] < d:
			best = i, d
		stack.extend((v, d + 1) for v in E[i] if not visited[v])
	return best

print('First' if (farthest(farthest(0)[0])[1] % 3 != 1) else 'Second')

Submission status: Accepted

Solution code:
from collections import deque

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)


def farthest(s):
    maxlen = 0
    farthest = s
    q = deque()
    q.append((s, 0, -1))
    while len(q):
        c, l, prev = q.pop()
        if prev >= 0 and len(g[c]) <= 1:
            if l > maxlen:
                maxlen = l
                farthest = c
            continue
        for n in g[c]:
            if n != prev:
                q.append((n, l+1, c))
    return maxlen, farthest


_, a = farthest(0)
diameter, b = farthest(a)

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