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:
# this is a real good problem!
# need to worry more about Takahashi's move
# make use of the properties of TREE (not GRAPH)

# solving flow:
# 0. Session for input and setup
# 1. Find far points from the function 'taka'
#    -> getting possible far points with distances from current Aoki's position (BFS)
# 2. See if Takahashi can reach each far point without facing Aoki
#    -> go deep down to reach the far point
#    -> 2 possible outcomes: reachable / unreachable
# 3. Among the possible far points, choose the one with maximum distance
# 4. Thru BFS, choose where to go to get the point found in (3) as early as possible

import sys
si = sys.stdin.readline


def BFS(g, s, e):
    d = 1
    q = [s]
    visited = set()
    visited.add(s)
    if s == e:
        return 0

    while len(q) != 0:
        qs = len(q)
        for _ in range(qs):
            qpop = q[0]
            q = q[1:]
            for v in g[qpop]:
                if v == e:
                    return d
                if v not in visited:
                    q.append(v)
                    visited.add(v)
        d += 1

    return d


def DFS(g, taka, e, aoki, visited, af):
    visited.add(taka)
    if taka == aoki:
        af = 1
    if taka == e and af == 0:
        return 1
    for node in g[taka]:
        if node not in visited:
            if DFS(g, node, e, aoki, visited, af):
                return 1
    if taka == aoki and af == 1:
        af = 0
    return 0


def taka(g, s):
    visited = set()
    visited.add(s)
    q = [s]
    d = 0
    distanceTable = {}

    while len(q) != 0:
        d += 1
        # distanceTable[d] = []
        qs = len(q)
        for _ in range(qs):
            qpop = q[0]
            q = q[1:]
            if len(g[qpop]) == 1 and list(g[qpop])[0] in visited:
                # print("reached:")
                # print(qpop)
                distanceTable[qpop] = d-1
            else:
                for v in g[qpop]:
                    if v not in visited:
                        q.append(v)
                        visited.add(v)

    return distanceTable


def main():
    l = [int(e) for e in si().split()]
    n, u, v, ans, graph = l[0], l[1], l[2], 0, {}

    for _ in range(n-1):
        l = [int(e) for e in si().split()]
        if l[0] not in graph:
            graph[l[0]] = set()
        if l[1] not in graph:
            graph[l[1]] = set()
        graph[l[0]].add(l[1])
        graph[l[1]].add(l[0])

    while 1:
        taka_options = taka(graph, v)
        taka_options_copy = dict(taka_options)
        for node in taka_options.keys():
            if node == u:
                continue
            visited_dfs = set()
            aokiFlag = 0
            DFSresult = DFS(graph, u, node, v, visited_dfs, aokiFlag)
            # print(DFSresult)
            if not DFSresult:
                del taka_options_copy[node]

        # print(taka_options_copy)
        distance_to_takaGoal = max(taka_options_copy.values())
        for (key, value) in taka_options_copy.items():
            if value == distance_to_takaGoal:
                takaGoal = key
                break

        T_options = {}
        for node in graph[u]:
            T_options[node] = BFS(graph, node, takaGoal)

        minValue = min(T_options.values())
        # print('T_options:')
        # print(T_options)

        for (key, value) in T_options.items():
            if value == minValue:
                u = key
                # print('T is now at:')
                # print(u)
                break

        if u == v:
            print(ans)
            break

        ans += 1
        A_options = {}
        for node in graph[v]:
            A_options[node] = BFS(graph, node, u)

        minValue = min(A_options.values())
        # print('A_options:')
        # print(A_options)

        for (key, value) in A_options.items():
            if value == minValue:
                v = key
                # print('A is now at:')
                # print(v)
                break

        if u == v:
            print(ans)
            break


if __name__ == '__main__':
    main()

Submission status: Runtime Error

Solution code:
import sys
sys.recursionlimit(10**5)

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

du,dv=[0]*-~N,[0]*-~N
T=[list() for i in range(-~N)]

def dfs(p,t,v,d):
  d[v]=t
  for i in T[v]:
    if i!=p:
      dfs(v,t+1,i,d)

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

dfs(0,0,u,du)
dfs(0,0,v,dv)

c=0
for i in range(1,-~N):
  if len(T[i])==1 and i!=v:
    if du[i]<dv[i]:
      c=max(c,~-dv[i])

print(c)

Submission status: Runtime Error

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

du,dv=[0]*-~N,[0]*-~N
T=[list() for i in range(-~N)]

def dfs(p,t,v,d):
  d[v]=t
  for i in T[v]:
    if i!=p:
      dfs(v,t+1,i,d)

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

dfs(0,0,u,du)
dfs(0,0,v,dv)

c=0
for i in range(1,-~N):
  if len(T[i])==1 and i!=v:
    if du[i]<dv[i]:
      c=max(c,~-dv[i])

print(c)

Submission status: Runtime Error

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

du,dv=[0]*-~N,[0]*-~N
T=[list() for i in range(-~N)]

def dsf(p,t,v,d):
  d[v]=t
  for i in T[v]:
    if i!=p:
      dsf(v,t+1,i,d)

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

dsf(0,0,u,du)
dsf(0,0,v,dv)

if du[v]==1 and len(T[v])==1:
  print(0)
else:
  m=0
  for i in range(1,~-N):
    if du[i] < dv[i]:
      if m<du[i]:
        v,m=i,du[i]

  if m!=0:
    print(du[v]+m-1)
  else:
    m=N+1
    for i in range(1,~-N):
      if du[i]==dv[i]:
        m=min(m,du[i])
    print(m)

Submission status: Runtime Error

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

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

du,dv=[0]*-~N,[0]*-~N
T=[list() for i in range(-~N)]

def dsf(p,t,v,d):
  d[v]=t
  for i in T[v]:
    if i!=p:
      dsf(v,t+1,i,d)

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

dsf(0,0,u,du)
dsf(0,0,v,dv)

if du[v]==1 and len(T[v])==1:
  print(0)
else:
  m=0
  for i in range(1,~-N):
    if du[i] < dv[i]:
      if m<du[i]:
        v,m=i,du[i]

  if m!=0:
    print(du[v]+(m if m%2 else m-1))
  else:
    m=N+1
    for i in range(1,~-N):
      if du[i]==dv[i]:
        m=min(m,du[i])
    print(m)

Submission status: Runtime Error

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

du,dv=[0]*-~N,[0]*-~N
T=[list() for i in range(-~N)]

def dsf(p,t,v,d):
  d[v]=t
  for i in T[v]:
    if i!=p:
      dsf(v,t+1,i,d)

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

dsf(0,0,u,du)
dsf(0,0,v,dv)

if du[v]==1 and len(T[v])==1:
  print(0)
else:
  m=0
  for i in range(1,~-N):
    if du[i] < dv[i]:
      if m<du[i]:
        v,m=i,du[i]

  if m!=0:
    print(du[v]+(m if m%2 else m-1))
  else:
    m=N+1
    for i in range(1,~-N):
      if du[i]==dv[i]:
        m=min(m,du[i])
    print(m)

Submission status: Runtime Error

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

def calc_dist(dlist, n, dist, nnode):
  for c in tree[n]:
    if c == nnode:
      continue
    dlist[c] = dist
    calc_dist(dlist, c, dist+1, n)
    
u_dist_list = [0] * N
calc_dist(u_dist_list, u-1, 1, -1)
#print(u_dist_list)

v_dist_list = [0] * N
calc_dist(v_dist_list, v-1, 1, -1)
#print(v_dist_list)

ans = 0
for i in range(N):
  if (v_dist_list[i] - u_dist_list[i]) > 0 and v_dist_list[i] > ans:
    ans = v_dist_list[i] - 1
    
print(ans)

Submission status: Runtime Error

Solution code:
from collections import defaultdict, Counter, namedtuple, deque
import itertools
import functools
import bisect
import heapq
import math
from typing import NamedTuple
from fractions import gcd

NN = 202020
MOD = 10**9+7
INF = float("inf")

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

def bfs(start, player):
    que = deque([(start, -1, 0)])
    while que:
        node, par, dst = que.popleft()
        # print(node, par, dst)
        if len(graph[node]) == 1:
            # print(player, node)
            dst_dict[player][node] = dst

        for nxt in graph[node]:
            if nxt == par:
                continue
            que.append((nxt, node, dst+1))


dst_dict = [{}, {}]
bfs(u, 0)
bfs(v, 1)
# print(dst_dict[0], dst_dict[1])

max_time = 0
for k in dst_dict[0]:
    if dst_dict[0][k] < dst_dict[1][k]:
        max_time = max(max_time, dst_dict[1][k]-1)

print(max_time)

Submission status: Runtime Error

Solution code:
from sys import exit

N, u, v = map(int, input().split())
u -= 1
v -= 1
tree = [[] for _ in range(N)]
inf = 10 ** 5 + 1

for _ in range(N-1):
    a, b = map(lambda x: int(x)-1, input().split())
    tree[a].append(b)
    tree[b].append(a)
if len(tree[u]) == 1 and tree[u][0] == v:
    print(0)
    exit()
amemo = [inf] * N
tmemo = [inf] * N
def dfs_a(i, c):
    if amemo[i] != inf:
        return
    amemo[i] = c
    for j in tree[i]:
        dfs_a(j, c+1)
def dfs_t(i, c):
    if tmemo[i] != inf:
        return
    tmemo[i] = c
    for j in tree[i]:
        dfs_t(j, c+1)
dfs_a(v, 0)
dfs_t(u, 0)
ans = 0
for t, a in zip(tmemo, amemo):
    if t < a:
        ans = max(ans, a)

print(ans-1)

Submission status: Runtime Error

Solution code:
N, u, v = map(int, input().split())
u -= 1
v -= 1
tree = [[] for _ in range(N)]
inf = 10 ** 5 + 1

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

amemo = [inf] * N
tmemo = [inf] * N
def dfs_a(i, c):
    if amemo[i] != inf:
        return
    amemo[i] = c
    for j in tree[i]:
        dfs_a(j, c+1)
def dfs_t(i, c):
    if tmemo[i] != inf:
        return
    tmemo[i] = c
    for j in tree[i]:
        dfs_t(j, c+1)
dfs_a(v, 0)
dfs_t(u, 0)
ans = 0
for t, a in zip(tmemo, amemo):
    if t < a:
        ans = max(ans, a)

print(ans-1)

Submission status: Runtime Error

Solution code:
def get_distance(v):              
    distance = [0] * n
    visited = [0] * n
    visited[v] = 1
    dfs(v, 0, distance, visited)
    return distance


def dfs(v, d, distance, visited):
    distance[v] = d
    for u in adj[v]:
        if not visited[u]:
            visited[u] = 1
            dfs(u, d + 1, distance, visited)


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

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

u_distance = get_distance(u - 1)
v_distance = get_distance(v - 1)

ans = 0
for u, v in zip(u_distance, v_distance):
    if u < v and v - 1 > ans:
        ans = v - 1

print(ans)

Submission status: Runtime Error

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

def solve():
  n,u,v = (int(i) for i in input().split())
  u,v = u-1,v-1
  query = [[] for _ in range(n)]
  for i in range(n-1):
    a,b = (int(i)-1 for i in input().split())
    query[a].append(b)
    query[b].append(a)
  que = deque([])
  que.append((v,str(v)))

  while que:
    #print(que)
    place,move = que.popleft()
    for i in query[place]:
      if not str(i) in move:
        que.append((i,move+str(i)))
    if len(que) == 0:
      aokiroot = move
  takahashigoal = aokiroot[-1]
  #print(takahashigoal)
  que.append((u,str(u)))
  while que:
    place,move = que.popleft()
    if str(place) == takahashigoal:
      takahashiroot = move
    else:
      for i in query[place]:
        if not str(i) in move:
          que.append((i,move+str(i)))
  ans = 0
  for i in range(min(len(takahashiroot),len(aokiroot))):
    if  takahashiroot[i]  == aokiroot[i]:
      break
    else:
      ans += 1
      try:
        if takahashiroot[i+1]  == aokiroot[i]:
          ans -=1
          break
      except:
        ans -= 1
        break      

  print(max(0,ans))

solve()

Submission status: Runtime Error

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

def solve():
  n,u,v = (int(i) for i in input().split())
  u,v = u-1,v-1
  query = [[] for _ in range(n)]
  for i in range(n-1):
    a,b = (int(i)-1 for i in input().split())
    query[a].append(b)
    query[b].append(a)
  que = deque([])
  que.append((v,str(v)))

  while que:
    #print(que)
    place,move = que.popleft()
    for i in query[place]:
      if not str(i) in move:
        que.append((i,move+str(i)))
    if len(que) == 0:
      aokiroot = move
  takahashigoal = aokiroot[-1]
  #print(takahashigoal)
  que.append((u,str(u)))
  while que:
    place,move = que.popleft()
    if str(place) == takahashigoal:
      takahashiroot = move
    else:
      for i in query[place]:
        if not str(i) in move:
          que.append((i,move+str(i)))
  ans = 0
  for i in range(min(len(takahashiroot),len(aokiroot))):
    ans += 1
    if  takahashiroot  == aokiroot:
      break

     
  print(max(0,ans-1))

solve()

Submission status: Runtime Error

Solution code:
#include<bits/stdc++.h>

int n, u, v, tdis[100010], adis[100010];
std::vector<int> links[100010], used(1e5, 0);

void dfs(int s, int depth, int dis[]){
        used[s] = 1;
        dis[s] = depth;
        for(int a: links[s]){
                if(!used[a]) dfs(a, depth+1, dis);
        }
        return;
}



int main(){
        scanf("%d %d %d", &n, &u, &v);
        u--; v--;

        for(int i=0; i<n-1; i++){
                int a, b;
                scanf("%d %d", &a, &b);
                links[a-1].push_back(b-1);
                links[b-1].push_back(a-1);
        }


        dfs(u, 0, tdis);
        std::fill(used.begin(), used.end(), 0);
        dfs(v, 0, adis);

        int ans = 0;
        for(int i=0; i<n; i++){
                if(tdis[i]<adis[i]) ans = std::max(ans, adis[i]-1);
        }
        printf("%d\n", ans);
        return 0;
}

Submission status: Runtime Error

Solution code:
n, u, v = map(int, input().split())
edge = [tuple(map(int, input().split())) for _ in range(n-1)]
u -= 1
v -= 1

connect = [set() for _ in range(n)]
for a, b in edge:
    connect[a-1].add(b-1)
    connect[b-1].add(a-1)

du = [0] * n
dv = [0] * n

def dfs(v, dis, ng, d):
    d[v] = dis
    ng.add(v)
    for w in connect[v]:
        if w not in ng:
            dfs(w, dis+1, ng, d)

dfs(u, 0, set(), du)
dfs(v, 0, set(), dv)

print(du)
print(dv)
ans = 0
for i in range(n):
    if du[i] < du[i]:
        ans = max(ans, du[v]-1)
print(ans)

Submission status: Runtime Error

Solution code:
from copy import deepcopy
N, u, v = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(N-1):
    a, b = map(int, input().split())
    a, b = a-1, b-1
    edge[a].append(b)
    edge[b].append(a)

aoki = [0] * N
takahasi = [0] * N
dist_list = [0] * N
def dfs(pv, v, dist):
    dist_list[v] = dist
    for nv in edge[v]:
        if nv == pv:
            continue
        dfs(v, nv, dist+1)

dfs(-1,u-1,0)
takahasi = deepcopy(dist_list)
dist_list = [0] * N
dfs(-1,v-1,0)
aoki = deepcopy(dist_list)
print(takahasi)
print(aoki)

Submission status: Runtime Error

Solution code:
#!/usr/bin/env python3
import sys, math, itertools, collections, bisect
input = lambda: sys.stdin.buffer.readline().rstrip().decode('utf-8')
inf = float('inf') ;mod = 10**9+7
mans = inf ;ans = 0 ;count = 0 ;pro = 1

n,U,V = map(int,input().split())
U-=1;V-=1
G = [[] for i in range(n)]
for i in range(n-1):
  a,b = map(int,input().split())
  a-=1;b-=1
  G[a].append(b)
  G[b].append(a)
Aokidis = [0]*n
Takahashidis = [0]*n
def dfs(node,dis,TorA,pre):
  if TorA == "Takahashi":Takahashidis[node] = dis
  else:Aokidis[node] = dis
  for vi in G[node]:
    if vi == pre:continue
    dfs(vi,dis+1,TorA,node)
dfs(U,0,"Takahashi",-1)
dfs(V,0,"",-1)
for i in range(n):
  if Takahashidis[i] <= Aokidis[i]:
    ans = max(ans,Aokidis[i]-1)
print(ans)

Submission status: Runtime Error

Solution code:
N,u,v = map(int,input().split())
E = [[] for _ in range(N + 1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)
#print(E)
def bfs(start,N):
    d = [-1]*(N+1)
    d[start] = 0
    q = [start]
    while q:
        #print(d,q)
        v = q.pop()
        cnt = d[v]+1
        for i in E[v]:
            if(d[i] == -1):
                q.append(i)
                d[i] = cnt
    return d
taka = bfs(u,N)
aoki = bfs(v,N)
#print(taka,aoki)
for i in range(N+1):
    if(taka[i] < aoki[i]):
        fin = max(fin,aoki[i])
print(fin - 1)

Submission status: Runtime Error

Solution code:
from collections import deque
N,u,v = map(int,input().split())
E = [[] for _ in range(N + 1)]
for i in range(N-1):
    a,b = map(int,input().split())
    E[a].append(b)
    E[b].append(a)
print(E)
def bfs(start,N,AB):
    d = [-1]*(N+1)
    d[start] = 0
    q = [start]
    while q:
        print(d,q)
        v = q.pop()
        cnt = d[v]+1
        for i in E[v]:
            if(d[i] == -1):
                q.append(i)
                d[i] = cnt
    return d
taka = bfs(u,N,AB)#takahashi
aoki = bfs(v,N,AB)
print(taka,aoki)
fin = -1
for i in range(N+1):
    if(taka[i] < aoki[i]):
        fin = max(fin,aoki[i])
        ans = fin - (aoki[i]-taka[i]+1)//2
print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(1000000)

I=list(map(int,Input.split()))
n=I.pop(0)
u=I.pop(0)
v=I.pop(0)
Graph=[]
for i in range(n):
    Graph.append([])
for i in range(n-1): #隣接頂点の登録
    a=I.pop(0)
    b=I.pop(0)
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)

def dfs(s,b=-1): #深さ優先探索(グラフ,スタート,深さ)
    for i in Graph[s]: #隣接点に対して
        if i!=b: #前の点と一緒じゃないとき
            depth[i]=depth[s]+1
            dfs(i,s) #深さを増やし、スタートを更新して再探索

depth=[0]*n
dfs(u-1)
dT=depth

depth=[0]*n
dfs(v-1)
dA=depth

print(max(dT),max(dA))

dArrest=0
for i in range(n):
    if dA[i]>dT[i]: #Tが先に着ける点のうち
        dArrest=max(dArrest,dA[i]) #一番Aから遠い点
print(dArrest-1)

Submission status: Runtime Error

Solution code:
n,u,v=(map(int,input().split()))
Graph=[]
for i in range(n):
    Graph.append([])
for i in range(n-1): #隣接頂点の登録
    a,b=map(int,input().split())
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)

def dfs(G,s,d): #深さ優先探索(グラフ,スタート,深さ)
    mark[s]=1 #訪問済みを0から1にする
    depth[s]=d #今の深さを記録
    for i in Graph[s]: #隣接点に対して
        if mark[i]==0: #未訪問なら
            dfs(G,i,d+1) #深さを増やし、スタートを更新して再探索

depth=[0]*n
mark=[0]*n
for i in range(n):
    dfs(Graph,u-1,0)
dT=depth

depth=[0]*n
mark=[0]*n
for i in range(n):
    dfs(Graph,v-1,0)
dA=depth

dArrest=0
for i in range(n):
    if dA[i]>dT[i]>=dArrest: #Tが先に着ける点のうち
        dArrest=dA[i] #一番Aから遠い点
print(dArrest-1)

Submission status: Runtime Error

Solution code:
n,u,v=(map(int,input().split()))
Graph=[]
for i in range(n):
    Graph.append([])
for i in range(n-1): #隣接頂点の登録
    a,b=map(int,input().split())
    Graph[a-1].append(b-1)
    Graph[b-1].append(a-1)

def dfs(G,s,d): #深さ優先探索(グラフ,スタート,深さ)
    mark[s]=1 #訪問済みを0から1にする
    depth[s]=d #今の深さを記録
    for i in Graph[s]: #隣接点に対して
        if mark[i]==0: #未訪問なら
            dfs(G,i,d+1) #深さを増やし、スタートを更新して再探索

depth=[0]*n
mark=[0]*n
for i in range(n):
    dfs(Graph,u-1,0)
dT=depth

depth=[0]*n
mark=[0]*n
for i in range(n):
    dfs(Graph,v-1,0)
dA=depth

print(dT,dA)

dArrest=0
for i in range(n):
    if dA[i]>dT[i]>=dArrest: #Tが先に着ける点のうち        arrest=i
        dArrest=dA[i] #一番Aから遠い点
print(dArrest-1)

Submission status: Runtime Error

Solution code:
from collections import deque
n, u, v = map(int, input().split())
u-=1; v-=1;
a = []; b = [];
dist = [[] for i in range(n)]
for i in range(n-1):
    a, b = map(int, input().split())
    a -= 1; b -= 1
    dist[a].append(b)
    dist[b].append(a)

def bfs(u):
    d = [-1]*n
    stack = deque([u])
    d[u] = 0
    while len(stack)!=0:
        s = stack.popleft()
        for t in dist[s]:
            if d[t]==-1:
                d[t] = d[s]+1
                stack.append(t)
    return d

A = bfs(v)
T = bfs(u)
ans=0
for i in range(n):
    if A[i]>d[i]:
        ans = max(A[i]-1, ans)
print(ans)

Submission status: Runtime Error

Solution code:
from collections import *
import copy
N,v,u=map(int,input().split())
AB=[list(map(int,input().split())) for i in range(N-1)]
data=[[] for i in range(N+1)]
for A,B in AB:
    data[A].append(B)
    data[B].append(A)

stack=deque([[v,0]])
visited=set([v])
while stack:
    a,m=stack.popleft()
    for p in data[a]:
        if p==u:
            K=m+1
        if not p in visited:
            visited.add(p)
            stack.append([p,m+1])


for i in range(len(data)):
    if len(data[i])>1:
        visited=set([i])
        stack=deque([i])
        End=set()
        break
while stack:
    a=stack.popleft()
    flag=0
    for p in data[a]:
        if not p in visited:
            visited.add(p)
            stack.append(p)
            flag=1
    if flag==0:
        End.add(a)

Uvisited=set([u])
Vvisited=set([])
if not v in End:
    Vvisited.add(v)
Ustack=deque([[u,0]])
Vstack=deque([[v,0]])
ans=[]
M=1

while Ustack:
    while Vstack:
        a,m=Vstack.popleft()
        if m==M:
            Vstack.append([a,m])
            break
        for p in data[a]:
            if not p in End:
                if p in Uvisited:
                    pass
                    #ans.append(m)
                elif not p in Vvisited:
                    Vvisited.add(p)
                    Vstack.append([p,m+1])
    while Ustack:
        a,m=Ustack.popleft()
        if m==M:

            Ustack.append([a,m])
            break
        for p in data[a]:

            if not p in Uvisited:
                if p in Vvisited:
                    ans.append(m+1)
                Uvisited.add(p)
                Ustack.append([p,m+1])
    M+=1
print(max(ans))

Submission status: Runtime Error

Solution code:
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(int, input().split())
    es[a-1].append(b-1)
    es[b-1].append(a-1)

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

def calc_dist(x):
    dist = [-1] * n
    dfs(x, dist)
    return dist

dist_t = calc_dist(u)
dist_a = calc_dist(v)

mx = 0
for i in range(n):
    if dist_t[i] < dist_a[i]:
        mx = max(mx, dist_a[i])

ans = mx - 1
print(ans)

Submission status: Runtime Error

Solution code:
from _collections import deque
from _ast import Num


def parser():
    while 1:
        data = list(input().split(' '))
        for number in data:
            if len(number) > 0:
                yield (number)


input_parser = parser()


def gw():
    global input_parser
    return next(input_parser)


def gi():
    data = gw()
    return int(data)


MOD = int(1e9 + 7)

import numpy
from collections import deque
from math import sqrt
from math import floor
import heapq
#https://atcoder.jp/contests/abc148/tasks/abc148_f
#F - Playing Tag on Tree
"""
"""
N = gi()
u = gi()
v = gi()
t = [[] for i in range(N + 1)]
d = [[0 for i in range(2)] for j in range(N + 1)]

for _ in range(1, N):
    a = gi()
    b = gi()
    t[a].append(b)
    t[b].append(a)

ls = []


def dfs(i, p, di):

    if len(t[i]) == 1:
        ls.append(i)
    for nei in t[i]:
        if nei == p:
            continue
        d[nei][di] = d[i][di] + 1
        dfs(nei, i, di)


d[u][0] = 0
dfs(u, -1, 0)
d[v][1] = 0
dfs(v, -1, 1)

ans = 0
for l in ls:
    du = d[l][0]
    dv = d[l][1]
    if dv >= du:
        ans = max(ans, dv - 1)

print(ans)

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(200000)

def dfs(array, current, count):
  array[current - 1] = count
  for neighbour in graph[current]:
    if array[neighbour - 1] == -1:
      array = dfs(array, neighbour, count + 1)
  else:
    return array

T = [-1 for x in range(100000)]
A = [-1 for x in range(100000)]

graph = {}

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

for i in range(N-1):
  a,b = map(int,input().split())
  try:
    graph[a].append(b)
  except KeyError:
    graph[a] = [b]

  try:
    graph[b].append(a)
  except KeyError:
    graph[b] = [a]

T = dfs(T, u, 0)
A = dfs(A, v, 0)

ans = -1
for i in range(N):
  if T[i] < A[i]:
    ans = max(ans, A[ImportError] - 1)
print(max(0,ans))

Submission status: Runtime Error

Solution code:
import sys
sys.setrecursionlimit(110000)

def dfs(array, current, count):
  array[current - 1] = count
  for neighbour in graph[current]:
    if array[neighbour - 1] == -1:
      array = dfs(array, neighbour, count + 1)
  else:
    return array

T = [-1 for x in range(100000)]
A = [-1 for x in range(100000)]

graph = {}

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

for i in range(N-1):
  a,b = map(int,input().split())
  try:
    graph[a].append(b)
  except KeyError:
    graph[a] = [b]

  try:
    graph[b].append(a)
  except KeyError:
    graph[b] = [a]

T = dfs(T, u, 0)
A = dfs(A, v, 0)

ans = -1
for i in range(N):
  if T[i+1] < A[i+1]:
    ans = max(ans, A[i+1] - 1)
print(max(0,ans))

Submission status: Runtime Error

Solution code:
n, u, v = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]
u -= 1
v -= 1

e = [[] for _ in range(n)]
for a, b in ab:
    e[a].append(b)
    e[b].append(a)

if len(e[u]) == 1:
    if e[u][0] == v:
        print(0)
        exit()

t = [0] * n
a = [0] * n

def dfs(x, p, d, c):
    if len(e[x]) == 1:
        if e[x][0] == p:
            return
    for y in e[x]:
        if y == p:
            continue
        if c == 0:
            t[y] = d
        else:
            a[y] = d
        dfs(y, x, d+1, c)

dfs(u, -1, 1, 0)
dfs(v, -1, 1, 1)
ans = 0
for i in range(n):
    if t[i] < a[i]:
        ans = max(a[i], ans)

print(ans-1)

Submission status: Runtime Error

Solution code:
n, u, v = map(int, input().split())
ab = [tuple(map(lambda x:int(x)-1, input().split())) for _ in range(n-1)]
u -= 1
v -= 1

e = [[] for _ in range(n)]
for a, b in ab:
    e[a].append(b)
    e[b].append(a)

t = [0] * n
a = [0] * n

def dfs(x, p, d, c):
    if len(e[x]) == 1:
        if e[x][0] == p:
            return
    for y in e[x]:
        if y == p:
            continue
        if c == 0:
            t[y] = d
        else:
            a[y] = d
        dfs(y, x, d+1, c)

dfs(u, -1, 1, 0)
dfs(v, -1, 1, 1)
ans = 0
for i in range(n):
    if t[i] < a[i]:
        ans = max(a[i], ans)

print(ans-1)

Submission status: Runtime Error

Solution code:
N, u, v = map(lambda x: int(x)-1, input().split())
N += 1
edges = [list(map(lambda x:int(x)-1, input().split())) for _ in range(N-1)]
adj = [[] for _ in range(N)]
for a, b in edges:
    adj[a].append(b)
    adj[b].append(a)

# bfs from v
dist_from_v = [-1]*N
dist_from_v[v] = 0
Q = {v}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_v[next] == -1:
                dist_from_v[next] = dist_from_v[cur]+1
                tmp.add(next)
    Q = tmp

# bfs from u
dist_from_u = [-1]*N
dist_from_u[u] = 0
Q = {u}
while Q:
    tmp = set()
    for cur in Q:
        for next in adj[cur]:
            if dist_from_u[next] == -1:
                if dist_from_u[cur]+1 < dist_from_v[next]:
                    dist_from_u[next] = dist_from_u[cur]+1
                    tmp.append(next)
    Q = tmp


dst_u = dist_from_u.index(max(dist_from_u))
dist_v_dst = dist_from_v[dst_u]
ans = dist_v_dst-1
print(ans)

Submission status: Runtime Error

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

DU = [-1 for _ in range(N)]  
DV = [-1 for _ in range(N)]
def dfs(p,c,D):
  D[p] = c
  for q in E[p]:
    if D[q] == -1:
      dfs(q,c+1,D)
dfs(u,0,DU)
dfs(v,0,DV)
#print(DU)
#print(DV)
mx = 0
for du,dv in zip(DU,DV):
  if du < dv:
    mx = max(dv,mx)
print(mx-1)

Submission status: Runtime Error

Solution code:
n, runner, chaser = map(int, input().split())
runner -= 1
chaser -= 1
if runner == chaser:
    print(0)

tree = {}
for i in range(n-1):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    if tree.get(a) is None:
        tree[a] = []
    if tree.get(b) is None:
        tree[b] = []
    tree[a].append(b)
    tree[b].append(a)


def dfs(dists, start, d=0, p=-1):  
    dists[start] = d
    for neighbor in tree[start]:
        if neighbor == p:
            continue
        dfs(dists, neighbor, d+1, start)

def dist(start):
    dists = [0 for _ in range(n)]
    dfs(dists, start)
    return dists

furthest = 0
run_dist = dist(runner)
chs_dist = dist(chaser)
for i in range(n):
    if run_dist[i] < chs_dist[i]:
        furthest = max(furthest, chs_dist[i])

ans = furthest-1

print(ans)

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 = [0]
  for k in dv.keys():
    if k in du and du[k] < dv[k]:
      costv.append(dv[k])
  print(max(costv) - 1)