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: Wrong Answer

Solution code:
# coding:utf-8

import sys
from collections import deque, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    G = defaultdict(list)
    for _ in range(n - 1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    def DFS(start):
        stack = deque([start])
        dist = [INF] * n
        dist[start] = 0
        max_dist = 0
        farthest_v = start
        while stack:
            curr = stack.pop()

            for next in G[curr]:
                if dist[next] != INF:
                    continue
                dist[next] = dist[curr] + 1
                stack.append(next)
                if dist[next] > max_dist:
                    max_dist = dist[next]
                    farthest_v = next

        return farthest_v, max_dist

    v, d = DFS(0)
    u, d = DFS(v)

    print('First' if ((d + 1) // 2) % 2 else 'Second')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

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

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

centroid = []
size = [0] * N
def dfs(v,prev):
    size[v] = 1
    is_centroid = True
    for to in es[v]:
        if to == prev: continue
        dfs(to,v)
        size[v] += size[to]
        if size[to] > N//2: is_centroid = False
    if N - size[v] > N//2: is_centroid = False
    if is_centroid:
        centroid.append(v)
dfs(0,-1)

print('First' if len(centroid)%2 else 'Second')

Submission status: Wrong Answer

Solution code:
N = int(input())
edge = [[] for i in range(N)]
connect = [0] * N
for i in range(N-1):
  a, b = map(int,input().split())
  edge[a-1] += [b-1]
  edge[b-1] += [a-1]
  connect[a-1]+=1
  connect[b-1]+=1

bunki = []
for i in range(N):
  if connect[i] >= 3:
    bunki += [i]
flag = 0
for p in bunki:
  ell = 0
  for q in edge[p]:
    if connect[q] > 1:
      ell += 1
  if ell > 1:
    flag = 1#Firstが勝てる

if len(bunki) == 0:
  flag = 1
else:
  p = bunki.pop()
  if connect[p] == N-1:
    flag = 1

if N == 1:
  flag = 0
  
if flag:
  print("First")
else:
  print("Second")

Submission status: Wrong Answer

Solution code:
n,*a=open(0).read().split()
print(['Second','First'][a.count(n)%2])

Submission status: Wrong Answer

Solution code:
N = int(input())
edge = [[] for i in range(N)]
connect = [0] * N
for i in range(N-1):
  a, b = map(int,input().split())
  edge[a-1] += [b-1]
  edge[b-1] += [a-1]
  connect[a-1]+=1
  connect[b-1]+=1

bunki = []
for i in range(N):
  if connect[i] >= 3:
    bunki += [i]
flag = 0
for p in bunki:
  ell = 0
  for q in edge[p]:
    if connect[q] > 1:
      ell += 1
  if ell > 1:
    flag = 1#Firstが勝てる

if len(bunki) == 0:
  flag = 1
else:
  p = bunki.pop()
  if connect[p] == N-1:
    flag = 1
  
if flag:
  print("First")
else:
  print("Second")

Submission status: Wrong Answer

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

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)

centroid = []
size = [0] * N
def dfs(v,prev):
    size[v] = 1
    is_centroid = True
    for to in es[v]:
        if to == prev: continue
        dfs(to,v)
        size[v] += size[to]
        if size[to] > N//2: is_centroid = False
    if N - size[v] > N//2: is_centroid = False
    if is_centroid:
        centroid.append(v)
dfs(0,-1)

print('First' if len(centroid)%2 else 'Second')

Submission status: Wrong Answer

Solution code:
N = int(input())

a = []
b = []

for i in range(N-1):
    A, B = list(map(int, input().split()))
    a.append(A)
    b.append(B)

flag = False
for i in range(1, N+1):
    if not i in a:
        flag = True
        break
    if not i in b:
        flag = True
        break

if N % 2 == 0 and flag == False:
    print('Second')
elif N % 2 == 1 and flag == False:
    print('First')
elif N % 2 == 0 and flag == True:
    print('First')
else:
    print('Second')

Submission status: Wrong Answer

Solution code:
N = int(input())

a = []
b = []

for i in range(N-1):
    A, B = list(map(int, input().split()))
    a.append(A)
    b.append(B)

flag = False
for i in range(1, N+1):
    if i in a:
        flag = True
        break
    if i in b:
        flag = True

if N % 2 == 0 and flag == False:
    print('Second')
elif N % 2 == 1 and flag == False:
    print('First')
elif N % 2 == 0 and flag == True:
    print('First')
else:
    print('Second')

Submission status: Wrong Answer

Solution code:
# coding:utf-8

import sys
from collections import deque, defaultdict

INF = float('inf')
MOD = 10 ** 9 + 7
dy, dx = (0, -1, 0, 1), (1, 0, -1, 0)

def LI(): return [int(x) for x in sys.stdin.readline().split()]
def LI_(): return [int(x) - 1 for x in sys.stdin.readline().split()]
def LS(): return sys.stdin.readline().split()
def II(): return int(sys.stdin.readline())
def SI(): return input()


def main():
    n = II()
    G = defaultdict(list)
    for _ in range(n - 1):
        a, b = LI_()
        G[a].append(b)
        G[b].append(a)

    def DFS(start):
        stack = deque([start])
        dist = [INF] * n
        dist[start] = 0
        max_dist = 0
        farthest_v = start
        while stack:
            curr = stack.pop()

            for next in G[curr]:
                if dist[next] != INF:
                    continue
                dist[next] = dist[curr] + 1
                stack.append(next)
                if dist[next] > max_dist:
                    max_dist = dist[next]
                    farthest_v = next

        return farthest_v, max_dist

    v, d = DFS(0)
    u, d = DFS(v)

    # print(v + 1, u + 1, d)
    if d == 2: d = 1
    print('First' if d % 2 else 'Second')

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
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)

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 E[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%2==0:
    print("Second")
else:
    print("First")

Submission status: Wrong Answer

Solution code:
N = int(input())

a = []
b = []

for i in range(N-1):
    A, B = list(map(int, input().split()))
    a.append(A)
    b.append(B)

if N % 2 == 0 and N < 50:
    print('Second')
elif N % 2 == 1 and N < 50:
    print('First')
elif N % 2 == 0 and N >= 50:
    print('First')
else:
    print('Second')

Submission status: Wrong Answer

Solution code:
N = int(input())

a = []
b = []

for i in range(N-1):
    A, B = list(map(int, input().split()))
    a.append(A)
    b.append(B)

if N % 2 == 0:
    print('Second')
else:
    print('First')

Submission status: Wrong Answer

Solution code:
N = int(input())
if (N % 2) == 1:
  print('First')
else:
  print('Second')

Submission status: Wrong Answer

Solution code:
n = int(input())
if n % 2 == 0:
  print("Second")
else:
  print("First")

Submission status: Wrong Answer

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

n = int(input())
coupl = [[] for _ in range(n)]
for _ in range(n-1):
    u,v = [int(x)-1 for x in input().split()]
    
    coupl[u].append(v)
    coupl[v].append(u)

leaves = [i for i in range(n) if len(coupl[i])<=1]

if len(leaves)%2==1:
    print 'First'
else:
    print 'Second'

Submission status: Time Limit Exceeded

Solution code:
#Solve this by Rerooting
import sys
from itertools import accumulate
import queue
input = sys.stdin.buffer.readline

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


#bfs、直すの面倒なので読み替えて。
dfs_order = []
parent = [-1] * N
root = 0
#queue
stack = queue.Queue()
stack.put(root)
while not stack.empty():
    node = stack.get()
    dfs_order.append(node)
    for next_node in adj[node]:
        if next_node != parent[node]:
            parent[next_node] = node
            stack.put(next_node)

dp1 = [1] * N
for node in reversed(dfs_order):
    for next_node in adj[node]:
        if next_node != parent[node]:
            dp1[node] = max(dp1[node], dp1[next_node] + 1)

dp2 = [1] * N
for node in dfs_order:
    around = [dp1[next_node]+1 if next_node != parent[node] else dp2[node] for next_node in adj[node]]
    from_left = [1] + list(accumulate(around, max))[:-1]
    from_right = list(accumulate(reversed(around), max))[-2::-1] + [1]
    without = [max(l, r) + 1 for l, r in zip(from_left, from_right)]
    for next_node, value in zip(adj[node], without):
        if next_node != parent[node]:
            dp2[next_node] = value

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

length = max(dp)

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

Submission status: Time Limit Exceeded

Solution code:
import sys

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

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

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

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


def solve():
    def gather(node, p):
        md1, md2 = 0, 0
        for x in adj[node]:
            if x != p:
                dx = gather(x, node)
                if md1 < dx:
                    md2 = md1
                    md1 = dx
                elif md2 < dx:
                    md2 = dx
        depth[node] = (md1, md2)
        return 1 + md1

    gather(0, -1)

    def distribute(node, p):
        d1, d2 = depth[node]
        if p >= 0:
            pd1, pd2 = depth[p]
            if pd1 == 1 + d1:
                pd1 = pd2
            if d2 < pd1 + 1:
                d2 = pd1 + 1
        max_len = d1 + d2 + 1
        for x in adj[node]:
            if x != p:
                l = distribute(x, node)
                if max_len < l:
                    max_len = l
        return max_len

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


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

Submission status: Time Limit Exceeded

Solution code:
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)

#find the longest path by trying BFS twice.
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)

#The 'node' gives one end of the longest path.
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")

Submission status: Time Limit Exceeded

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

Submission status: Time Limit Exceeded

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)
        
    d = 0
    for st in range(N):
        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)
        d = max(d,max(dep))
        
    if d%3 == 1:
        print("Second")
    else:
        print("First")

if __name__ == "__main__":
    main()

Submission status: Time Limit Exceeded

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

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

def dfs(cur, cost):
    dist[cur] = cost
    for to in G[cur]:
        if dist[to] == -1:
            dfs(to, cost+1)
dist = [-1]*n
dfs(0, 0)
m = max(dist)
for i in range(n):
    if dist[i] == m:
        start = i
        break
dist = [-1]*n
dfs(start, 0)
m = max(dist)

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

Submission status: Time Limit Exceeded

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

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

def dfs(cur, cost):
    dist[cur] = cost
    for to in G[cur]:
        if dist[to] == -1:
            dfs(to, cost+1)
dist = [-1]*n
dfs(0, 0)
m = max(dist)
for i in range(n):
    if dist[i] == m:
        start = i
        break
dist = [-1]*n
dfs(start, 0)
m = max(dist)

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

Submission status: Time Limit Exceeded

Solution code:
import queue
n = int(input())

tree = {i: [] for i in range(n)}

for _ in range(n-1):
  t = input().split()
  u, v = int(t[0]), int(t[1])
  tree[u-1].append(v-1)
  tree[v-1].append(u-1)

a = 0
q = queue.Queue()
q.put(a)
v = [0 for _ in range(n)]
v[a] = 1

while (not q.empty()):
    a = q.get()
    for b in tree[a]:
        if (v[b] == 0):
            q.put(b)
            v[b] = 1

s = a
q = queue.Queue()
q.put([a, 1])
v = [0 for _ in range(n)]
v[a] = 1

while (not q.empty()):
    a = q.get()
    for b in tree[a[0]]:
        if (v[b] == 0):
            q.put([b, a[1] + 1])
            v[b] = 1

l = a[1]
if l%3 == 2:
    print("Second")
else:
    print("First")

Submission status: Time Limit Exceeded

Solution code:
import queue
n = int(input())

tree = {i: [] for i in range(n)}

for _ in range(n-1):
  u, v = map(int, input().split())
  tree[u-1].append(v-1)
  tree[v-1].append(u-1)

a = 0
q = queue.Queue()
q.put(a)
v = [0 for _ in range(n)]
v[a] = 1

while (not q.empty()):
    a = q.get()
    for b in tree[a]:
        if (v[b] == 0):
            q.put(b)
            v[b] = 1

s = a
q = queue.Queue()
q.put([a, 1])
v = [0 for _ in range(n)]
v[a] = 1

while (not q.empty()):
    a = q.get()
    for b in tree[a[0]]:
        if (v[b] == 0):
            q.put([b, a[1] + 1])
            v[b] = 1

l = a[1]
if l%3 == 2:
    print("Second")
else:
    print("First")

Submission status: Time Limit Exceeded

Solution code:
import sys
import heapq
sys.setrecursionlimit(10**6)
INF = 10**9

n = int(input())
edge = [[] for _ in range(n)]

def get_max_dist(frm, n, dist):
    val = 0
    index = -1
    for item in edge[n]:
        if item == frm:
            if len(edge[n]) == 1:
                return dist, n
            continue
        tmp, tindex = get_max_dist(n, item, dist+1)
        if val < tmp:
            val = tmp
            index = tindex
    return val, index

for i in range(n-1):
    a, b = [int(item) for item in input().split()]
    a -= 1; b -= 1
    edge[a].append(b)
    edge[b].append(a)

val, left = get_max_dist(-1, 0, 0)
diam, right = get_max_dist(-1, left, 0)

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

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse import*;n,*t=map(int,open(0).read().split());b=csgraph.dijkstra;c=csr_matrix(([1]*~-n,(t[::2],t[1::2])),[n+1]*2);print('SFeicrosntd'[b(c,0,b(c,0,1)[1:].argmax()+1)[1:].max()%3!=1::2])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(210000)
def s(x,v,d):
  r=[d,v]
  for u in g[v]:
    if u!=x:
      t=s(v,u,d+1)
      if r[0]<t[0]:r=t
  return r
n,*t=map(int,open(0).read().split())
g=[set()for _ in range(n+1)]
for a,b in zip(t[::2],t[1::2]):
  g[a].add(b)
  g[b].add(a)
print('SFeicrosntd'[s(0,s(0,1,0)[1],0)[0]%3!=1::2])

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)
def s(x,v,d):
  r=[d,v]
  for u in g[v]:
    if u!=x:
      t=s(v,u,d+1)
      if r[0]<t[0]:r=t
  return r
n,*t=map(int,open(0).read().split())
g=[set()for _ in range(n+1)]
for a,b in zip(t[::2],t[1::2]):
  g[a].add(b)
  g[b].add(a)
print('SFeicrosntd'[s(0,s(0,1,0)[1],0)[0]%3!=1::2])

Submission status: Time Limit Exceeded

Solution code:
def diameter(N, E):#diamete of a tree
    V = [-1]*N
    V[0] = 0
    q = [0]
    s = 0
    while q:
        v = q.pop(0)
        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 = [s]
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.pop(0)
        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: Time Limit Exceeded

Solution code:
def diameter(N, E):#diamete of a tree
    V = [-1]*N
    V[0] = 0
    q = [0]
    while q:
        v = q.pop(0)
        for w in E[v]:
            if V[w] == -1:
                V[w] = V[v] + 1
                q.append(w)
    s = V.index( max(V))
    p = [s]
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.pop(0)
        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: Time Limit Exceeded

Solution code:
def diameter(N, E):#diamete of a tree
    V = [-1]*N
    V[0] = 0
    q = [0]
    while q:
        v = q.pop(0)
        ev = V[v]
        for w in E[v]:
            if V[w] == -1:
                V[w] = ev + 1
                q.append(w)
    s = V.index( max(V))
    p = [s]
    W = [-1]*N
    W[s] = 0
    while p:
        v = p.pop(0)
        ev = W[v]
        for w in E[v]:
            if W[w] == -1:
                W[w] = ev + 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: Time Limit Exceeded

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

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

tree = defaultdict(list)
nodes_len = defaultdict(list)
for i in range(N):
    nodes_len[i+1] = [0, 0]

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

while len(tree) > 1:
    del_nodes = []
    for from_node, to_nodes in list(tree.items()):
        # dictのサイズが1なら
        if len(to_nodes) == 1:
            to_node = to_nodes[0]

            # そのノードが持つ隣接ノード長を追加する
            nodes_len[to_node].append(nodes_len[from_node][0]+1)

            # 長さが2以上のみ保持する
            nodes_len[to_node].sort(reverse=True)
            nodes_len[to_node] = nodes_len[to_node][:2]

            # treeのto_nodeの部分から削除する
            tree[to_node].remove(from_node)

            # 自分を削除する
            del tree[from_node]

n = list(tree.keys())[0]
print("Second" if (nodes_len[n][0] + nodes_len[n][1]+1) % 3 == 2 else "First")

Submission status: Time Limit Exceeded

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

N = int(input())

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

tree = defaultdict(list)
nodes_len = defaultdict(list)
for i in range(N):
    nodes_len[i+1] = [0, 0]

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

while len(tree) > 1:
    del_nodes = []
    for from_node, to_nodes in tree.items():
        # dictのサイズが1なら
        if len(to_nodes) == 1:
            to_node = to_nodes[0]

            # そのノードが持つ隣接ノード長を追加する
            nodes_len[to_node].append(nodes_len[from_node][0]+1)

            # 長さが2以上のみ保持する
            nodes_len[to_node].sort(reverse=True)
            nodes_len[to_node] = nodes_len[to_node][:2]

            # treeのto_nodeの部分から削除する
            tree[to_node].remove(from_node)

            del_nodes.append(from_node)

    for node in del_nodes:
        del tree[node]

n = list(tree.keys())[0]
print("Second" if (nodes_len[n][0] + nodes_len[n][1]+1) % 3 == 2 else "First")

Submission status: Time Limit Exceeded

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

N = int(input())

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

tree = defaultdict(list)
nodes_len = defaultdict(list)
for i in range(N):
    nodes_len[i+1] = [0, 0]

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

queue_set = set()
while len(tree) > 1:
    del_nodes = []
    for from_node, to_nodes in tree.items():
        # dictのサイズが1なら
        if len(to_nodes) == 1:
            to_node = to_nodes[0]

            # queueに次のノードを入れる
            queue_set.add(to_node)

            # そのノードが持つ隣接ノード長を追加する
            nodes_len[to_node].append(nodes_len[from_node][0]+1)

            # 長さが2以上のみ保持する
            nodes_len[to_node].sort(reverse=True)
            nodes_len[to_node] = nodes_len[to_node][:2]

            # treeのto_nodeの部分から削除する
            tree[to_node].remove(from_node)

            del_nodes.append(from_node)

    for node in del_nodes:
        del tree[node]

n = list(tree.keys())[0]
print("Second" if (nodes_len[n][0] + nodes_len[n][1]+1) % 3 == 2 else "First")

Submission status: Time Limit Exceeded

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 diameter(tree):
    _, s = farest(tree, 1)
    diam, _ = farest(tree, s)
    return diam


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

    while len(cand_q) > 0:
        u = cand_q.popleft()
        for edge in tree:
            if u in edge:
                v = edge[0] if u == edge[1] else edge[1]
                if dp[v-1] is None:
                    cand_q.append(v)
                    dp[v-1] = dp[u-1] + 1
    max_ = max(dp)
    i_max = dp.index(max_)
    return max_, i_max + 1


d = diameter(edges)


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

# def farest_vtx(tree, i):
#     cand = deque(tree)
#     for edge in cand:
#         if i in edge:

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

    while distance_count < nodecount:
        vlist_next = set()
        for v in vlist:
            distance_list[v] = distance
            distance_count += 1
            vlist_next = vlist_next | ((set(linklist[v]) - vlist_previous))
        distance += 1
        vlist_previous = vlist
        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:
# C問題 20分で最長の長さの道の含むノードの数Nに対して
# N%3 == 2ならS, それ以外でFであることまでわかった。
# !!直径rでいうとr%3 ==1 ならS
# しかし、longest path problemはNP hardとか言われた... 
# けど、treeであることを考慮に入れて再検索すると行けた。
# ググり力 = 関連ワードを色々入れて試す力 & 関係なさそうなテーマから早く撤退する

# 木の直径というらしい
# 木DP or 適当に初期点W　→ Wからの最遠点U　→ Uからの最遠点V でUとVの距離でわかるらしい。

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 = []
    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]
        # bestの更新
        if currentLength > best[1]:
            best = [currentPosition, currentLength]
        visited.append(currentPosition)
        # 繋がっているノードのうち未探索の場所を追加
        for position in E[currentPosition]:
            if position not in visited:
                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: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import heapq
INF = float("inf")


def argmax(a):
    m, n = -(1 << 31), -1
    for i, v in enumerate(a):
        if m < v:
            m, n = v, i
    return m, n

# 無向グラフを仮定する。


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.V = list(range(N))
        self.E = [[] for _ in range(N)]

    def add_edge(self, edge):
        """辺を加える。edgeは(始点, 終点、重み)からなるリスト
        重みがなければ、重み1とする。
        """
        if len(edge) == 2:
            edge.append(1)
        elif len(edge) != 3:
            print("error in add_edge")
            pass

        s, t, w = edge
        self.E[s].append([t, w])
        self.E[t].append([s, w])  # 無向グラフを仮定。逆向きにも辺を張る

        pass


def shortestPath(g: Graph, s: int):
    """ グラフgにおいて、始点sから各頂点への最短路を求める
    引数
    g: グラフ, s: 始点
    返り値
    dist: 始点からの距離が格納されたリスト
    prev: 始点から最短経路で移動する場合、各頂点に至る前の頂点のリスト
    """
    dist = [INF]*g.N
    dist[s] = 0

    prev = [None]*g.N
    Q = []
    heapq.heappush(Q, (dist[s], s))

    while len(Q) > 0:
        _, u = heapq.heappop(Q)
        for v, w in g.E[u]:
            if dist[v] > dist[u] + w:
                dist[v] = dist[u] + w
                prev[v] = u
                heapq.heappush(Q, (dist[v], v))
    return dist, prev


def tree_diameter(g):
    # 木の直径を求める。
    # ダイクストラ法を二回行う実装。
    dist, prev = shortestPath(g, 0)
    m, s = argmax(dist)
    dist, prev = shortestPath(g, s)
    return max(dist)


def solve(N: int, a: "List[int]", b: "List[int]"):
    g = Graph(N)
    for aa, bb in zip(a, b):
        g.add_edge([aa-1, bb-1])

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


def main():

    def iterate_tokens():
        for line in sys.stdin:
            for word in line.split():
                yield word
    tokens = iterate_tokens()
    N = int(next(tokens))  # type: int
    a = [int()] * (N-1)  # type: "List[int]"
    b = [int()] * (N-1)  # type: "List[int]"
    for i in range(N-1):
        a[i] = int(next(tokens))
        b[i] = int(next(tokens))
    solve(N, a, b)


if __name__ == '__main__':
    main()