Problem:


Score : 600 points

Problem Statement

We have a tree with N vertices. The i-th edge connects Vertex A_i and B_i bidirectionally.

Takahashi is standing at Vertex u, and Aoki is standing at Vertex v.

Now, they will play a game of tag as follows:

1. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Takahashi moves to a vertex of his choice that is adjacent to his current vertex.

2. If Takahashi and Aoki are standing at the same vertex, the game ends. Otherwise, Aoki moves to a vertex of his choice that is adjacent to his current vertex.

3. Go back to step 1.

Takahashi performs his moves so that the game ends as late as possible, while Aoki performs his moves so that the game ends as early as possible.

Find the number of moves Aoki will perform before the end of the game if both Takahashi and Aoki know each other's position and strategy.

It can be proved that the game is bound to end.

Constraints

2 \leq N \leq 10^5

1 \leq u,v \leq N

u \neq v

1 \leq A_i,B_i \leq N

The given graph is a tree.

Input

Input is given from Standard Input in the following format:

N u v
A_1 B_1
:
A_{N-1} B_{N-1}

Output

Print the number of moves Aoki will perform before the end of the game.

Sample Input 1

5 4 1
1 2
2 3
3 4
3 5

Sample Output 1

2

If both players play optimally, the game will progress as follows:

Takahashi moves to Vertex 3.

Aoki moves to Vertex 2.

Takahashi moves to Vertex 5.

Aoki moves to Vertex 3.

Takahashi moves to Vertex 3.

Here, Aoki performs two moves.

Note that, in each move, it is prohibited to stay at the current vertex.

Sample Input 2

5 4 5
1 2
1 3
1 4
1 5

Sample Output 2

1

Sample Input 3

2 1 2
1 2

Sample Output 3

0

Sample Input 4

9 6 1
1 2
2 3
3 4
4 5
5 6
4 7
7 8
8 9

Sample Output 4

5



Sample input:
5 4 1
1 2
2 3
3 4
3 5


Sample output:
2

Submission status: Runtime Error

Solution code:
import sys
from collections import deque
input = sys.stdin.readline
N, u, v = [int(x) for x in input().strip().split()]

m = [[] for n in range(N)]
f_aokikun = [False for n in range(N)]
f_takahashikun = [False for n in range(N)]
aokikun = [0 for n in range(N)]
takahashikun = [0 for n in range(N)]
takahashikun_enable = [1 for n in range(N)]
for n in range(N-1):
    a, b = [int(x) for x in input().strip().split()]
    m[a-1].append(b)
    m[b-1].append(a)

def aokifunc(c, f, p, cost):
    c[p-1] = cost
    f[p-1] = True
    for p_next in m[p-1]:
        if f[p_next-1]:
            continue
        aokifunc(c, f, p_next, cost+1)

def takahashifunc(c, f, p, cost, aokikun, takahashikun_enable):
    if aokikun[p-1] <= cost:
        takahashikun_enable[p-1] = 0
    c[p-1] = 0
    f[p-1] = True
    for p_next in m[p-1]:
        if f[p_next-1]:
            continue
        takahashifunc(c, f, p_next, cost+1, aokikun, takahashikun_enable)

aokifunc(aokikun, f_aokikun, v, 0)
takahashifunc(takahashikun, f_takahashikun, u, 0, aokikun, takahashikun_enable)
print(max([i * j for i, j in zip(aokikun, takahashikun_enable)])-1)

Submission status: Runtime Error

Solution code:
import numpy as np
N = int(input())
n = N % 2
if n == 1:
  ans = 0
else:
  AB = list(range(N, 1, -2))
  a = int(np.log(N) / np.log(5))
  ab = []
  for i in range(a):
    a5 = 5 ** (i + 1)
    for Ab in AB:
      if Ab % a5 == 0:
        ab.append(Ab)
  ans = len(ab)
print(ans)

Submission status: Runtime Error

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

def dfs(dist, v, d=0, p=-1):
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(dist, u, d+1, v)

def calcDist(s):
    dist = [0] * N
    dfs(dist, s)
    return dist

distS = calcDist(s)
distT = calcDist(t)

mx = 0
for i in range(N):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)

Submission status: Runtime Error

Solution code:
n,u,v = map(int, input().split())
adjacent_list = [[]for i in range(n+1)]
aoki = [-1 for i in range(n+1)]
takahashi = [-1 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)

def dfs(node, count,li):
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i, count + 1,li)

def search_path(node,t):
    if node == t:
        return
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            pre_node[i] = node
            search_path(i, t)

finished = set()
dfs(v,0,aoki)
finished = set()
path = []
pre_node = [0 for i in range(n+1)]
#最短炉を出す
search_path(u,v)
while v != u:
    path = [v] + path
    v = pre_node[v]
start = u
for i in range(len(path)-1):
    if aoki[path[i+1]] <= i+1:
        start = path[i]
        break
finished = set()
ans_path = [0 for i in range(n+1)]
dfs(start,0,ans_path)
ans = 0
for i in range(1,n+1):
    if aoki[i] > ans_path[i]:
        ans = max(ans, ans_path[i])
print(ans + aoki[start] - 1)

Submission status: Runtime Error

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

def dfs(dist, v, d=0, p=-1):
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(dist, u, d+1, v)

def calcDist(s):
    dist = [0] * N
    dfs(dist, s)
    return dist

distS = calcDist(s)
distT = calcDist(t)

mx = 0
for i in range(N):
    if distS[i] < distT[i]:
        mx = max(mx, distT[i])
ans = mx - 1
print(ans)

Submission status: Runtime Error

Solution code:
n,u,v = map(int, input().split())
adjacent_list = [[]for i in range(n+1)]
aoki = [-1 for i in range(n+1)]
takahashi = [-1 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)

def dfs(node, count,li):
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i, count + 1,li)

def search_path(node,t):
    if node == t:
        return
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            pre_node[i] = node
            search_path(i, t)

finished = set()
dfs(v,0,aoki)
finished = set()
path = []
pre_node = [0 for i in range(n+1)]
#最短炉を出す
search_path(u,v)
while v != u:
    path = [v] + path
    v = pre_node[v]
start = u
for i in range(len(path)-1):
    if aoki[path[i+1]] <= i+1:
        start = path[i]
        break
finished = set(path)
ans = [0 for i in range(n+1)]
dfs(start,0,ans)
print(max(ans) + aoki[start] - 1)

Submission status: Runtime Error

Solution code:
n, u, v = map(int, input().split())
edges = {}
for i in range(n-1):
  a, b = map(int, input().split())
  if a in edges.keys():
    edges[a].append(b)
  else:
    edges[a] = [b]
  if b in edges.keys():
    edges[b].append(a)
  else:
    edges[b] = [a]

tkhs = [-1 for i in range(n+1)]
def search1(node, t):
  global tkhs
  tkhs[node] = t
  t += 1
  for edge in edges[node]:
    if tkhs[edge] == -1:
      search1(edge, t)
aok = [-1 for i in range(n+1)]
def search2(node, t):
  global aok
  aok[node] = t
  t += 1
  for edge in edges[node]:
    if aok[edge] == -1:
      search2(edge, t)
search1(u, 0)
search2(v, 0)

ans = 0
for i in range(1, n+1):
  if tkhs[i] < aok[i] and tkhs[i] != -1:
    ans = max(ans, aok[i] - 1)
print(ans)

Submission status: Runtime Error

Solution code:
n,u,v = map(int, input().split())
adjacent_list = [[]for i in range(n+1)]
aoki = [-1 for i in range(n+1)]
takahashi = [-1 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
finished = set()

def dfs(node, count,li):
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i, count + 1,li)

def search_path(node,t):
    if node == t:
        return
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            pre_node[i] = node
            search_path(i, t)
finished = set()
dfs(v,0,aoki)
finished = set()
path = []
node = v
pre_node = [0 for i in range(n+1)]
search_path(u,v)
while node != u:
    path = [node] + path
    node = pre_node[node]
start = 0
for i in range(len(path)-1):
    if aoki[path[i+1]] <= i+1:
        start = path[i]
        break
finished = set(path)
ans = [0 for i in range(n+1)]
dfs(start,0,ans)
print(max(0, max(ans) + aoki[start] - 1))

Submission status: Runtime Error

Solution code:
n,u,v = map(int, input().split())
adjacent_list = [[]for i in range(n+1)]
aoki = [-1 for i in range(n+1)]
takahashi = [-1 for i in range(n+1)]
for i in range(n-1):
    a,b = map(int ,input().split())
    adjacent_list[a].append(b)
    adjacent_list[b].append(a)
finished = set()

def dfs(node, count,li):
    li[node] = count
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            dfs(i, count + 1,li)

def search_path(node,t):
    if node == t:
        return
    finished.add(node)
    for i in adjacent_list[node]:
        if i not in finished:
            pre_node[i] = node
            search_path(i, t)
finished = set()
dfs(v,0,aoki)
finished = set()
path = []
node = v
pre_node = [0 for i in range(n+1)]
search_path(u,v)
while node != u:
    path = [node] + path
    node = pre_node[node]
start = 0
for i in range(len(path)-1):
    if aoki[path[i+1]] <= i+1:
        start = path[i]
        break
finished = set(path)
ans = [0 for i in range(n+1)]
dfs(start,0,ans)
print(ans)
print(min(0, max(ans) + aoki[start] - 1))

Submission status: Runtime Error

Solution code:
n, u, v = map(int, input().split())
edges = {}
for i in range(n-1):
  a, b = map(int, input().split())
  if a in edges.keys():
    edges[a].append(b)
  else:
    edges[a] = [b]
  if b in edges.keys():
    edges[b].append(a)
  else:
    edges[b] = [a]

tkhs = [-1 for i in range(n+1)]
def search1(node, t):
  tkhs[node] = t
  t += 1
  for edge in edges[node]:
    if tkhs[edge] == -1:
      search1(edge, t)
aok = [-1 for i in range(n+1)]
def search2(node, t):
  aok[node] = t
  t += 1
  for edge in edges[node]:
    if aok[edge] == -1:
      search2(edge, t)
search1(u, 0)
search2(v, 0)

ans = 0
for i in range(1, n+1):
  if tkhs[i] < aok[i] and tkhs[i] != -1:
    ans = max(ans, aok[i] - 1)
print(ans)

Submission status: Runtime Error

Solution code:
n, u, v = map(int, input().split())
edges = {}
for i in range(n-1):
  a, b = map(int, input().split())
  if a in edges.keys():
    edges[a].append(b)
  else:
    edges[a] = [b]
  if b in edges.keys():
    edges[b].append(a)
  else:
    edges[b] = [a]

tkhs = [-1 for i in range(n+1)]
def search1(node, t):
  tkhs[node] = t
  t += 1
  for edge in edges[node]:
    if tkhs[edge] == -1 and edge != v:
      search1(edge, t)
    elif edge == v:
      tkhs[edge] = t
aok = [-1 for i in range(n+1)]
def search2(node, t):
  aok[node] = t
  t += 1
  for edge in edges[node]:
    if aok[edge] == -1:
      search2(edge, t)
search1(u, 0)
search2(v, 0)

ans = 0
for i in range(1, n+1):
  if tkhs[i] < aok[i] and tkhs[i] != -1:
    ans = max(ans, aok[i] - 1)
print(ans)

Submission status: Runtime Error

Solution code:
import sys
n, tak, aok = map(int, input().split())
sys.setrecursionlimit(10e5)
tak = tak - 1
aok = aok - 1
neighbors = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    neighbors[a].add(b)
    neighbors[b].add(a)
rurality = [n] * n
def paint(rurality, here, num, output=None):
    if rurality[here] >= num:
        rurality[here] = num
        if output is not None:
            output.add(num)
        for nei in neighbors[here]:
            paint(rurality, nei, num + 1)
paint(rurality, aok, 0)
takback = tak
for _ in range((rurality[tak] - 1) // 2):
    for nei in neighbors[takback]:
        if rurality[nei] < rurality[takback]:
            takback = nei
            break
output = set()
paint(rurality, takback, rurality[takback], output)
print(max(output))

Submission status: Runtime Error

Solution code:
import sys
n, tak, aok = map(int, input().split())
sys.setrecursionlimit(n)
tak = tak - 1
aok = aok - 1
neighbors = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    neighbors[a].add(b)
    neighbors[b].add(a)
rurality = [n] * n
def paint(rurality, here, num, output=None):
    if rurality[here] >= num:
        rurality[here] = num
        if output is not None:
            output.add(num)
        for nei in neighbors[here]:
            paint(rurality, nei, num + 1)
paint(rurality, aok, 0)
takback = tak
for _ in range((rurality[tak] - 1) // 2):
    for nei in neighbors[takback]:
        if rurality[nei] < rurality[takback]:
            takback = nei
            break
output = set()
paint(rurality, takback, rurality[takback], output)
print(max(output))

Submission status: Runtime Error

Solution code:
import sys
n, tak, aok = map(int, input().split())
sys.setrecursionlimit(n))
tak = tak - 1
aok = aok - 1
neighbors = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    neighbors[a].add(b)
    neighbors[b].add(a)
rurality = [n] * n
def paint(rurality, here, num, output=None):
    if rurality[here] >= num:
        rurality[here] = num
        if output is not None:
            output.add(num)
        for nei in neighbors[here]:
            paint(rurality, nei, num + 1)
paint(rurality, aok, 0)
takback = tak
for _ in range((rurality[tak] - 1) // 2):
    for nei in neighbors[takback]:
        if rurality[nei] < rurality[takback]:
            takback = nei
            break
output = set()
paint(rurality, takback, rurality[takback], output)
print(max(output))

Submission status: Runtime Error

Solution code:
import sys; readline = sys.stdin.readline
from collections import deque

N, U, V = map(int, readline().split())
AB = [list(map(int, readline().split())) for i in range(N - 1)]

A = [a - 1 for a, b in AB]
B = [b - 1 for a, b in AB]

U, V = U - 1, V - 1

conn = {}
for a, b in zip(A, B):
    if not a in conn:
        conn[a] = []
    conn[a].append(b)

    if not b in conn:
        conn[b] = []
    conn[b].append(a)

t = [0 for i in range(N)]

def dfsU(u, parent, depth):
    t[u] = depth

    for _u in conn[u]:
        if _u != parent:
            dfsU(_u, u, depth + 1)

dfsU(V, -1, 0)

maxv = 0
maxu = U
def dfsV(v, parent, depth):
    global maxv
    global maxu
    if depth < t[v]:
        if t[v] > maxv:
            maxv = t[v]
            maxu = depth
        for _v in conn[v]:
            if _v != parent:
                dfsV(_v, v, depth + 1)

dfsV(U, -1, 0)
if (maxv - maxu) % 2 == 1:
    print(maxv - 1)
else:
    print(maxv - 1)

Submission status: Runtime Error

Solution code:
#%%
import numpy as np
n,nige,oni = map(int,input().split())
aa = np.zeros((n,n),dtype=bool)
for i in range(n-1):
    a,b = map(int,input().split())
    aa[a-1][b-1] = 1
    aa[b-1][a-1] = 1
nigel = np.zeros(n,dtype=bool)
nigel[nige-1] = 1
onil = np.zeros(n,dtype=bool)
onil[oni-1] = 1
ans = 0
for i in range(n-1):
    nigel = np.any(aa[nigel] == True,axis = 0)
    if np.logical_and(onil,nigel).sum() == nigel.sum():
        print(ans)
        exit()
    ans += 1
    onil = np.any(aa[onil] == True,axis = 0)
    nigel = np.logical_and(nigel,~onil)
    if nigel.sum() == 0:
        print(ans)
        exit()

Submission status: Runtime Error

Solution code:
n,u,v=map(int,input().split())
E=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    E[a].append(b)
    E[b].append(a)
depth=[-1]*(n+1)
dis=[-1]*(n+1)
def dsf_1(p,d):
    depth[p]=d
    for c in E[p]:
        if depth[c]==-1:
            dsf_1(c,d+1)
dsf_1(v,0)
def dsf_2(p,d):
    dis[p]=d
    for c in E[p]:
        if dis[c]==-1:
            dsf_2(c,d+1)
dsf_2(u,0)
ans=0
for i in range(1,n+1):
    if len(E[i])==1 and i!=v:
        if dis[i]<depth[i]:
           ans=max(ans,depth[i]-1)
print(ans)

Submission status: Runtime Error

Solution code:
N, u, v = map(int,input().split())
edges=[list(map(int,input().split())) for i in range(N-1)]
root = [[] for i in range(N)]
ans = 100000000
for a,b in edges:
    root[a-1].append(b-1)
    root[b-1].append(a-1)
def chase_move(my_pos,opponent_pos):
    if opponent_pos in root[my_pos]:
        tmp = [opponent_pos]
        return tmp
    else:
        tmp = root[my_pos][:]
        return tmp

def escape_move(my_pos,opponent_pos):
    if opponent_pos in root[my_pos]:
        tmp = root[my_pos][:]
        tmp.remove(opponent_pos)
        tmp.append(opponent_pos)
        return tmp
    else:
        tmp = root[my_pos][:]
        return tmp
        
def main(takahashi_pos,aoki_pos,cnt,turn):
    global ans
    if takahashi_pos==aoki_pos:
        if cnt<ans:
            ans=cnt
            return
    if ans<=cnt:
        return
    if turn == 0:
        tmp = escape_move(takahashi_pos,aoki_pos)
        for i in tmp:
            main(i,aoki_pos,cnt,1)
    elif turn == 1:
        cnt+=1
        tmp = chase_move(aoki_pos,takahashi_pos)
        for i in tmp:
            main(takahashi_pos,i,cnt,0)
main(u-1,v-1,0,0)
print(ans)

Submission status: Runtime Error

Solution code:
#%%
import numpy as np
n,nige,oni = map(int,input().split())
aa = np.zeros((n,n),dtype=bool)
for i in range(n-1):
    a,b = map(int,input().split())
    aa[a-1][b-1] = 1
    aa[b-1][a-1] = 1
nigel = np.zeros(n,dtype=bool)
nigel[nige-1] = 1
onil = np.zeros(n,dtype=bool)
onil[oni-1] = 1
ans = 0
for i in range(n-1):
    nigel = np.any(aa[nigel] == True,axis = 0)
    if np.logical_and(onil,nigel).sum() == nigel.sum():
        print(ans)
        exit()
    ans += 1
    onil = np.any(aa[onil] == True,axis = 0)
    if np.logical_and(onil,nigel).sum() == nigel.sum():
        print(ans)
        exit()

Submission status: Runtime Error

Solution code:
n, u, v = map(int, input().split())
u, v = u - 1, v - 1
nodes = [[] for i in range(n)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    nodes[a].append(b)
    nodes[b].append(a)


def search(parent, node, depth):
    chokudai_depth = 0
    max_depth = depth
    if node == u:
        chokudai_depth = depth
    if len(nodes[node]) == 1 and parent != -1:
        return max_depth, chokudai_depth
    for child in nodes[node]:
        if child != parent:
            _max_depth, _chokudai_depth = search(node, child, depth + 1)
            max_depth = max(max_depth, _max_depth)
            chokudai_depth = max(chokudai_depth, _chokudai_depth)
    return max_depth, chokudai_depth


max_depth, chokudai_depth = search(-1, v, 0)
ans = max_depth - chokudai_depth
if chokudai_depth == 0:
    print(0)
else:
    ans += chokudai_depth - 1
    print(ans)

Submission status: Runtime Error

Solution code:
n,u,v=map(int,input().split())
E=[[] for _ in range(n+1)]
for _ in range(n-1):
    a,b=map(int,input().split())
    E[a].append(b)
    E[b].append(a)
depth=[-1]*(n+1)
dis=[-1]*(n+1)
def dsf_1(p,d):
    depth[p]=d
    for c in E[p]:
        if depth[c]==-1:
            dsf_1(c,d+1)
dsf_1(v,0)
def dsf_2(p,d):
    dis[p]=d
    for c in E[p]:
        if depth[c]==-1:
            dsf_2(c,d+1)
dsf_2(u,0)
ans=0
for i in range(1,n+1):
    if len(E[i])==1 and i!=v:
        if dis[i]<depth[i]:
           ans=max(ans,depth[i]-1)
print(ans)

Submission status: Runtime Error

Solution code:
import heapq;

n, u, v = [int(v) for v in input().split()]

vert = []

for i in range(n):
    vert.append([])

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

taka = u-1
aoki = v-1

if taka == aoki:
    return 0

q = [(0, aoki)]
aoki_dist = [-1] * n
aoki_dist[aoki] = 0

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if aoki_dist[l] >= 0:
            continue
        aoki_dist[i] = c
        q.append((c, l))
    index += 1

q = [(0, taka)]
max_dist = aoki_dist[taka]

index = 0
while index < len(q):
    c0, i = q[index]
    c = c0 + 1
    for l in vert[i]:
        if aoki_dist[l] < 0:
            continue
        if c >= aoki_dist[l]:
            continue
        if max_dist < aoki_dist[l]:
            max_dist = aoki_dist[l]
        aoki_dist[l] = -1
        q.append((c, l))
    index += 1

print(max_dist - 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def visit(to, visited, depth, dic):
    if to in visited:
        return
    visited.add(to)
    dic[to] = depth
    available_edge = edges[to]
    for e in available_edge:
        visit(e, visited, depth + 1, dic)


def walk(to, visited):
    if to in visited:
        return
    visited.add(to)
    if depths_runner[to] < depths_tracer[to]:
        valid.add(depths_tracer[to])
        available_edges = edges[to]
        for e in available_edges:
            walk(e, visited)


num_vertex, tracer, runner = map(int, input().split())

edges = defaultdict(set)
for _ in range(1, num_vertex):
    src, dest = map(int, input().split())
    edges[src].add(dest)
    edges[dest].add(src)

if runner in edges[tracer]:
    print(0)
    exit(0)

# print(edges)
depths_tracer = defaultdict(set)
visit(tracer, set(), 0, depths_tracer)
# print(depths_tracer)

depths_runner = defaultdict(set)
visit(runner, set(), 0, depths_runner)
# print(depths_runner)

valid = set()
walk(runner, set())
ans = max(valid)

if ans % 2 == 0:
    ans -= 1

print(ans)
exit(0)

Submission status: Runtime Error

Solution code:
N = int(input())

ans = 0

if N%2 == 0:
    for i in range(100000000000):
        if 10*(5**i)<=N:
            ans+=int(N/(10*(5**i)))
        else:
            break


print(int(ans))

Submission status: Runtime Error

Solution code:
# -*- coding: utf-8 -*-

N, ko, oni = map(int, input().split())
AB = [list(map(int, input().split())) for i in range(N-1)]

# 隣接リスト
v_edges = [[] for i in range(N+1)]

for a, b in AB:
    v_edges[a].append(b)
    v_edges[b].append(a)


oni_depth = [0]
v_depths = [-1] * (N+1)
v_onipath = [0] * (N+1)
def dfs(v_edges, v, parent, depth):
    v_depths[v] = depth

    for next_v in v_edges[v]:
        if next_v == parent:
            continue
        dfs(v_edges, v=next_v, parent=v, depth=depth+1)

    if v == oni:
        oni_depth[0] = depth
        v_onipath[v] = 1

    for c in v_edges[v]:
        if c == parent:
            continue
        v_onipath[v] += v_onipath[c]


dfs(v_edges, ko, -1, 0)  # 子, 逃げる人を根とする

#print(v_depths)
#print(v_onipath)
#print(oni_depth)

for i in range(1, N+1):
    if v_onipath[i]:
        if v_depths[i] >= (oni_depth[0] / 2):
            v_edges[i] = []


v_depths = [-1] * (N+1)
v_onipath = [0] * (N+1)
dfs(v_edges, ko, -1, 0)

print(max(v_depths))

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import deque, defaultdict
import heapq
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)
        pass

    def add_edge(self, from_, to_, weight=1):
        self.E[from_].append((to_, weight))
        self.E[to_].append((from_, weight))


INF = float("inf")


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

    ddhouse = [0]*N

    def dfs(f_, pre, dep):
        ddhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(v-1, -1, 0)

    ffhouse = [0]*N

    def dfs(f_, pre, dep):
        ffhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(u-1, -1, 0)
    m = 0
    for d, f in zip(ddhouse, ffhouse):
        if f >= d:
            continue
        else:
            m = max(d, m)
    print(max(m-1, 0))
    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
    u = int(next(tokens))  # type: int
    v = 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, u, v, A, B)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
from sys import setrecursionlimit
setrecursionlimit(10101)

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

depthu = [-1] * (N)
depthu[u] = 0
depthv = [-1] * (N)
depthv[v] = 0

def dfs_depth(p, depth):
    for q in table[p]:
        if depth[q] == -1:
            depth[q] = depth[p] + 1
            dfs_depth(q, depth)

dfs_depth(v, depthv)
dfs_depth(u, depthu)

p = [i for i in range(1, N-1) if depthu[i] >= depthv[i] + 2]
if p:
    print(max(depthu[i] + (depthu[i] - depthv[i]) // 2 for i in p))
else:
    print(depthv[u] // 2)

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,u,v = map(int,input().split(' '))
l = [None]*N
for i in range(N-1):
    l[i] = list(map(int, input().split()))

MAP = {}
for i in range(N):
    if l[i]==None:
        continue
    a,b = l[i]
    if a in MAP:
        MAP[a].append(b)
    else:
        MAP[a] = [b]
    if b in MAP:
        MAP[b].append(a)
    else:
        MAP[b] = [a]

#Tがたどり着くのにかかる手数
t_MAP = [0]*(N+1)
cost = 0

def t_dfs(n,c):
    t_MAP[n] = c
    c += 1
    if n in MAP:
        for j in MAP[n]:
            if t_MAP[j]==0 and j!=u:
                t_dfs(j,c)
t_dfs(u,cost)

a_visited = [False]*(N+1)
break_even = False
pre_tcost = 10**5
ANS = [0]
def a_dfs(n,c,pre_c):
    a_visited[n] = True
    t_cost = t_MAP[n]
    if t_cost>c:
        if t_cost>pre_c:
            return
    ANS[0] = max(c,ANS[0])
    c += 1
    if n in MAP:
        for j in MAP[n]:
            if not a_visited[j]:
                a_dfs(j,c,t_cost)
a_visited[v] = True
a_dfs(v,cost,pre_tcost)
print(ANS[0]-1)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys
import math
from collections import deque, defaultdict
import heapq
INF = float("inf")


class Graph(object):
    def __init__(self, N):
        self.N = N
        self.E = defaultdict(list)
        pass

    def add_edge(self, from_, to_, weight=1):
        self.E[from_].append((to_, weight))
        self.E[to_].append((from_, weight))


INF = float("inf")


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

    ddhouse = [0]*N

    def dfs(f_, pre, dep):
        ddhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(v-1, -1, 0)

    ffhouse = [0]*N

    def dfs(f_, pre, dep):
        ffhouse[f_] = dep

        for t_, w in g.E[f_]:
            if t_ == pre:
                continue
            dfs(t_, f_, dep+1)
        return

    dfs(u-1, -1, 0)
    m = 0
    for d, f in zip(ddhouse, ffhouse):
        if f >= d:
            continue
        else:
            m = max(d, m)
    print(max(m-1, 0))
    print(ddhouse, ffhouse)
    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
    u = int(next(tokens))  # type: int
    v = 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, u, v, A, B)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
def input():
    return sys.stdin.readline()[:-1]
N,u,v = map(int,input().split(' '))
l = [None]*N
for i in range(N-1):
    l[i] = list(map(int, input().split()))

MAP = {}
for i in range(N):
    if l[i]==None:
        continue
    a,b = l[i]
    if a in MAP:
        MAP[a].append(b)
    else:
        MAP[a] = [b]
    if b in MAP:
        MAP[b].append(a)
    else:
        MAP[b] = [a]

#Tがたどり着くのにかかる手数
t_MAP = [0]*(N+1)
cost = 0

def t_dfs(n,c):
    t_MAP[n] = c
    c += 1
    if n in MAP:
        for j in MAP[n]:
            if t_MAP[j]==0 and j!=u:
                t_dfs(j,c)
t_dfs(u,cost)

a_visited = [False]*(N+1)
break_even = False
pre_tcost = 10**5
ANS = [0]
def a_dfs(n,c,pre_c):
    a_visited[n] = True
    t_cost = t_MAP[n]
    if t_cost>c:
        if t_cost>pre_c:
            return
    ANS[0] = max(c,ANS[0])
    c += 1
    if n in MAP:
        for j in MAP[n]:
            if not a_visited[j]:
                a_dfs(j,c,t_cost-1)
a_visited[v] = True
a_dfs(v,cost,pre_tcost)
print(ANS[0]-1)

Submission status: Runtime Error

Solution code:
n, tak, aok = map(int, input().split())
tak = tak - 1
aok = aok - 1
neighbors = [set() for _ in range(n)]
for _ in range(n - 1):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    neighbors[a].add(b)
    neighbors[b].add(a)
rurality = [n] * n
def paint(rurality, here, num, output=None):
    if rurality[here] >= num:
        rurality[here] = num
        if output is not None:
            output.add(num)
        for nei in neighbors[here]:
            paint(rurality, nei, num + 1)
paint(rurality, aok, 0)
takback = tak
for _ in range(rurality[tak] // 2):
    for nei in neighbors[takback]:
        if rurality[nei] < rurality[takback]:
            takback = nei
            break
output = set()
paint(rurality, takback, rurality[takback], output)
print(max(output))

Submission status: Runtime Error

Solution code:
n,u,v = map(int,input().split())

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)

visit1 = [False]*n
visit2 = [False]*n

visit1[u-1] = True
visit2[v-1] = True

stack1 = [u-1]
stack2 = [v-1]

dis1 = [-1] * n
dis2 = [-1] * n
dis1[u-1] = 0
dis2[v-1] = 0

while stack1:
    for _ in range(len(stack1)):
        q1 = stack1.pop(-1)
        for i in edges[q1]:
            if not visit1[i] and not visit2[i]:
                visit1[i] = True
                dis1[i] = dis1[q1] + 1
                stack1.append(i)

    for _ in range(len(stack2)):
        q2 = stack2.pop(-1)
        for i in edges[q2]:
            if not visit2[i]:
                visit2[i] = True
                dis2[i] = dis2[q2] + 1
                stack2.append(i)

while stack2:
    q = stack2.pop(-1)
    for i in edges[q]:
        if not visit2[i]:
            visit2[i] = True
            dis2[i] = dis2[q] + 1
            stack2.append(i)

Ans = 0
for i in range(n):
    If dis1[i] != 0:
        Ans =max(Ans,dis2[i])
ans = Ans -1

print(ans)