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:
#!/usr/bin/env python3
# -*- coding:utf-8 -*-

from collections import defaultdict
import json
from copy import deepcopy

def dfs(graph, s, d, count=0, visited_nodes=None):
  if visited_nodes is None:
    visited_nodes = []
  visited_nodes.append(s)
  if len(graph[s]) == 1:
    d[s] = count
  for t in graph[s]:
    if t in visited_nodes:
      continue
    dfs(graph, t, d, count+1, visited_nodes)

if __name__=='__main__':
  graph = defaultdict(list)
  n, u, v = map(int, input().strip().split())
  for _ in range(n-1):
    ai, bi = map(int, input().strip().split())
    graph[ai].append(bi)
    graph[bi].append(ai)
  du, dv = dict(), dict()
  du[u], dv[v] = 0, 0
  dfs(graph, u, du)
  dfs(graph, v, dv)

  costv = []
  for k in dv.keys():
    if k in du and du[k] < dv[k]:
      costv.append(dv[k])
  print(max(costv) - 1)

Submission status: Runtime Error

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

from collections import defaultdict
import json
from copy import deepcopy

def dfs(graph, s, d, count=0):
  if len(graph[s]) == 0:
    # print(count)
    d[s] = count
  for t in graph[s]:
    if s in graph[t]:
      graph[t].remove(s)
    # print(s, t)
    dfs(graph, t, d, count+1)

if __name__=='__main__':
  graph = defaultdict(list)
  n, u, v = map(int, input().strip().split())
  for _ in range(n-1):
    ai, bi = map(int, input().strip().split())
    graph[ai].append(bi)
    graph[bi].append(ai)
  du, dv = dict(), dict()
  du[u], dv[v] = 0, 0
  dfs(deepcopy(graph), u, du)
  dfs(deepcopy(graph), v, dv)
  # print(json.dumps(du, indent=2))
  # print(json.dumps(dv, indent=2))

  costv = []
  for k in dv.keys():
    if k in du and du[k] < dv[k]:
      costv.append(dv[k])
  print(max(costv) - 1)

Submission status: Runtime Error

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

from collections import defaultdict
import json
from copy import deepcopy

def dfs(graph, s, d, count=0):
  if len(graph[s]) == 0:
    d[s] = count
  for t in graph[s]:
    if s in graph[t]:
      graph[t].remove(s)
    dfs(graph, t, d, count+1)

if __name__=='__main__':
  graph = defaultdict(list)
  n, u, v = map(int, input().strip().split())
  for _ in range(n-1):
    ai, bi = map(int, input().strip().split())
    graph[ai].append(bi)
    graph[bi].append(ai)
  du, dv = dict(), dict()
  du[u], dv[v] = 0, 0
  dfs(deepcopy(graph), u, du)
  dfs(deepcopy(graph), v, dv)

  costv = []
  for k in dv.keys():
    if du[k] < dv[k]:
      costv.append(dv[k])
  print(max(costv) - 1)

Submission status: Runtime Error

Solution code:
from collections import defaultdict


def find_distances(edge_dict, node, distances):
    for end in edge_dict[node]:
        if distances[end] < 0:
            distances[end] = distances[node] + 1
            distances = find_distances(edge_dict, end, distances)

    return distances


if __name__ == "__main__":
    V, T, A = map(int, input().split())
    T -= 1
    A -= 1
    edge_dict = defaultdict(list)

    for _ in range(V - 1):
        start, end = map(int, input().split())
        edge_dict[start - 1].append(end - 1)
        edge_dict[end - 1].append(start - 1)
    
    dist_T = [-1] * V
    dist_T[T] = 0
    dist_T = find_distances(edge_dict, T, dist_T)

    dist_A = [-1] * V
    dist_A[A] = 0
    dist_A = find_distances(edge_dict, A, dist_A)

    max_dist = 0
    for i in range(V):
        if dist_T[i] <= dist_A[i]:
            max_dist = max(max_dist, dist_A[i])
    
    print(max_dist - 1)

Submission status: Runtime Error

Solution code:
N, u, v = list(map(int, input().split()))
graph = [[] for _ in range(N+1)]
for i in range(N-1):
  A, B = list(map(int, input().split()))
  graph[A].append(B)
  graph[B].append(A)
#print(graph)

def dfs(v):
  dist = [-1] * (N+1)
  dist[v] = 0
  stack = [v
 # print(dist)
  while stack:
    now = stack.pop()
    dw = dist[now] + 1
#graph[]は隣接している要素
    for ne in graph[now]:
      if dist[ne] >= 0:
        continue
      dist[ne] = dw
      stack.append(ne)
      #print(ne)
  return dist

Taka = dfs(u)
#Ao = dfs(v)

print(Taka)
#print(Ao)

ans = 0
for t, a in zip(Takahashi[1:], Aoki[1:]):
  if t < a:
    ans = max(ans, a-1)

print(ans)

Submission status: Runtime Error

Solution code:
def search(tree, self, dist, d):
    dist[self] = d
    for num in tree[self]:
        if(dist[num] == -1 or dist[num] > d):
            search(tree, num, dist, d+1)

N, U, V = map(int, input().split())
tree = [[] for _ in range(N + 1)]

for _ in range(N - 1):
    A, B = map(int, input().split())
    tree[A].append(B)
    tree[B].append(A)

dist_a = [-1] * (N+1)
dist_b = [-1] * (N+1)

search(tree, U, dist_a, 0)
search(tree, V, dist_b, 0)

ans = 0

for i in range(1, N+1):
    if (dist_a[i] < dist_b[i]):
        ans = max(ans, dist_b[i])

print(ans - 1)

Submission status: Runtime Error

Solution code:
# nlognの実装。駄目。
import numpy as np
from scipy.sparse.csgraph import dijkstra


def calc(d):
    if d == 1 or d == 0:
        return 0
    else:
        return int(d - 1)


delta = []
n, u, v = map(int, input().split())
Gn = np.full((n, n), float("inf"))
for i in range(n - 1):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    Gn[a][b] = 1
    Gn[b][a] = 1
    Gn[i][i] = 0
minimum_u = dijkstra(Gn, indices=u - 1)
minimum_v = dijkstra(Gn, indices=v - 1)
for i in range(n):
    if minimum_v[i] - minimum_u[i] > 0 and i != u - 1 and i != v - 1:
        delta.append([i, minimum_v[i]])
if delta != []:
    delta_sorted = sorted(delta, key=lambda x: x[1])
    p = delta_sorted[-1][0]
    d = int(minimum_v[p])
    print(calc(d))
else:
    print(calc(minimum_u[v - 1]))

Submission status: Runtime Error

Solution code:
# nlognの実装。駄目。
import numpy as np
from scipy.sparse.csgraph import dijkstra

inf = 10 ** 9


def calc(d):
    if d == 1 or d == 0:
        return 0
    else:
        return int(d - 1)


delta = []
n, u, v = map(int, input().split())
Gn = np.full((n, n), inf)
for i in range(n - 1):
    a, b = map(int, input().split())
    a = a - 1
    b = b - 1
    Gn[a][b] = 1
    Gn[b][a] = 1
    Gn[i][i] = 0
minimum_u = dijkstra(Gn, indices=u - 1)
minimum_v = dijkstra(Gn, indices=v - 1)
for i in range(n):
    if minimum_v[i] - minimum_u[i] > 0 and i != u - 1 and i != v - 1:
        delta.append([i, minimum_v[i]])
if delta != []:
    delta_sorted = sorted(delta, key=lambda x: x[1])
    p = delta_sorted[-1][0]
    d = int(minimum_v[p])
    print(calc(d))
else:
    print(calc(minimum_u[v - 1]))

Submission status: Runtime Error

Solution code:
graph = [[] for i in range(N+1)]
for i,j in AB:
    graph[i].append(j)
    graph[j].append(i)
 
#深さ優先探索
def dfs(v):
    dist = [-1] * (N+1)
    stack = [v]
    dist[v] = 0
    while stack:
        v = stack.pop()
        dw = dist[v] + 1
        for w in graph[v]:
            if dist[w] >= 0:
                continue
            dist[w] = dw
            stack.append(w)
    return dist
 
DU,DV = dfs(u),dfs(v)
 
answer = 0
for u,v in zip(DU[1:],DV[1:]):
    if u < v:
        x = v - 1
        if answer < x:
            answer = x
 
print(answer)

Submission status: Runtime Error

Solution code:
from collections import defaultdict,deque
import sys,heapq,bisect,math,itertools,string,queue,copy,time
sys.setrecursionlimit(10**8)
INF = float('inf')
mod = 10**9+7
eps = 10**-7
def inp(): return int(sys.stdin.readline())
def inpl(): return list(map(int, sys.stdin.readline().split()))
def inpl_str(): return list(sys.stdin.readline().split())
 
N = inp()
 
if N%2 == 1:
    print(0)
else:
    ans = 0
    div = 10
    while div <= N:
        ans += N//div
        div *= 5
    print(ans)

Submission status: Runtime Error

Solution code:
n, u, v = int(input())
print(n, u, v)

Submission status: Runtime Error

Solution code:
N,u,v = map(int,input().split())
u -= 1
v -= 1

du = [0]*N
dv = [0]*N
du[u] = 0
dv[v] = 0
G = [[]]*N

def dfs(v, d, p, dis):
    dis[v] = d
    if G[v] != []:
        for u in G[v]:
            if( u == p):
                continue
            else:
                dfs( u, d+1, v, dis )

def calcDist(s, dist):
    dfs(s, 0, -1, dist)

for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == []:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == []:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if v in G[u]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    maxD = 0
    for idu,idv in zip(du,dv):
        if idu < idv:
            maxD = max(maxD, idv)       
    ans = maxD-1
    
print(ans)

Submission status: Runtime Error

Solution code:
N,u,v = map(int,input().split())
u -= 1
v -= 1

du = [0]*N
dv = [0]*N
du[u] = 0
dv[v] = 0
G = [[]]*N

def dfs(v, d, p, dis):
    dis[v] = d
    if G[v] != 0:
        for u in G[v]:
            if( u == p):
                continue
            else:
                dfs( u, d+1, v, dis )

def calcDist(s, dist):
    dfs(s, 0, -1, dist)

for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == []:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == []:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if G[u]==[v]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    maxD = 0
    for idu,idv in zip(du,dv):
        if idu < idv:
            maxD = max(maxD, idv)       
    ans = maxD-1
    
print(ans)

Submission status: Runtime Error

Solution code:
N,u,v = map(int,input().split())
u -= 1
v -= 1

du = [0]*N
dv = [0]*N
du[u] = 0
dv[v] = 0
G = [0]*N

def dfs(v, d, p, dis):
    dis[v] = d
    if G[v] != 0:
        for u in G[v]:
            if( u == p):
                continue
            else:
                dfs( u, d+1, v, dis )

def calcDist(s, dist):
    dfs(s, 0, -1, dist)

for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == 0:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == 0:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if G[u]==[v]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    maxD = 0
    for idu,idv in zip(du,dv):
        if idu < idv:
            maxD = max(maxD, idv)       
    ans = maxD-1
    
print(ans)

Submission status: Runtime Error

Solution code:
INF = 1000000
N,T,A=map(int,input().split())
T -= 1
A -= 1
G = [ [] for i in range(N) ]
DT = [ INF for _ in range(N) ]
DA = [ INF for _ in range(N) ]
for i in range(N-1):
    h1,h2=map(int,input().split())
    h1 -= 1
    h2 -= 1
    G[h1].append(h2);
    G[h2].append(h1);

def DFS_T( v, d ):
    for nv in G[v]:
        if DT[nv] != INF:
            continue
        DT[nv] = d + 1
        DFS_T(nv, d + 1)

def DFS_A( v, d ):
    for nv in G[v]:
        if DA[nv] != INF:
            continue
        DA[nv] = d + 1
        DFS_A(nv, d+1)

DT[T] = 0
DA[A] = 0
DFS_T(T,0)
DFS_A(A,0)
max_da = 0
for i in range(N):
    #print(i, " T:", DT[i], " A:", DA[i])
    if DA[i] - DT[i] >= 1 :
        max_da = max(DA[i]-1, max_da)
print(max_da)

Submission status: Runtime Error

Solution code:
N,u,v = map(int,input().split())
u -= 1
v -= 1

du = [0]*N
dv = [0]*N
du[u] = 0
dv[v] = 0
G = [0]*N

def dfs(v, d, p, dis):
    dis[v] = d
    for u in G[v]:
        if( u == p):
            continue
        else:
            dfs( u, d+1, v, dis )

def calcDist(s, dist):
    dfs(s, 0, -1, dist)

for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == 0:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == 0:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if G[u]==[v]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    maxD = 0
    for idu,idv in zip(du,dv):
        if idu < idv:
            maxD = max(maxD, idv)       
    ans = maxD-1
    
print(ans)

Submission status: Runtime Error

Solution code:
N,u,v = map(int,input().split())
u -= 1
v -= 1

du = [0]*N
dv = [0]*N
du[u] = 0
dv[v] = 0
G = [0]*N

def dfs(v, d, p, dis):
    dis[v] = d
    for u in G[v]:
        if( u == p):
            continue
        else:
            dfs( u, d+1, v, dis )

def calcDist(s, dist):
    dfs(s, 0, -1, dist)

for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == 0:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == 0:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if G[u]==[v]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    maxD = 0
    for idu,idv in zip(du,dv):
        if idu < idv:
            maxD = max(maxD, idv)       
  
print(maxD - 1)

Submission status: Runtime Error

Solution code:
N,u,v = map(int,input().split())
u -= 1
v -= 1

du = [0]*N
dv = [0]*N
du[u] = 0
dv[v] = 0
G = [0]*N

def dfs(v, d, p, dis):
    dis[v] = d
    for u in G[v]:
        if( u == p):
            continue
        else:
            dfs( u, d+1, v, dis )

def calcDist(s, dist):
    dfs(s, 0, -1, dist)

for i in range(N-1):
    e1,e2 = map(int, input().split())
    e1 -= 1
    e2 -= 1
    if G[e1] == 0:
        G[e1] = [e2]
    else:
        G[e1].append(e2)
    if G[e2] == 0:
        G[e2] = [e1]
    else:
        G[e2].append(e1)

if G[u]==[v]:
    ans = 0
else:    

    calcDist(v,dv)
    calcDist(u,du)
    for idu,idv in zip(du,dv):
        maxD = 0
        if idu < idv:
            maxD = max(maxD, idv)       
  
print(maxD - 1)

Submission status: Runtime Error

Solution code:
import sys, numpy as np, heapq
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import shortest_path, floyd_warshall, dijkstra, bellman_ford, johnson  
from collections import defaultdict
from itertools import product, permutations, combinations

sys.setrecursionlimit(10**7)
def input():
    return sys.stdin.readline()[:-1]

N, u, v = map(int, input().split())



def dijkstra_heap(s,edge):
#始点sから各頂点への最短距離
    d = [10**20] * N
    used = [True] * N #True:未確定
    d[s] = 0
    used[s] = False
    edgelist = []
    for a,b in edge[s]:
        heapq.heappush(edgelist,a*(10**6)+b)
    while len(edgelist):
        minedge = heapq.heappop(edgelist)
        #まだ使われてない頂点の中から最小の距離のものを探す
        if not used[minedge%(10**6)]:
            continue
        v = minedge%(10**6)
        d[v] = minedge//(10**6)
        used[v] = False
        for e in edge[v]:
            if used[e[1]]:
                heapq.heappush(edgelist,(e[0]+d[v])*(10**6)+e[1])
    return d

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

adjl = [[] for _ in range(N)]
for ab in AB:
    a, b = ab[0]-1, ab[1]-1
    adjl[a].append([1, b])
    adjl[b].append([1, a])

du = dijkstra_heap(u-1, adjl)
dv = dijkstra_heap(v-1, adjl)
dOK = [j for i, j in zip(du, dv) if i < j]

print(int(max(dOK)-1))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(10000000)
# input = sys.stdin.readline
# from bisect import *
# from collections import *
# from heapq import *
# import functools
# import itertools
# import math
INF = 500000
MOD = 10**9+7

def dfs(x, d):
    dep[x] = d
    for y in es[x]:
        if dep[y] == None:
            dfs(y, d+1)

def find(x):
    if dep[u] <= dep[x] and x != u:
        return -1
    if x == u:
        return x
    for y in es[x]:
        if dep[x] < dep[y]:
            tmp = find(y)
            if tmp != -1:
                tmp = x if dep[x] == l else tmp
                return tmp

def Maxd(x):
    ret = dep[x]
    for y in es[x]:
        if dep[x] < dep[y]:
            ret = max(ret, Maxd(y))
    return ret

N, u, v = map(int, input().split())
u -= 1
v -= 1
es = [[] for i in range(N)]
for i in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    es[a].append(b)
    es[b].append(a)
dep = [None] * N
dfs(v, 0)
l = u//2+1
k = find(v)
print(dep[u]-l+Maxd(k)-l+(dep[u]==2))

Submission status: Runtime Error

Solution code:
from typing import List
import sys

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

def dfs(v):
    dist = [-1] * (n+1)
    dist[v] = 0
    stack = [v]
    while stack:
        now = stack.pop()
        dw = dist[now] + 1
        for ne in graph[now]:
            if dist[ne] >= 0:
                continue
            dist[ne] = dw
            stack.append(ne)
    return dist

Takahashi = dfs(u)
Aoki = dfs(v)

ans = 0
for t, a in zip(Takahashi[1:], Aoki[1:]):
    if t < a:
        ans = max(ans, a - 1)

print(ans)

Submission status: Runtime Error

Solution code:
from typing import List
import sys

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

def dfs(v: int) -> List[int]:
    dist = [-1] * (n+1)
    dist[v] = 0
    stack = [v]
    while stack:
        now = stack.pop()
        dw = dist[now] + 1
        for ne in graph[now]:
            if dist[ne] >= 0:
                continue
            dist[ne] = dw
            stack.append(ne)
    return dist

Takahashi = dfs(u)
Aoki = dfs(v)

ans = 0
for t, a in zip(Takahashi[1:], Aoki[1:]):
    if t < a:
        ans = max(ans, a - 1)

print(ans)

Submission status: Runtime Error

Solution code:
from typing import List
import sys

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

def dfs(v: int) -> List[int]:
    dist = [-1] * (n+1)
    dist[v] = 0
    stack = [v]
    while stack:
        now = stack.pop()
        dw = dist[now] + 1
        for ne in graph[now]:
            if dist[ne] > 0:
                continue
            dist[ne] = dw
            stack.append(ne)
    return dist

Takahashi = dfs(u)
Aoki = dfs(v)

ans = 0
for t, a in zip(Takahashi, Aoki):
    if t < a:
        ans = max(ans, a - 1)

print(ans)

Submission status: Runtime Error

Solution code:
from typing import List

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

def dfs(v: int) -> List[int]:
    dist = [-1] * n+1
    dist[v] = 0
    stack = [v]
    while stack:
        now = stack.pop()
        dw = dist[now] + 1
        for ne in graph[now]:
            if dist[ne] > 0:
                continue
            dist[ne] = dw
            stack.append(ne)
    return dist

Takahashi = dfs(u)
Aoki = dfs(v)

ans = 0
for t, a in zip(Takahashi, Aoki):
    if t < a:
        ans = max(ans, a - 1)

print(ans)

Submission status: Runtime Error

Solution code:
from typing import List

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

def dfs(v: int) -> List[int]:
    dist = [-1] * n
    dist[v] = 0
    stack = [v]
    while stack:
        now = stack.pop()
        dw = dist[now] + 1
        for ne in graph[now]:
            if dist[ne] > 0:
                continue
            dist[ne] = dw
            stack.append(ne)
    return dist

Takahashi = dfs(u-1)
Aoki = dfs(v-1)

ans = 0
for t, a in zip(Takahashi, Aoki):
    if t < a:
        ans = max(ans, a - 1)

print(ans)

Submission status: Runtime Error

Solution code:
from typing import List

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

def dfs(v: int) -> List[int]:
    dist = [-1] * n
    dist[v] = 0
    stack = [v]
    while stack:
        now = stack.pop()
        dw = dist[now] + 1
        for ne in graph[now]:
            if dist[ne] < 0:
                continue
            dist[ne] = dw
            stack.append(ne)
    return dist

Takahashi = dfs(u-1)
Aoki = dfs(v-1)

ans = 0
for t, a in zip(Takahashi, Aoki):
    if t < a:
        ans = max(ans, a - 1)

print(ans)

Submission status: Runtime Error

Solution code:
INF = 1000000
N,T,A=map(int,input().split())
T -= 1
A -= 1
G = [ [] for i in range(N) ]
DT = [ INF for _ in range(N) ]
DA = [ INF for _ in range(N) ]
for i in range(N-1):
    h1,h2=map(int,input().split())
    h1 -= 1
    h2 -= 1
    G[h1].append(h2);
    G[h2].append(h1);

def DFS_T( v, d ):
    for nv in G[v]:
        if DT[nv] != INF:
            continue
        DT[nv] = d + 1
        DFS_T(nv, d + 1)

def DFS_A( v, d ):
    for nv in G[v]:
        if DA[nv] != INF:
            continue
        DA[nv] = d + 1
        DFS_A(nv, d+1)

DT[T] = 0
DA[A] = 0
DFS_T(T,0)
DFS_A(A,0)
max_da = 0
for i in range(N):
    #print(i, " T:", DT[i], " A:", DA[i])
    if DA[i] - DT[i] >= 1 :
        max_da = max(DA[i], max_da)
print(max_da-1)

Submission status: Runtime Error

Solution code:
import sys
input = sys.stdin.readline
 
# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)

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

def dfs(G, cr, seen, dist):
  seen[cr] = 1
  for i in range(G[cr]):
    if seen[i] == 0:
      dist[i] = dist[cr] + 1
      dfs(G, i, seen, dist)
  return dist

seen_u = [0]*n
seen_v = [0]*n
dist_u = [0]*n
dist_v = [0]*n

T1 = dfs(l, u, seen_u, dist_u)
T2 = dfs(l, v, seen_v, dist_v)

for i in range(n):
  if dist_u[i] >= dist_v[i]:
    dist_v[i] = -1
    
print(max(dist_v)-1)

Submission status: Runtime Error

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

# 再帰上限を引き上げる
sys.setrecursionlimit(10**6)




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

u,v = u-1,v-1

a = [[] for i in range(n)]

for i in range(n-1):
	# 配列indexは0開始だからinputは-1
	l,m = (int(x)-1 for x in input().split())
	a[l].append(m)
	a[m].append(l)

# v視点のdistを調べる
dist_u = [0]*n
dist_v = [0]*n

# G:graph, cr:current node, seen:is seen?, dist:out;each distance
def dfs_u(cr,seen):
	seen[cr] = 1
	for i in G[cr]: #G[cr]から行ける各頂点へ
		if seen[i] == 0: #まだ通っていなかったら
			dist_u[i] = dist_u[cr]+1
			dfs_u(i,seen)
# G:graph, cr:current node, seen:is seen?, dist:out;each distance
def dfs_v(cr,seen):
	seen[cr] = 1
	for i in G[cr]: #G[cr]から行ける各頂点へ
		if seen[i] == 0: #まだ通っていなかったら
			dist_v[i] = dist_v[cr]+1
			dfs_v(i,seen)

dfs_u(u,[0]*n)
# u視点のdistを調べる
dfs_v(v,[0]*n)

for i in range(n):
	if dist_u[i] >= dist_v[i]: # vが追いつける距離なら
		dist_u[i] = -1

print(dist_v[dist_u.index(max(dist_u))] - 1)

Submission status: Runtime Error

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

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

def DFS(s, dist, to, d = 0, p = -1):
    dist[s] = d
    for v in to[s]:
        if v == p:
            continue
        DFS(v, dist, to, d + 1, s)
    
def calcDict(s, dist, to):
    DFS(s, dist, to)
    
distU = [0] * (n + 1)
distV = [0] * (n + 1)

calcDist(u, distU, to)
calcDist(v, distV, to)
ans = 0
for i in range(n + 1):
    if dictU[i] < dictV[i]:
        ans = max(ans, dictV[i])
print(ans - 1)

Submission status: Runtime Error

Solution code:

import copy

def dfs(graph, v, d):
    seen[v] = True # 訪問済みかどうか
    dist[v] = d # 距離を記録

    # 頂点vから行ける頂点を全探索
    for i in graph[v]:
        if seen[i]:
            continue
        dfs(graph, i, d+1)

# ここから本文
N, u, v = map(int, input().split())

u -= 1
v -= 1

# グラフ構造を作る
graph = [[] for i 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)

# 青木くんからの各頂点の距離
seen = [False for i in range(N)]
dist = [0 for i in range(N)]
dfs(graph, v, 0)
aoki_dist = copy.deepcopy(dist)

# 高橋くんからの各頂点の距離
seen = [False for i in range(N)]
dist = [0 for i in range(N)]
dfs(graph, u, 0)
takahashi_dist = copy.deepcopy(dist)

ans = 0
for i in range(N):
    if aoki_dist[i] > takahashi_dist[i]:
        if aoki_dist[i] - 1 > ans:
            ans = aoki_dist[i] - 1      

print(ans)

Submission status: Runtime Error

Solution code:
def dfs(v, dist, d = 0, p = -1):
#     print(v, d)
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(u, dist, d + 1, v)
def calcDist(s, dist):
    dfs(s, dist)        
n, u, v = map(int, input().split())
u -= 1
v -= 1
to = [[] for _ in range(n + 1)]
for i in range(n - 1):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    to[a].append(b)
    to[b].append(a)
distS = [0] * n
distT = [0] * n
calcDist(u, distS)
calcDist(v, distT)
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())
A = [[] for _ in range(N)]
import sys
sys.setrecursionlimit(10**8)
for _ in range(N - 1):
    a, b = map(int, input().split())

    A[a - 1].append(b - 1)
    A[b - 1].append(a - 1)

C = [0] * N
D = [0] * N

def DFS(x, pre, cnt, C):
    C[x] = cnt
    cnt += 1
    for a in A[x]:
        if a == pre:
            continue

        DFS(a, x, cnt, C)


DFS(V - 1, -1, 0, C)
DFS(U - 1, -1, 0, D)
for i in range(N):
    if C[i]>D[i]:
        ans =max(ans, C[i]-1)
print(ans)

Submission status: Runtime Error

Solution code:
h,w=map(int,input().split())
l=[]
for i in range(h):
    l.append(list(input()))
p=[[0 for i in range(w)] for j in range(h)]
#q=[[0 for i in range(w)] for j in range(h)]
for i in range(h):
    f=0
    for j in range(w-1,-1,-1):
        if l[i][j]=='O':
            f+=1
        elif l[i][j]=='J':
            p[i][j]=f
a=0
for i in range(w):
    f=0
    for j in range(h-1,-1,-1):
        if l[j][i]=='I':
            f+=1
        elif l[j][i]=='J':
            a+=p[j][i]*f
print(a)

Submission status: Runtime Error

Solution code:
from collections import deque

n, s, t = map(int, input().split(' '))
s -= 1
t -= 1

v = [[] for i in range(n)]
f = [0]*n

for i in range(n-1):
    a, b = map(int, input().split(' '))
    a -= 1
    b -= 1
    v[a].append(b)
    v[b].append(a)
    f[a] += 1
    f[b] += 1
for i in range(n):
    if f[i] == 0:
        l.append(i)
depth = [-1]*n
depth[t] = 0
q = deque([t])
while q:
    x = q.popleft()
    for y in v[x]:
        if depth[y] < 0:
            depth[y] = depth[x]+1
            q.append(y)
l = depth[:]
d = [-1]*n
d[s] = 0
q = deque([s])
while q:
    x = popleft()
    for y in v[x]:
        if d[y] < 0:
            d[y] = d[x]+1
            q.append(y)
l = sorted(range(n), key=lambda x:-depth[x])
for i in l:
    if d[i] < depth[i]:
        break
print(depth[i] - 1)

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>
using namespace std;

#define int long long

vector<vector<int>>e(1e5);

vector<int>aoki(1e5,1e9), taka(1e5,0);

vector<bool>flag(1e5,false);



void aoki_bfs(int node,int cnt){
    aoki[node] = cnt;
    for(int i=0;i<e[node].size();i++){
        if(flag[e[node][i]]==false){
            flag[e[node][i]]=true;
            aoki_bfs(e[node][i],cnt+1);
        }
    }
}

void taka_bfs(int node,int cnt){
    taka[node] = cnt;
    for(int i=0;i<e[node].size();i++){
        if(flag[e[node][i]]==false){
            flag[e[node][i]]=true;
            taka_bfs(e[node][i],cnt+1);
        }
    }
}

signed main(void){
    int n,u,v; cin >> n >> u >> v;u--;v--;
    for(int i=0;i<n-1;i++){
        int a,b; cin >> a >> b; a--;b--;
        e[a].push_back(b);
        e[b].push_back(a);
    }

    // for(int i=0;i<n;i++){
    //     for(int j=0;j<e[i].size();j++){
    //         cout << e[i][j] << ' ';
    //     }cout << endl;
    // }


    for(int i=0;i<n;i++)flag[i] = false;
    flag[u]=true;
    taka_bfs(u,0);
    for(int i=0;i<n;i++)flag[i] = false;
    flag[v] = true;
    aoki_bfs(v,0);

    // cout << endl;
    // for(int i=0;i<n;i++){
    //     cout << aoki[i] << ' ' << taka[i] << endl;
    // }cout << endl;

    int ans = 0;
    for(int i=0;i<n;i++){
        if(taka[i]<aoki[i]){
            int tmp = aoki[i]-1;
            if(ans < tmp) ans = tmp;
        } 
    }
    cout << ans << endl;
    return 0;
}

Submission status: Runtime Error

Solution code:
def dfs(v, dist, d = 0, p = -1):
#     print(v, d)
    dist[v] = d
    for u in to[v]:
        if u == p:
            continue
        dfs(u, dist, d + 1, v)
def calcDist(s, dist):
    dfs(s, dist)        
n, u, v = map(int, input().split())
u -= 1
v -= 1
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)
distS = [0] * n
distT = [0] * n
calcDist(u, distS)
calcDist(v, distT)
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:
import sys
input = sys.stdin.readline

# G:graph, cr:current node, seen:is seen?, dist:out;each distance
def dfs(G,cr,seen,dist):
	seen[cr] = 1
	for i in G[cr]: #G[cr]から行ける各頂点へ
		if seen[i] == 0: #まだ通っていなかったら
			dist[i] = dist[cr]+1
			dfs(G,i,seen,dist)


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

u,v = u-1,v-1

a = [[] for i in range(n)]

for i in range(n-1):
	# 配列indexは0開始だからinputは-1
	l,m = ( int(x)-1 for x in input().split() )
	a[l].append(m)
	a[m].append(l)

# v視点のdistを調べる
dist_u = [0]*n
dfs(a,u,[0]*n,dist_u)
# u視点のdistを調べる
dist_v = [0]*n
dfs(a,v,[0]*n,dist_v)

for i in range(n):
	if dist_u[i] >= dist_v[i]: # vが追いつける距離なら
		dist_u[i] = -1

print(dist_v[dist_u.index(max(dist_u))] - 1)