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

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

n,u,v=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(n-1)]
graph = [[] for _ in range(n+1)]
for vs in ab:
    graph[vs[0]].append(vs[1])
    graph[vs[1]].append(vs[0])

depth=[[-1,-1] for _ in range(n+1)]
depth[v][0]=0
depth[v][1]=0

def dfs1(graph,v):
    vv=graph[v]
    for vvv in vv:
        if depth[vvv][0]==-1:
            depth[vvv][0]=depth[v][0]+1
            dfs1(graph,vvv)

def dfs2(graph,v):
    vv=graph[v]
    for vvv in vv:
        if depth[vvv][1]==-1:
            depth[vvv][1]=depth[v][1]+1
            dfs2(graph,vvv)

dfs1(graph,v)
dfs2(graph,u)
depth.sort(reverse=True)

idx = 0
while True:
    if depth[idx][0] - depth[idx][1] >= 1:
        print(depth[idx][0]-1)
        exit()
    else:
        idx += 1

Submission status: Wrong Answer

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

n,u,v=map(int, input().split())
ab=[list(map(int, input().split())) for _ in range(n-1)]
graph = [[] for _ in range(n+1)]
for vs in ab:
    graph[vs[0]].append(vs[1])
    graph[vs[1]].append(vs[0])

depth=[[-1,-1] for _ in range(n+1)]
depth[v][0]=0
depth[v][1]=0

def dfs1(graph,v):
    vv=graph[v]
    for vvv in vv:
        if depth[vvv][0]==-1:
            depth[vvv][0]=depth[v][0]+1
            dfs1(graph,vvv)

def dfs2(graph,v):
    vv=graph[v]
    for vvv in vv:
        if depth[vvv][1]==-1:
            depth[vvv][1]=depth[v][1]+1
            dfs2(graph,vvv)

dfs1(graph,v)
dfs2(graph,u)
depth=sorted(depth,reverse=True)

for i in range(10**6):
    if depth[i][0]-depth[i][1]>=1:
        print(depth[i][0]-1)
        break

Submission status: Wrong Answer

Solution code:
import sys
sys.setrecursionlimit(1000000000)

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

dist = [-1]*n
dist[v] = 0
prev = [-1]*n
def dfs(now):
    for nxt in G[now]:
        if dist[nxt] != -1: continue
        dist[nxt] = dist[now]+1
        prev[nxt] = now
        dfs(nxt)
dfs(v)

color = [0]*n
now = u
while now >= 0:
    color[now] = 1
    now = prev[now]

def dfs2(now,prev,dist,cnt):
    if dist == 0: return cnt
    if dist == -1: return cnt-1
    if G[now] == [prev]: return cnt+dist-1
    res = 0
    for nxt in G[now]:
        if nxt == prev: continue
        if color[nxt]: res = max(res,dfs2(nxt,now,dist-2,cnt+1))
        else: res = max(res,dfs2(nxt,now,dist,cnt+1))
    return res

print(dfs2(u,-1,dist[u]-dist[v],0))

Submission status: Wrong Answer

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

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

def bfs1(pos, before_pos):
    for next_pos in ab[pos]:
        if next_pos == before_pos:
            continue
        if next_pos == u:
            return True, [pos]
        tf, root = bfs1(next_pos, pos)
        if tf:
            root.append(pos)
            return True, root
    return False, []
    
root = bfs1(v, -1)[1]
root = root[::-1]
root.append(v)
n = (len(root)) // 2

max_len = 0

def bfs2(pos, before_pos, cnt):
    global max_len
    cnt += 1
    max_len = max(max_len, cnt)
    if cnt < n - 1:
        bfs2(root[cnt + 1], pos, cnt)
    else:
        for next_pos in ab[pos]:
            if next_pos == before_pos:
                continue
            bfs2(next_pos, pos, cnt)


bfs2(v, -1, -1)
ans = max_len - 1
ans = max(ans, 0)
print(ans)

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

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

    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    tt[u] = 0
    qa = queue.Queue()
    qt = queue.Queue()
    qt.put((0,u,-1))
    qa.put((0,v,-1))

    while not qa.empty():
        ti,pi,pp = qa.get()
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] == -1:
                ta[i] = ti+1
                qa.put((ti+1,i,pi))

    while not qt.empty():
        ti,pi,pp = qt.get()
        if ta[pi] <= ti:
            continue
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] > ti:
                tt[i] = ti+1
                qt.put((ti+1,i,pi))

    ma = 0
    for i in range(1,n+1):
        if ma < tt[i]+max(0,ta[i]-tt[i]-1)//2:
            ma = tt[i]+max(0,ta[i]-tt[i]-1)//2
    print(ma)


    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

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

    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    tt[u] = 0
    qa = queue.Queue()
    qt = queue.Queue()
    qt.put((0,u,-1))
    qa.put((0,v,-1))

    while not qa.empty():
        ti,pi,pp = qa.get()
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] == -1:
                ta[i] = ti+1
                qa.put((ti+1,i,pi))

    while not qt.empty():
        ti,pi,pp = qt.get()
        if ta[pi] <= ti:
            continue
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] > ti:
                tt[i] = ti+1
                qt.put((ti+1,i,pi))

    mat = max(tt)
    ma = 0
    for i in range(1,n+1):
        if tt[i] == mat and ma < tt[i]+max(0,ta[i]-tt[i]-1)//2:
            ma = tt[i]+max(0,ta[i]-tt[i]-1)//2
    print(ma)


    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

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

    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    tt[u] = 0
    qa = queue.Queue()
    qt = queue.Queue()
    qt.put((0,u,-1))
    qa.put((0,v,-1))

    while not qa.empty():
        ti,pi,pp = qa.get()
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] == -1:
                ta[i] = ti+1
                qa.put((ti+1,i,pi))

    while not qt.empty():
        ti,pi,pp = qt.get()
        if ta[pi] <= ti:
            continue
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] > ti:
                tt[i] = ti+1
                qt.put((ti+1,i,pi))

    mai = tt.index(max(tt))
    print(tt[mai]+max(0,ta[mai]-tt[mai]-1)//2)


    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

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

    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    qa = queue.Queue()
    qt = queue.Queue()
    qt.put((0,u,-1))
    qa.put((0,v,-1))

    while not qa.empty():
        ti,pi,pp = qa.get()
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] == -1:
                ta[i] = ti+1
                qa.put((ti+1,i,pi))

    while not qt.empty():
        ti,pi,pp = qt.get()
        if ta[pi] <= ti:
            continue
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] > ti:
                tt[i] = ti+1
                qt.put((ti+1,i,pi))

    ma = 0
    for i,tti in enumerate(tt[1::]):
        tai = ta[i+1]
        if tti == -1:
            continue
        if ma < tti+(tai-tti)//2:
            ma = tti+(tai-tti)//2
    print(ma)


    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

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

    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    qa = queue.Queue()
    qt = queue.Queue()
    qt.put((0,u,-1))
    qa.put((0,v,-1))

    while not qa.empty():
        ti,pi,pp = qa.get()
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] == -1:
                ta[i] = ti+1
                qa.put((ti+1,i,pi))

    while not qt.empty():
        ti,pi,pp = qt.get()
        if ta[pi] < ti:
            continue
        for i in way[pi]:
            if i == pp:
                continue
            if ta[i] > ti:
                tt[i] = ti+1
                qt.put((ti+1,i,pi))

    ma = 0
    for i,tti in enumerate(tt[1::]):
        tai = ta[i+1]
        if tti == -1:
            continue
        if ma < tti+(tai-tti)//2:
            ma = tti+(tai-tti)//2
    print(ma)


    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

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

    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    qa = queue.Queue()
    qt = queue.Queue()
    qt.put((0,u))
    qa.put((0,v))

    while not qa.empty():
        ti,pi = qa.get()
        for i in way[pi]:
            if ta[i] == -1:
                ta[i] = ti+1
                qa.put((ti+1,i))

    while not qt.empty():
        ti,pi = qt.get()
        if ta[pi] < ti:
            continue
        for i in way[pi]:
            if ta[i] > ti:
                tt[i] = ti+1
                qt.put((ti+1,i))

'''
    ma = 0
    for i,tti in enumerate(tt[1::]):
        tai = ta[i+1]
        if tti == -1:
            continue
        if ma < tti+(tai-tti)//2:
            ma = tti+(tai-tti)//2
    print(ma)


    return
'''
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

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

    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    qa = queue.Queue()
    qt = queue.Queue()
    qt.put((0,u))
    qa.put((0,v))

    while not qa.empty():
        ti,pi = qa.get()
        for i in way[pi]:
            if ta[i] == -1:
                ta[i] = ti+1
                qa.put((ti+1,i))
'''
    while not qt.empty():
        ti,pi = qt.get()
        if ta[pi] < ti:
            continue
        for i in way[pi]:
            if ta[i] > ti:
                tt[i] = ti+1
                qt.put((ti+1,i))

    ma = 0
    for i,tti in enumerate(tt[1::]):
        tai = ta[i+1]
        if tti == -1:
            continue
        if ma < tti+(tai-tti)//2:
            ma = tti+(tai-tti)//2
    print(ma)


    return
'''
if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
import math
#import numpy as np
import queue
from collections import deque,defaultdict
import heapq as hpq
from sys import stdin,setrecursionlimit
#from scipy.sparse.csgraph import dijkstra
#from scipy.sparse import csr_matrix
ipt = stdin.readline
setrecursionlimit(10**7)

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

    ta = [-1]*(n+1)
    tt = [-1]*(n+1)
    ta[v] = 0 #AOKI
    qa = queue.Queue()
    qt = queue.Queue()
    qt.put((0,u))
    qa.put((0,v))

    while not qa.empty():
        ti,pi = qa.get()
        for i in way[pi]:
            if ta[i] == -1:
                ta[i] = ti+1
                qa.put((ti+1,i))
    while not qt.empty():
        ti,pi = qt.get()
        if ta[pi] < ti:
            continue
        for i in way[pi]:
            if ta[i] > ti:
                tt[i] = ti+1
                qt.put((ti+1,i))

    ma = 0
    for i,tti in enumerate(tt[1::]):
        tai = ta[i+1]
        if tti == -1:
            continue
        if ma < tti+(tai-tti)//2:
            ma = tti+(tai-tti)//2
    print(ma)


    return

if __name__ == '__main__':
    main()

Submission status: Wrong Answer

Solution code:
N,u,v=map(int,input().split())
from collections import deque
g=[[] for _ in range(N)]
for i in range(N-1):
  A,B=map(int,input().split())
  g[A-1].append(B-1)
  g[B-1].append(A-1)
def bfs(n):
  stack=deque([])
  depth=[-1]*N
  depth[n-1]=0
  stack.append(n-1)
  while stack:
    a=stack.popleft()
    for b in g[a]:
      if depth[b]==-1:
        depth[b]=depth[a]+1
        stack.append(b)
  return depth
U=bfs(u)
V=bfs(v)
List=[]
for i in range(N):
  if len(g[i])==1 and U[i]<=V[i]:
    List.append(i)
max=-1
happa=-1
for i in List:
  if U[i]>max:
    max=U[i]
    happa=i

print(V[happa]-1)

Submission status: Wrong Answer

Solution code:
N,u,v=map(int,input().split())
from collections import deque
g=[[] for _ in range(N)]
for i in range(N-1):
  A,B=map(int,input().split())
  g[A-1].append(B-1)
  g[B-1].append(A-1)
def bfs(n):
  stack=deque([])
  depth=[-1]*N
  depth[n-1]=0
  stack.append(n-1)
  while stack:
    a=stack.popleft()
    for b in g[a]:
      if depth[b]==-1:
        depth[b]=depth[a]+1
        stack.append(b)
  return depth
U=bfs(u)
V=bfs(v)
List=[]
for i in range(N):
  if len(g[i])==1 and U[i]<V[i]:
    List.append(i)
max=-1
happa=-1
for i in List:
  if U[i]>max:
    max=U[i]
    happa=i

print(V[happa]-1)

Submission status: Wrong Answer

Solution code:
n,t,aoki=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)

if tree[t-1]==[aoki-1]:
    print(0)
    exit()


from collections import deque
ans=[-1]*n
stack = deque([t-1])
ans[t-1]=0

while len(stack)>0:
    tmp=stack.popleft()
    for item in tree[tmp]:
        if ans[item]==-1:
            ans[item]=ans[tmp]+1
            stack.append(item)


ans2=[-1]*n
stack = deque([aoki-1])
ans2[aoki-1]=0

result=0
#print("hoge",ans2)

while len(stack)>0:
    tmp=stack.popleft()
    for item in tree[tmp]:
        if ans2[item]==-1:
            ans2[item]=ans2[tmp]+1
            stack.append(item)
            if ans[item]<ans2[item]:
                result=max(result,ans2[item])-1
            elif ans[item]==ans2[item]:
                result=max(result,ans2[item])

print(result)

Submission status: Wrong Answer

Solution code:
n,t,aoki=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)


from collections import deque
ans=[-1]*n
stack = deque([t-1])
ans[t-1]=0

while len(stack)>0:
    tmp=stack.popleft()
    for item in tree[tmp]:
        if ans[item]==-1:
            ans[item]=ans[tmp]+1
            stack.append(item)


ans2=[-1]*n
stack = deque([aoki-1])
ans2[aoki-1]=0

result=0
#print("hoge",ans2)

while len(stack)>0:
    tmp=stack.popleft()
    for item in tree[tmp]:
        if ans2[item]==-1:
            ans2[item]=ans2[tmp]+1
            stack.append(item)
            if ans[item]<ans2[item]:
                result=max(result,ans2[item])-1
            elif ans[item]==ans2[item]:
                result=max(result,ans2[item])

print(result)

Submission status: Wrong Answer

Solution code:
from collections import deque

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

not_yet = deque([u-1])
already = [False]*n
already[u-1] = True
dist = [0]*n

while not_yet:
  key = not_yet.popleft()
  for value in tree[key]:
    if already[value]:
      continue
    dist[value] = dist[key] + 1
    already[value] = True
    not_yet.append(value)
  
not_yet = deque([v-1])
already = [False]*n
already[v-1] = True
dist2 = [0]*n

while not_yet:
  key = not_yet.popleft()
  for value in tree[key]:
    if already[value]:
      continue
    dist2[value] = dist2[key] + 1
    already[value] = True
    not_yet.append(value)

judge = dist[v-1]
ans = 0
for i in range(n):
  if dist[i]+dist2[i] > judge:
    sub = dist2[i]-1
  else:
    sub = judge-1
  if sub > ans:
    ans = sub
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
import  math
import fractions
from collections import deque
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,u,v=nm()
u=u-1
v=v-1
INF=10**18
edge=[[] for i in range(N)]

def bfs(start,edge):
    d=[INF]*N
    d[start]=0
    q=deque([start])
    while (q):
        e=q.popleft()
        for i in edge[e]:
            if(d[e]+1<d[i]):
                d[i]=d[e]+1
                q.append(i)   
    return d


for i in range(N-1):
    A,B=nm()
    edge[B-1].append(A-1)
    edge[A-1].append(B-1)


d_A=bfs(u,edge)
d_B=bfs(v,edge)

ans=0
for i in range(N):
    #if(d_A[0]%2==d_B[0]%2):
    #    continue
    #else:
    tmp=max(d_A[i],d_B[i])
    ans=max(ans,tmp)

print(ans-1)

Submission status: Wrong Answer

Solution code:
import sys
import  math
import fractions
from collections import deque
from collections import defaultdict
stdin = sys.stdin
     
ns = lambda: stdin.readline().rstrip()
ni = lambda: int(stdin.readline().rstrip())
nm = lambda: map(int, stdin.readline().split())
nl = lambda: list(map(int, stdin.readline().split()))

N,u,v=nm()
u=u-1
v=v-1
INF=10**18
edge=[[] for i in range(N)]

def bfs(start,edge):
    d=[INF]*N
    d[start]=0
    q=deque([start])
    while (q):
        e=q.popleft()
        for i in edge[e]:
            if(d[e]+1<d[i]):
                d[i]=d[e]+1
                q.append(i)   
    return d


for i in range(N-1):
    A,B=nm()
    edge[B-1].append(A-1)
    edge[A-1].append(B-1)


d_A=bfs(u,edge)
d_B=bfs(v,edge)

ans=0
for i in range(N):
    if(d_A[0]%2==d_B[0]%2):
        continue
    else:
        tmp=max(d_A[i],d_B[i])
        ans=max(ans,tmp)

print(ans-1)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,u,v=map(int,input().split())
g=[set([]) for _ in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].add(b)
    g[b].add(a)

leaf=[]
for i in range(1,n+1):
    if(len(g[i])==1):
        leaf.append(i)

d_a=[-1 for _ in range(n+1)]
d_b=[-1 for _ in range(n+1)]

def bfs(start,d):
    d[start]=0
    q=deque([start])

    while(len(q)>0):
        qi=q.popleft()
        di=d[qi]

        next_qi=g[qi]
        for i in next_qi:
            if(d[i]==-1):
                d[i]=di+1
                q.append(i)

    return d


d_a=bfs(a, d_a)
d_b=bfs(b, d_b)


if(u in leaf and list(g[u])[0]==v):
    print(0)
else:
    ans=0
    for li in leaf:
        if(d_a[li]<d_b[li]):
            ans=max(ans,d_b[li]-1)
    print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
n,u,v=map(int,input().split())
g=[set([]) for _ in range(n+1)]
for i in range(n-1):
    a,b=map(int,input().split())
    g[a].add(b)
    g[b].add(a)

leaf=[]
for i in range(1,n+1):
    if(len(g[i])==1):
        leaf.append(i)

d_a=[-1 for _ in range(n+1)]
d_b=[-1 for _ in range(n+1)]

def bfs(start,d):
    d[start]=0
    q=deque([start])

    while(len(q)>0):
        qi=q.popleft()
        di=d[qi]

        next_qi=g[qi]
        for i in next_qi:
            if(d[i]==-1):
                d[i]=di+1
                q.append(i)

    return d


d_a=bfs(a, d_a)
d_b=bfs(b, d_b)

ans=0
for li in leaf:
    if(d_a[li]<d_b[li]):
        ans=max(ans,d_b[li]-1)
print(ans)

Submission status: Wrong Answer

Solution code:
N, u, v = (int(i) for i in input().split())
adj=[]
for i in range(N+1):adj.append([])
for i in range(N-1):
	a,b = map(int,input().split())
	adj[a]+=[b]
	adj[b]+=[a]
	
prof = [0]*(N+1)
haut = [0]*(N+1)
parent = [-1]*(N+1)

def enraciner(sommet):
	for s in adj[sommet]:
		if s!=parent[sommet]:
			parent[s] = sommet
			prof[s] = 1+prof[sommet]
			enraciner(s)
	haut[sommet] = 1
	tmp = [haut[s]for s in adj[sommet] if s!=parent[sommet]]
	if tmp: haut[sommet]+=max(tmp)

# ~ enraciner(v)

# ~ print("parent",parent)
# ~ print("haut",haut)
# ~ print("prof",prof)

ans = 0

#montee
pu = prof[u]
pv = prof[v]
m = (pu - pv -1)//2
pu-=m
pv+=m
# ~ print("m",m)
ans+=m
for i in range(m):
	u = parent[u]

mx = 0
# ~ if len(adj[u])>1:mx = max(haut[i] for i in adj[u] if i!= parent[u])
# ~ print("mx",mx)
ans+= mx

last = (pu-pv)//2
# ~ print("last",last)
ans+=last

print(ans)

Submission status: Wrong Answer

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

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

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

stack = [u-1]
check = [False]*n
check[u-1] = True
check[v-1] = True
takahasi = [0]*n

while stack:
    now = stack.pop()
    for i in range(len(graph[now])):
        if check[graph[now][i]]:continue
        check[graph[now][i]] = True
        stack.append(graph[now][i])
        takahasi[graph[now][i]] = 1 + takahasi[now]

aoki = [0]*n
stack = [v-1]
check = [False]*n
check[v-1] = True
while stack:
    now = stack.pop()
    for i in range(len(graph[now])):
        if check[graph[now][i]]:continue
        check[graph[now][i]] = True
        stack.append(graph[now][i])
        aoki[graph[now][i]] = 1 + aoki[now]

#print(takahasi)
#print(aoki)

ans = 0
ans_= n+1
takahasi[u-1] = -1

henone = [0]*n
for i in range(n):
    if len(graph[i]) == 1:
        henone[i] = 1

for i in range(n):
    if henone[i] == 1 and takahasi[i] != 0:
        ans = max(aoki[i]-1,ans)
    """
    if takahasi[i] == 0:continue
    if takahasi[i] < aoki[i]:
        if (aoki[i] - takahasi[i]) % 2 == 1:
            ans = max(ans,aoki[i]-1)
        else:
            ans = max(ans,aoki[i])
    elif takahasi[i] == aoki[i]:
        ans_ = min(ans_,takahasi[i])
    """
print(ans)

Submission status: Wrong Answer

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

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

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

stack = [u-1]
check = [False]*n
check[u-1] = True
check[v-1] = True
takahasi = [0]*n

while stack:
    now = stack.pop()
    for i in range(len(graph[now])):
        if check[graph[now][i]]:continue
        check[graph[now][i]] = True
        stack.append(graph[now][i])
        takahasi[graph[now][i]] = 1 + takahasi[now]

aoki = [0]*n
stack = [v-1]
check = [False]*n
check[v-1] = True
while stack:
    now = stack.pop()
    for i in range(len(graph[now])):
        if check[graph[now][i]]:continue
        check[graph[now][i]] = True
        stack.append(graph[now][i])
        aoki[graph[now][i]] = 1 + aoki[now]

#print(takahasi)
#print(aoki)

ans = 0
ans_= n+1

henone = [0]*n
for i in range(n):
    if len(graph[i]) == 1:
        henone[i] = 1

for i in range(n):
    if henone[i] == 1:
        ans = max(aoki[i]-1,ans)
    """
    if takahasi[i] == 0:continue
    if takahasi[i] < aoki[i]:
        if (aoki[i] - takahasi[i]) % 2 == 1:
            ans = max(ans,aoki[i]-1)
        else:
            ans = max(ans,aoki[i])
    elif takahasi[i] == aoki[i]:
        ans_ = min(ans_,takahasi[i])
    """
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque
from heapq import heapify,heappop,heappush,heappushpop
from copy import copy,deepcopy
from itertools import product,permutations,combinations,combinations_with_replacement
from collections import defaultdict,Counter
from bisect import bisect_left,bisect_right
# from math import gcd,ceil,floor,factorial
# from fractions import gcd
from functools import reduce
from pprint import pprint

INF = float("inf")

def myinput():
    return map(int,input().split())

def mylistinput(n):
    return [ list(myinput()) for _ in range(n) ]

def mycol(data,col):
    return [ row[col] for row in data ]

def mysort(data,col,reverse_flag):
    data.sort(key=lambda x:x[col],reverse=reverse_flag)
    return data

def mymax(data):
    M = -1*float("inf")
    for i in range(len(data)):
        m = max(data[i])
        M = max(M,m)
    return M

def mymin(data):
    m = float("inf")
    for i in range(len(data)):
        M = min(data[i])
        m = min(m,M)
    return m

def mycount(ls,x):
    # lsはソート済みであること
    l = bisect_left(ls,x)
    r = bisect_right(ls,x)
    return (r-l)

def myoutput(ls,space=True):
    if space:
        if len(ls)==0:
            print(" ")
        elif type(ls[0])==str:
            print(" ".join(ls))
        elif type(ls[0])==int:
            print(" ".join(map(str,ls)))
        else:
            print("Output Error")
    else:
        if len(ls)==0:
            print("")
        elif type(ls[0])==str:
            print("".join(ls))
        elif type(ls[0])==int:
            print("".join(map(str,ls)))
        else:
            print("Output Error")


def getTreeDiameter(n,G):
    N = n
    # N: 木Tの頂点数
    # G[u] = [(w, c), ...]:
    #   頂点uに隣接する頂点wとそれを繋ぐ辺の長さc
    # from collections import deque
    def bfs(s):
        dist = [None]*N
        que = deque([s])
        dist[s] = 0
        while que:
            v = que.popleft()
            d = dist[v]
            for w, c in G[v]:
                if dist[w] is not None:
                    continue
                dist[w] = d + c
                que.append(w)
        d = max(dist)
        return dist.index(d), d
    u, _ = bfs(0)
    v, d = bfs(u)
    # パスu-vがこの木Tの直径(長さd)
    return d

n,u,v = myinput()
g = [ [] for _ in range(n) ]
for i in range(n-1):
    a,b = myinput()
    a -= 1
    b -= 1
    g[a].append((b,1))
    g[b].append((a,1))
# print(g)

d = getTreeDiameter(n,g)
# print(d)
ans = d - 1
print(ans)

Submission status: Wrong Answer

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


def solve(x):
    visit = [-1 for _ in range(n+1)]
    visit[x] = 0
    q = deque([x])
    while q:
        p = q.popleft()
        for i in tree[p]:
            if visit[i] < 0:
                visit[i] = visit[p]+1
                q.append(i)
    return visit

visit_a = solve(v)
visit_t = solve(u)

x, y = [], []
for i in range(1, n+1):
    if visit_a[i] >= visit_t[i]:
        x.append(visit_a[i])
        y.append(visit_t[i])
p = y.index(max(y))

print(x[p]-1)

Submission status: Wrong Answer

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


def solve(x):
    visit = [-1 for _ in range(n+1)]
    visit[x] = 0
    q = deque([x])
    while q:
        p = q.popleft()
        for i in tree[p]:
            if visit[i] < 0:
                visit[i] = visit[p]+1
                q.append(i)
    return visit

visit_a = solve(v)
visit_t = solve(u)

x, y = [], []
for i in range(1, n+1):
    if visit_a[i] >= visit_t[i]:
        x.append(visit_a[i])
        y.append(visit_t[i])
p = y.index(max(y))

if y[p]==0:
    print(0)
else:
    print(x[p]-1)