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: Runtime Error

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

Submission status: Runtime Error

Solution code:
import sys
import queue

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


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


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

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

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


q = queue.Queue()
q.put(0)
visited = set()
visited.add(0)
last = 0
while not q.empty():
    n = q.get()
    last = n
    for nb in graph[n]:
        if nb not in visited:
            visited.add(nb)
            q.put(nb)

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


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

Submission status: Runtime Error

Solution code:
n = int(input())
l = [list() for _ in range(n)]
for _ in range(n-1):
  a,b = map(int,input().split())
  l[a-1].append(b-1)
  l[b-1].append(a-1)

dep = [n]*n
def dfs(v,t,p):
  dep[v] = t
  for x in l[v]:
    if x == p:
      continue
    dfs(x,t+1,v)
  return

dfs(0,0,-1)
p = dep.index(max(dep))
dep = [n]*n
dfs(p,0,-1)
q = max(dep)-1
print("First" if q%3 else "Second")

Submission status: Runtime Error

Solution code:
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: Runtime Error

Solution code:
from collections import deque

N = int(input())

dic = {}

for  i in range(N-1):

    a,b = map(int,input().split())
    a-=1
    b-=1

    if a not in dic:
        dic[a] = []
    if b not in dic:
        dic[b] = []

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

for xxx in range(1):

    lis = [float("inf")] * N
    lis[0] = 0
    maxind = 0
    q = deque([0])

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:

            if lis[nex] > lis[now] + 1:
                lis[nex] = lis[now] + 1
                q.append(nex)
                maxind = nex

    lis = [float("inf")] * N
    lis[maxind] = 1
    q = deque([maxind])
    L = 0

    while len(q) > 0:

        now = q.popleft()

        for nex in dic[now]:

            if lis[nex] > lis[now] + 1:
                lis[nex] = lis[now] + 1
                q.append(nex)
                L = lis[nex]

    #print (lis)
    #print (L)

    if L == 1 or L % 3 != 2:

        print ("First")

    else:

        print ("Second")

Submission status: Runtime Error

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

def bfs(v0):
    dist = [-1]*N
    que = deque([v0])
    dist[v0] = 0
    while que:
        v = que.pop()
        d = dist[v]
        for nv in edges[v]:
            if dist[nv] < 0:
                que.append(nv)
                dist[nv] = d+1
    m = max(dist)
    v = dist.index(d)
    return v, m
u, _ = bfs(0)
_, dia = bfs(u)
if (dia+1-2)%3 == 0:
    print('Second')
else:
    print('First')

Submission status: Runtime Error

Solution code:
# coding: utf-8
# Your code here!

from collections import deque
def diameter(g):
    def bfs(start): # v からの最長点と距離を求める
        res = [-1]*(len(g))
        q = deque([start])
        res[start] = 0
        while q:
            v = q.popleft()
            for c in g[v]:
                if res[c] >= 0: continue
                res[c] = res[v] + 1 #重みつきのときは+1でなく +cost(v,c)
                q.append(c) 
        return (res[v],v)

    d0,v0 = bfs(0)
    d1,v1 = bfs(v0)
    return d1 # i0, i1 が最遠頂点対


##################################################
# coding: utf-8
# Your code here!
import sys
sys.setrecursionlimit(10**6)
readline = sys.stdin.readline
 
n = int(input())
#n,q = [int(i) for i in readline().split()]
 
g = [[] for _ in range(n)]
for i in range(n-1):
    a,b = [int(i) for i in readline().split()]
    g[a-1].append(b-1)
    g[b-1].append(a-1)

d = diameter(g)
if d%3 != 1:
    print("First")
else:
    print("Second")
    
assert n!=6

Submission status: Runtime Error

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 and len(tree[b]) != 1):
            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 and len(tree[b]) != 1):
            q.put([b, a[1] + 1])
            v[b] = 1

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

Submission status: Runtime Error

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 and len(tree[b]) != 1):
            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 and len(tree[b]) != 1):
            q.put([b, a[1] + 1])
            v[b] = 1

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

Submission status: Runtime Error

Solution code:
import heapq
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: Runtime Error

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

Submission status: Runtime Error

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

Submission status: Runtime Error

Solution code:
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: Runtime Error

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

used = [True]*n
q = []
used[0] = False
for e in edge[0]:
    q.append(e)
    used[e] = False
while q:
    tank = []
    for elt in q:
        for e in edge[elt]:
            if used[e]:
                tank.append(e)
                used[e] = False
    if len(tank) == 0:
        start = q[0]
    q = tank

used = [True]*n
q = []
used[start] = False
for e in edge[start]:
    q.append(e)
    used[e] = False
d = 1
while q:
    tank = []
    for elt in q:
        for e in edge[elt]:
            if used[e]:
                tank.append(e)
                used[e] = False
    if tank:
        d += 1
    q = tank

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

Submission status: Runtime Error

Solution code:
from collections import defaultdict
import numpy as np
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)

print(tree.keys())


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]:
                print(from_node, one_step_node, two_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: Runtime Error

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 dfs(v, p):
    for u in adj[v]:
        if u != p:
            depth[u] = depth[v] + 1
            dfs(u, v)

depth = [0] * N
dfs(0, -1)

i = depth.index(max(depth))

depth = [0] * N

dfs(i, -1)

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

Submission status: Runtime Error

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

N = int(input())


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: Runtime Error

Solution code:
import collections
N=int(input())
inarr=[[int(j) for j in input().split()] for i in range(N-1)]
nodes={}
class Node:
    def __init__(self, parent, children, value):
        self.parent = parent
        self.children = children
        self.value = value
    
    def __str__(self):
        return "NODE[v={},par={},chld={}]".format(self.value,self.parent.value if self.parent else "none",list(map(lambda x: x.value, self.children)))

for i,j in inarr:
    if not i in nodes:
        nodes[i] = Node(None, [], i)
        if not j in nodes:
            nodes[j] = Node(nodes[i], [], j)
            nodes[i].children.append(nodes[j])
        else:
            nodes[i].parent = nodes[j]
            nodes[j].children.append(nodes[i])
    else:
        if not j in nodes:
            nodes[j] = Node(nodes[i], [], j)
            nodes[i].children.append(nodes[j])
        else:
            if not nodes[i].parent:
                nodes[i].parent = nodes[j]
                nodes[j].children.append(nodes[i])
            elif not nodes[j].parent:
                nodes[j].parent = nodes[i]
                nodes[i].children.append(nodes[j])
            else:
                print("error")

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

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

visited = {i: True}
queue = collections.deque([[i, 0]])
while queue:
    i, d = queue.popleft()
    for node in nodes[i].children:
        if not node.value in visited:
            visited[node.value] = True
            queue += [[node.value, d + 1]]
    if nodes[i].parent and not nodes[i].parent.value in visited:
        visited[nodes[i].parent.value] = True
        queue += [[nodes[i].parent.value, 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: Runtime Error

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


def farest(tree, i):
    dp = [None] * 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')

Submission status: Runtime Error

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(p,v):
        ans = [0,v]
        for e in tree[v]:
            if e ==p:
                continue
            tmp = saiki(v,e)
            tmp[0]=tmp[0]+1
            if ans[0]<tmp[0]:
                ans = tmp
        return ans
    leaf = saiki(-1,0)
    ans = saiki(-1,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: Runtime Error

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

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

Submission status: Runtime Error

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: Runtime Error

Solution code:
import numpy as np

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)


INF = N + 1
D = [INF] * N

stack = [
	i
	for i in range(N)
	if len(E[i]) == 1
]

for i in stack:
	D[i] = 0

max_d = 0
cnt = 0
while stack:
	nexts = []
	for i in stack:
		if D[i] > max_d:
			D[i] = max_d
		nexts.extend(v for v in E[i] if D[v] == INF)
	max_d += 1
    cnt = len(stacks)
	stack = nexts

Rx2 = max_d * 2 if 1 < cnt else max_d * 2 - 1
print('First' if (Rx2 % 3 != 2) else 'Second')

Submission status: Runtime Error

Solution code:
n = int(input())

a,b = [int(i) for i in input().split()]

if n%2 == 0:
    print("Second")
else:
    print("First")

Submission status: Runtime Error

Solution code:
n = int(input())

a,b = [int(i) for i in input().split()]

print(("First","Second")[n%2 == 0])

Submission status: Runtime Error

Solution code:
def dia(Node,i,j):
	lst = []
	Node.remove(i)
	if(len(Node) == 0):
		lst.append(1)
	else:
		for n in Node:
			t = dia(A[n],j,n)
			lst.append(t+1)
	return max(lst)
		
N = input()
A = [[] for i in range(N)]
for i in range(N-1):
	a2,b2 = map(int, raw_input().split())
	A[a2-1].append(b2-1)
	A[b2-1].append(a2-1)
lst = []
for n in A[0]:
	lst.append(dia(A[n],0,n))
m1 = max(lst)
lst.remove(m1)
if(len(lst) == 0):
	m2 = 1
else:
	m2 = max(lst)+1
if((m1 + m2) % 3 == 2):
	print("Second")
else:
	print("First")

Submission status: Runtime Error

Solution code:
def dia(Node):
	lst = []
	if(len(Node) == 0):
		lst.append(1)
	else:
		for n in Node:
			t = dia(d[n])
			lst.append(t+1)
	return max(lst)
		
N = input()
A = []
for i in range(N-1):
	a2,b2 = map(int, raw_input().split())
	if(a2 > b2):
		a2,b2 = b2,a2
	k = [a2,b2]
	A.append(k)
root = A[0][0]
rootd = [A[0][1]]
d = {A[0][0]:[A[0][1]],A[0][1]:[]}
A.pop(0)
for a2 in A:
	if(a2[0] in d):
		t = d[a2[0]]
		n = a2[1]
	elif(a2[1] in d):
		t = d[a2[1]]
		n = a2[0]
	else:
		A.append(a2)
		continue
	t.append(n)
	d[n] = []
lst = []
for n in d[root]:
	lst.append(dia(d[n]))
m1 = max(lst)
lst.remove(m1)
if(len(lst) == 0):
	m2 = 1
else:
	m2 = max(lst)+1
if((m1 + m2) % 3 == 2):
	print("Second")
else:
	print("First")

Submission status: Runtime Error

Solution code:
def dia(Node):
	lst = []
	if(len(Node) == 0):
		lst.append(1)
	else:
		for n in Node:
			t = dia(d[n])
			lst.append(t+1)
	return max(lst)
		
N = input()
A = []
for i in range(N-1):
	a2,b2 = map(int, raw_input().split())
	if(a2 > b2):
		a2,b2 = b2,a2
	k = [a2,b2]
	A.append(k)
root = A[0][0]
rootd = [A[0][1]]
d = {A[0][0]:[A[0][1]],A[0][1]:[]}
for i in range(1,N-1):
	if(A[i][0] in d):
		t = d[A[i][0]]
		n = A[i][1]
	elif(A[i][1] in d):
		t = d[A[i][1]]
		n = A[i][0]
	t.append(n)
	d[n] = []
lst = []
for n in d[root]:
	lst.append(dia(d[n]))
m1 = max(lst)
lst.remove(m1)
if(len(lst) == 0):
	m2 = 1
else:
	m2 = max(lst)+1
if((m1 + m2) % 3 == 2):
	print("Second")
else:
	print("First")

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

conn = [len(v) for v in adj]
min_ind = conn.index(1)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1 and prev in adj[cur]:
        return dist
    else:
        ret = 0
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = max(ret, dfs(n, cur, dist+1))
        return ret


D = dfs(min_ind, -1, 0)+1
if D % 3 != 1:
    print("First")
else:
    print("Second")

Submission status: Runtime Error

Solution code:
# python template for atcoder1
import sys
sys.setrecursionlimit(10**9)
input = sys.stdin.readline

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

conn = [len(v) for v in adj]
min_ind = conn.index(1)


def dfs(cur, prev, dist):
    if len(adj[cur]) == 1 and prev in adj[cur]:
        return dist
    else:
        ret = 0
        for n in adj[cur]:
            if n == prev:
                continue
            else:
                ret = max(ret, dfs(n, cur, dist+1))
        return ret


D = dfs(min_ind, -1, 0)+1
if D % 3 == 0:
    print("First")
else:
    print("Second")

Submission status: Runtime Error

Solution code:
H,W,N=map(int,input().split())
Sr,Sc=map(int,input().split())
S=input()
T=input()

wr=Sc
wl=Sc
hu=Sr
hd=Sr


ans='YES'
for i in range(N):
    if S[i]=='R':
        wr+=1
    elif S[i]=='L':
        wl-=1
    elif S[i]=='U':
        hu-=1
    elif S[i]=='D':
        hd+=1
    if wr>W or wl<1 or hu<1 or hd>H:
        ans='NO'
        break

    if T[i]=='R':
        wl = min(W,wl+1)
    elif T[i]=='L':
        wr = max(1,wr-1)
    elif T[i]=='U':
        hd= max(1,hd-1)
    elif T[i]=='D':
        hu=min(H,hu+1)

print(ans)

Submission status: Runtime Error

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+1)
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: Runtime Error

Solution code:
# この問題はグラフの最大経路を各ターンに1or2減らし、自分のターンに0にした方が負けというゲームであると言える
# 先攻のターンの時点で最後に枝数が1つなら後攻が、2つか3つなら先攻が勝つ→最大経路を3で割った余りで場合分け
# 後攻は先行の手に関係なく１ターンの枝数の減少を3にできる→初期が3n+1なら後攻が必勝
# 先攻は常に3n or 3n+2を維持すれば勝てる、これは3nの時は1を3n+2の時は2を出していれば可能
# つまり最大経路が3n or 3n+2なら先行、3n+1なら後攻が勝つ

n = int(input())

dimensionDict = {}
edgeList = []
leafList = []
for i in range(n):
  dimensionDict[(i+1)] = 0
for i in range(n-1):
  edge0, edge1 = map(int, input().split())
  dimensionDict[edge0] += 1
  dimensionDict[edge1] += 1
  edgeList.append((edge0, edge1))
  
for k, v in dimensionDict.items():
  if v == 1:
    leafList.append(k)

for k in leafList:
  distanceDict[k] = 0
  for edge in edgeList:
    if edge[0] == k:
      distanceDict[edge[1]] =  distanceDict[k] + 1
    elif edge[0] == k:
      distanceDict[edge[0]] =  distanceDict[k] + 1
# 途中です

Submission status: Runtime Error

Solution code:
import random

def dfs(v,D):
    global Already,d_dist,Edge
    for child in D[v]:
        if child not in Already:
            d_dist[child] = d_dist[v] +1
            Already.append(child)
            dfs(child,D)
            Edge.append(d_dist[child])
    return Edge

if __name__ == "__main__":
    global Already,d_dist,Edge
    N = int(input())
    D = [[] for i in range(N)] #各頂点の字数
    for i in range(N-1):
        a,b = map(int,input().split())
        D[a-1].append(b-1)
        D[b-1].append(a-1)
    a_max = 0
    for i in range(N**2):
        d_dist = [0 for i in range(N)]
        Already = []
        Edge = []
        v = random.randint(0,N-1)
        edge = dfs(v,D)
        a = max(edge)
        if a_max < a:
            a_max = a
    if a_max!= 5 and a_max!= 2:
        State = "First"
    else:
        State = "Second"
    print(State)

Submission status: Runtime Error

Solution code:
n=int(input())
l=[0 for i in range(n)]
L=[list(map(int,input().split())) for i in range(n-1)]
ct=0
for i in range(n-1):
  l[L[i][0]-1]+=1
  l[L[i][1]-1]+=1
for i in range(n):
  if l[i]>=3:ct+=1
if ct%2=0:print('First')
else:print('Second')

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys

def dfs(idx, con, visited):
    visited[idx] = True
    max_depth = 0
    max_len = 0
    depths = []
    if idx >= len(con):
        return max_depth, max_len
    for v in con[idx]:
        if v < len(visited) and not visited[v]:
            max_d, max_l = dfs(v, con, visited)
            max_len = max(max_len, max_l)
            depths.append(max_d + 1)
    if len(depths) > 0:
        depths.sort(reverse=True)
        max_depth = depths[0]
        if len(depths) > 1:
            max_len = max(max_len, depths[0] + depths[1])
        else:
            max_len = max(max_len, depths[0])
    visited[idx] = False
    return max_depth, max_len


def solve(N: int, A: "List[int]", B: "List[int]"):
    con = [[] for _ in range(N)]
    for i in range(len(A)):
        a = A[i] - 1
        b = B[i] - 1
        con[a].append(b)
        con[b].append(a)
    #print(con)
    visited = [False] * N
    max_depth, max_len = dfs(0, con, visited)
    #print(max_len)
    if (max_len + 1) % 3 == 2:
        ret = 'Second'
    else:
        ret = 'First'
    print(ret)
    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()