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

Solution (Python):
N,U,V = map(int,input().split())
U,V = U-1, V-1

adj = [list() for _ in range(N)]

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



dist_u = [None]*N
dist_u[U] = 0
stack = [U]

while stack:
    x = stack.pop()
    d = dist_u[x]+1
    for y in adj[x]:
        if dist_u[y] is None:
            dist_u[y] = d
            stack.append(y)


dist_v = [None]*N
dist_v[V] = 0
stack = [V]

while stack:
    x = stack.pop()
    d = dist_v[x]+1
    for y in adj[x]:
        if dist_v[y] is None:
            dist_v[y] = d
            stack.append(y)

n = max(b for a,b in zip(dist_u, dist_v) if a < b)
m = min((b for a,b in zip(dist_u, dist_v) if a <= b), default=n)

print(max(n,m)-1)

Solution (Python):
from collections import deque

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

graph = [[] for _ in range(N)]

for e in edge:
    graph[e[0]-1].append(e[1]-1)
    graph[e[1]-1].append(e[0]-1)

level = [-1 for _ in range(N)]
level[v-1] = 0

queue = deque([v-1])

while queue:
    node = queue.popleft()
    for adj in graph[node]:
        if level[adj]==-1:
            level[adj] = level[node] + 1
            queue.append(adj)

t = level[u-1]

stack = [u-1]
maxlevel = t
visited = [0 for _ in range(N)]
visited[u-1] = 0
a = 0

while stack:
    node = stack.pop()
    for adj in graph[node]:
        if not visited[adj] and t-level[adj]<=(t-1)//2:
            stack.append(adj)
            maxlevel = max(maxlevel,level[adj])
            visited[adj] = 1

d = maxlevel-t

print(d+t-1)

Solution (Python):
import sys
input = sys.stdin.readline

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



parent = [None]*N
parent[v-1] = -1
depth = [None]*N
depth[v-1] = 0

queue = [v-1]
d=1
while queue:
    queue_new = []
    for q in queue:
        for e in E[q]:
            if parent[e] is not None: continue
            parent[e] = q
            queue_new.append(e)
            depth[e] = d

    queue = queue_new
    d+=1




w = u-1
x = (depth[u-1]-1)//2
for _ in range(x):
    w = parent[w]
    



depth_from_w = 0
queue = [w]
while queue:
    queue_new = []
    for q in queue:
        for e in E[q]:
            if e==parent[q]: continue
            queue_new.append(e)

    queue = queue_new
    depth_from_w+=1


print(depth[w] + depth_from_w-2)

Solution (Python):
import sys
input=sys.stdin.readline
n,u,v=map(int,input().split())
Edge=[[] for i in range(n)]
for i in range(n-1):
  a,b=map(int,input().split())
  Edge[a-1].append(b-1)
  Edge[b-1].append(a-1)


from collections import deque

def BFS(s):
  dist=[-1]*n
  que=deque([s-1])
  dist[s-1]=0
  while que:
    v=que.popleft()
    d=dist[v]
    for w in Edge[v]:
      if dist[w]>-1:
        continue
      dist[w]=d+1
      que.append(w)
  return dist

U_d,V_d=BFS(u),BFS(v)
ans=0
for i in range(n):
  if U_d[i]<V_d[i]:
    ans=max(ans,V_d[i]-1)
print(ans)

Solution (Python):
n, u, v = (int(i) for i in input().split())
ablist=[]
onilist=[-1]*n
whelist=[]
sudelist=[0]*n
for i in range(n):
    whelist.append([])

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



onilist[v-1]=0

mark=1
now=[v-1]
turn=1
while mark<n:
    nextis=[]
    for nw in now:
        nextis+=whelist[nw]
    now=[]
    for nx in nextis:
        if onilist[nx]==-1:
            onilist[nx]=turn
            now.append(nx)
            mark+=1
    turn+=1



swit=0
nowmax=onilist[u-1]
limit=nowmax//2

now=[u-1]
sudelist[u-1]=1

while swit==0:
    nextis=[]
    for nw in now:
        nextis+=whelist[nw]
    now=[]
    
    for nx in nextis:
        if sudelist[nx]==0 and onilist[nx]>limit:
            now.append(nx)
            sudelist[nx]=1
            if onilist[nx]>nowmax:
                nowmax=onilist[nx]
    
    if now==[]:
        swit=1


print(nowmax-1)

Solution (Python):

import sys
input = sys.stdin.buffer.readline


from collections import defaultdict
import queue

INF = float("inf")

class Graph(object):
	def __init__(self):
		self.graph = defaultdict(list)

	def __len__(self):
		return len(self.graph)

	def add_edge(self, a, b):
		self.graph[a].append(b)

	def get_nodes(self):
		return self.graph.keys()

class BFS(object):
	def __init__(self, graph, s, N):
		self.g = graph.graph
		self.Q = queue.Queue()
		self.Q.put(s)
		self.dist = [INF] * N
		self.dist[s] = 0
		self.visit = ["No"] * N
		self.visit[s] = "Yes"
		while not self.Q.empty():
			v = self.Q.get()
			for i in self.g[v]:
				if self.visit[i] == "No":
					self.dist[i] = self.dist[v] + 1
					self.Q.put(i)
					self.visit[i] = "Yes"


def getlist():
	return list(map(int, input().split()))


def main():
	N, u, v = getlist()
	u -= 1; v -= 1
	G = Graph()
	for i in range(N - 1):
		A, B = getlist()
		A -= 1; B -= 1
		G.add_edge(A, B)
		G.add_edge(B, A)
	BF_taka = BFS(G, u, N)
	BF_ao = BFS(G, v, N)
	taka_dist = BF_taka.dist
	ao_dist = BF_ao.dist
	dis = 0

	for i in range(N):
		val = taka_dist[i]
		xval = ao_dist[i]
		if val < xval:
			dis = max(dis, xval)
	
	print(dis - 1)


if __name__ == '__main__':
	main()

Solution (Python):
import sys
input = sys.stdin.readline
n,T,A = map(int, input().split(' '))
ab = [list(map(int, input().split(' '))) for i in range(n-1)]
graph = [[] for i in range(n+1)]
parent = [0 for i in range(n+1)]
dist = [0 for i in range(n+1)]
root = A
order = []
stack = [root]
for a,b in ab:
    graph[a].append(b)
    graph[b].append(a)
while stack:
    x = stack.pop()
    order.append(x)
    for y in graph[x]:
        if parent[x] == y:
            continue
        parent[y] = x
        stack.append(y)
for x in order:
    if x == root:
        continue
    dist[x] = 1+dist[parent[x]]

dist_ini = dist[T]
ans = 0
if dist_ini > 2:
    ans += (dist_ini-1)//2
    for i in range(ans):
        T = parent[T]
    dist_n = (dist_ini-1)%2+1
else:
    dist_n = dist_ini

stack = [(T,0)]
dist_final = 0
while stack:
    x,cnt = stack.pop()
    dist_final = max(dist_final,cnt)
    for y in graph[x]:
        if parent[x] == y:
            continue
        stack.append((y,cnt+1))
ans += dist_final
if dist_ini % 2 == 0:
    ans += 1
print(ans)

Solution (Python):
from collections import deque


n, u, v = map(int, input().split())
info = [list(map(int, input().split())) for i in range(n - 1)]

tree = [[] for i in range(n)]
for i in range(n - 1):
    a, b = info[i]
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

v -= 1
u -= 1

root = u
visited = [False] * n
q = deque([root])
visited[root] = True
new_tree = [[] for i in range(n)]

while q:
    pos = q.pop()
    for next_pos in tree[pos]:
        if visited[next_pos]:
            continue
        visited[next_pos] = True
        if next_pos != v:
            q.append(next_pos)
        new_tree[pos].append(next_pos)
        new_tree[next_pos].append(pos)

is_leaf = [False] * n
for i in range(n):
    if len(new_tree[i]) == 1:
        is_leaf[i] = True
        
time = [-1] * n
root = v
time[root] = 0
q = deque([root])
while q:
    pos = q.pop()
    for next_pos in new_tree[pos]:
        if time[next_pos] >= 0:
            continue
        time[next_pos] = time[pos] + 1
        q.append(next_pos)


time2 = [-1] * n
root = u
time2[root] = 0
q = deque([root])
while q:
    pos = q.pop()
    for next_pos in new_tree[pos]:
        if time2[next_pos] >= 0:
            continue
        time2[next_pos] = time2[pos] + 1
        q.append(next_pos)



can_reach = [False] * n
for i in range(n):
    if time[i] > time2[i] and is_leaf[i]:
        can_reach[i] = True
    
ans = 0
for i in range(n):
    if can_reach[i]:
        ans = max(ans, time[i] - 1)
print(ans)

Solution (Python):
import sys

sys.setrecursionlimit(10 ** 5)


def dfs(v, parent, depth):
    parents[v] = parent
    self_depths[v] = depth
    sd = 0
    for u in links[v]:
        if u == parent:
            continue
        res = dfs(u, v, depth + 1)
        sd = max(sd, res + 1)

    subtree_depths[v] = sd
    return sd


def solve(u):
    ans = 0
    catch = self_depths[u] // 2
    while self_depths[u] > catch:
        ans = max(ans, self_depths[u] + subtree_depths[u] - 1)
        u = parents[u]
    return ans


n, u, v = map(int, input().split())
u -= 1
v -= 1
links = [set() for _ in range(n)]
for line in sys.stdin:
    a, b = map(int, line.split())
    a -= 1
    b -= 1
    links[a].add(b)
    links[b].add(a)

parents = [-1] * n
self_depths = [0] * n
subtree_depths = [0] * n
dfs(v, -1, 0)



print(solve(u))

Solution (Python):
n, u, v = map(int, input().split())
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)
d1 = [-1] * n
d1[u - 1] = 0
s = [u - 1]
while s:
    d = s.pop()
    for node in g[d]:
        if d1[node] == -1:
            s.append(node)
            d1[node] = d1[d] + 1
d2 = [-1] * n
d2[v - 1] = 0
s = [v - 1]
while s:
    d = s.pop()
    for node in g[d]:
        if d2[node] == -1:
            s.append(node)
            d2[node] = d2[d] + 1
m = 0
mi = 0
for i in range(n):
    if d1[i] < d2[i]:
        if m < d2[i]:
            m = d2[i]
            mi = i
print(m - 1)

Solution (Python):
import sys
from collections import deque
input = sys.stdin.buffer.readline

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

que = deque()
que.append(u0)
du = [-1] * (N+1)
du[u0] = 0
while que:
    v = que.popleft()
    for u in adj[v]:
        if du[u] == -1:
            du[u] = du[v] + 1
            que.append(u)

que = deque()
que.append(v0)
dv = [-1] * (N+1)
dv[v0] = 0
while que:
    v = que.popleft()
    for u in adj[v]:
        if dv[u] == -1:
            dv[u] = dv[v] + 1
            que.append(u)

duv = [du[i] - dv[i] for i in range(N+1)]

ans = 0

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

Solution (Python):
import sys
input = sys.stdin.readline

N,u,v=map(int,input().split())
E=[tuple(map(int,input().split())) for i in range(N-1)]

EDGE=[[] for i in range(N+1)]

for x,y in E:
    EDGE[x].append(y)
    EDGE[y].append(x)

from collections import deque
T=[-1]*(N+1)

Q=deque()
Q.append(u)
T[u]=0

while Q:
    x=Q.pop()
    for to in EDGE[x]:
        if T[to]==-1:
            T[to]=T[x]+1
            Q.append(to)

A=[-1]*(N+1)

Q=deque()
Q.append(v)
A[v]=0

while Q:
    x=Q.pop()
    for to in EDGE[x]:
        if A[to]==-1:
            A[to]=A[x]+1
            Q.append(to)


OK=[0]*(N+1)

for i in range(N+1):
    if T[i]<A[i]:
        OK[i]=1

ANS=0
for i in range(N+1):
    if OK[i]==1:
        ANS=max(ANS,A[i])

print(max(0,ANS-1))

Solution (Python):
import sys
input = sys.stdin.readline
from collections import deque
N, u, v = map(int, input().split())
u, v = u-1, v-1
X = [[] for i in range(N)]
for i in range(N-1):
    x, y = map(int, input().split())
    X[x-1].append(y-1)
    X[y-1].append(x-1)

P = [-1] * N
Q = deque([v])
R = []
while Q:
    i = deque.popleft(Q)
    R.append(i)
    for a in X[i]:
        if a != P[i]:
            P[a] = i
            X[a].remove(i)
            deque.append(Q, a)

DE = [0] * N
for i in R[1:]:
    DE[i] = DE[P[i]] + 1

D = [0] * N
for i in R[::-1]:
    D[i] = max([D[j] for j in X[i]] + [DE[i]])

i = u
ma = D[i]
while True:
    i = P[i]
    if DE[i] * 2 <= DE[u]: break
    ma = max(ma, D[i])

print(ma - 1)

Solution (Python):
import sys
input = sys.stdin.readline

n,u,v = map(int,input().split())
C = [list(map(int,input().split())) for i in range(n-1)]

V = [-1] * (n+1)
W = [-1] * (n+1)


M = [[] for i in range(n+1)]
for i in range(n-1):
    M[C[i][0]].append(C[i][1])
    M[C[i][1]].append(C[i][0])


Q = [[u,0]]
s = 0
V[u] = 0
while s < len(Q):
    i = Q[s][0]
    d = Q[s][1]
    for x in M[i]:
        if V[x] == -1:
            V[x] = d+1
            Q.append([x,d+1])
    s += 1

Q = [[v,0]]
s = 0
W[v] = 0
while s < len(Q):
    i = Q[s][0]
    d = Q[s][1]
    for x in M[i]:
        if W[x] == -1:
            W[x] = d+1
            Q.append([x,d+1])
    s += 1



ans = 0
for i in range(len(V)):
    if W[i] > V[i]:
        ans = max(ans,W[i])
print(ans-1)

Solution (Python):
from collections import deque

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

AB = []
dic = {}

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

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

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

q = deque([u])

tk = [float("inf")] * N
tk[u] = 0

while len(q) > 0:

    now = q.popleft()

    for i in dic[now]:

        if tk[i] > tk[now] + 1:
            tk[i] = tk[now] + 1
            q.append(i)



ao = [float("inf")] * N
q = deque([v])
ao[v] = 0

while len(q) > 0:

    now = q.popleft()

    for i in dic[now]:

        if ao[i] > ao[now] + 1:
            ao[i] = ao[now] + 1
            q.append(i)

ans = 0
for i in range(N):

    if ao[i] > tk[i]:
        ans = max(ans , ao[i] - 1)

print (ans)

Solution (Python):
def examA():
    AB = [I() for _ in range(2)]
    for i in range(1,4):
        if not i in AB:
            ans = i
            break
    print(ans)
    return

def examB():
    N = I()
    S,T = LSI()
    ans = ""
    for i in range(N):
        ans += S[i]+T[i]
    print(ans)
    return

def gcd(x, y):
    if y == 0:
        return x
    while y != 0:
        x, y = y, x % y
    return x
def lcm(x, y):
    return x * y // gcd(x, y)
def examC():
    A, B = LI()
    ans = lcm(A,B)
    print(ans)
    return

def examD():
    N = I()
    A = LI()
    ans = N; cur = 1
    for a in A:
        if cur==a:
            ans -=1
            cur +=1
    if ans==N:
        ans = -1
    print(ans)
    return

def examE():
    N = I()
    ans = 0
    if N%2==0:
        N //=2
        while(N>0):
            ans +=N//5
            N //=5
    print(ans)
    return


def bfs(n,e,fordfs):
    
    W = [-1]*n
    
    W[e] = 0
    que = deque()
    que.append(e)
    len = [float("inf")]*n
    len[e] = 0
    while que:
        now = que.popleft()
        nowv = W[now]
        nowlen = len[now]
        for ne in fordfs[now]:
            if nowv == W[ne]:
                
                return -1
            elif W[ne] == -1:
                W[ne] = (nowv+1) % 2
                len[ne] = nowlen+1
                que.append(ne)
    return len
def examF():
    N, u, v = LI()
    V = [[] for _ in range(N)]
    for _ in range(N-1):
        a, b = LI()
        V[a-1].append(b-1)
        V[b-1].append(a-1)
    La = bfs(N,u-1,V)
    Lb = bfs(N,v-1,V)


    ans = 0
    for i in range(N):
        if La[i]>Lb[i]:
            continue
        ans = max(Lb[i],ans)
    print(ans-1)
    return

import sys,copy,bisect,itertools,heapq,math
from heapq import heappop,heappush,heapify
from collections import Counter,defaultdict,deque
def I(): return int(sys.stdin.readline())
def LI(): return list(map(int,sys.stdin.readline().split()))
def LSI(): return list(map(str,sys.stdin.readline().split()))
def LS(): return sys.stdin.readline().split()
def SI(): return sys.stdin.readline().strip()
mod = 10**9 + 7
inf = float('inf')

if __name__ == '__main__':
    examF()

Solution (Python):

from collections import defaultdict,deque
from heapq import heappush, heappop
import sys
import math
import bisect
import random
def LI(): return [int(x) for x in sys.stdin.readline().split()]
def I(): return int(sys.stdin.readline())
def LS():return [list(x) for x in sys.stdin.readline().split()]
def S():
    res = list(sys.stdin.readline())
    if res[-1] == "\n":
        return res[:-1]
    return res
def IR(n):
    return [I() for i in range(n)]
def LIR(n):
    return [LI() for i in range(n)]
def SR(n):
    return [S() for i in range(n)]
def LSR(n):
    return [LS() for i in range(n)]

sys.setrecursionlimit(1000000)
mod = 1000000007

def solve():
    def lca(x,y):
        k = depth[x] - depth[y]
        while k > 0:
            x = par[x][int(math.log(k,2))]
            k = depth[x] - depth[y]
        k = -k
        while k > 0:
            y = par[y][int(math.log(k,2))]
            k = depth[y] - depth[x]
        if x == y:
            return x
        for i in range(17)[::-1]:
            if par[x][i] != par[y][i]:
                x = par[x][i]
                y = par[y][i]
        return par[x][0]
    n,s,t = LI()
    s -= 1
    t -= 1
    v = [[] for i in range(n)]
    f = [0]*n
    for i in range(n-1):
        a,b = LI()
        a -= 1
        b -= 1
        v[a].append(b)
        v[b].append(a)
        f[a] += 1
        f[b] += 1
    l = []
    for i in range(n):
        if f[i] == 1:
            l.append(i)
    par = [[] for i in range(n)]
    par[t].append(t)
    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)
                par[y].append(x)
    d = [-1]*n
    d[s] = 0
    q = deque([s])
    while q:
        x = q.popleft()
        for y in v[x]:
            if d[y] < 0:
                d[y] = d[x]+1
                q.append(y)
    for i in range(16):
        for x in range(n):
            par[x].append(par[par[x][i]][i])
    l.sort(key = lambda x:-depth[x])
    for i in l:
        x = lca(i,s)
        if d[x] < depth[x]:
            break
    print(depth[i]-1)
    return


if __name__ == "__main__":
    solve()

Solution (Python):
import itertools, heapq, bisect
from collections import defaultdict as ddic, deque, Counter

rr = raw_input
rri = lambda: int(raw_input())
rrm = lambda: map(int, raw_input().split())
MOD = 10 ** 9 + 7



def solve(N, T, A, graph):
    if T == A: return 0
    stack = [(A, None)]
    seen = {A}
    back = {}
    while stack:
        node, par = stack.pop()
        back[node] = par
        for nei in graph[node]:
            if nei != par:
                if nei not in seen:
                    stack.append((nei, node))
                    seen.add(nei)

    path = [T]
    while back[path[-1]] is not None:
        path.append(back[path[-1]])

    def bfs(source, par):
        queue = deque([(source, par, 0)])
        d=  0
        while queue:
            node, par, d = queue.popleft()
            for nei in graph[node]:
                if nei != par:
                    queue.append((nei, node, d+1))
        return d
    
    ans = 0
    i = 0
    j = len(path) - 1
    while i + 2 < j:
        i += 1
        j -= 1
        ans += 1
    
    
    ans += j-i-1
    ans += bfs(path[i], path[i+1])
    return ans


N, T, A = rrm()
T -= 1; A -= 1
graph = [[] for _ in xrange(N)]

for _ in xrange(N-1):
    a, b = rrm()
    a -= 1; b -= 1
    graph[a].append(b)
    graph[b].append(a)

print solve(N, T, A, graph)