倍增LCA + 求最短路

import java.util.*;
import java.io.*;

public class Main{
	static final int N = 100010, M = N * 2;
	static final long INF = (long)1e18;
	static int n, m;
	static int[] h = new int[N];
	static int[] e = new int[M];
	static int[] ne = new int[M];
	static int[] w = new int[N];
	static int idx;
	static long[] dist = new long[N];
	static int[][] f = new int[N][17];
	static int[] depth = new int[N];
	
	public static void main(String[] args) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] str = br.readLine().split(" ");
		n = Integer.parseInt(str[0]);
		m = Integer.parseInt(str[1]);
		
		List<Integer>[] list = new ArrayList[N];
		
		for(int i=1 ; i<=n ; i++)
			list[i] = new ArrayList<>();
		
		for(int i=0 ; i<n-1 ; i++)
		{
			str = br.readLine().split(" ");
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);

			list[a].add(b);
			list[b].add(a);
		}
		
		Arrays.fill(h, -1);
		
		for(int i=1 ; i<=n ; i++)
		{
			int c = list[i].size();
			w[i] = c;
			
			for(int x: list[i])
				add(i, x);
		}
		
		bfs();
		
		while(m -- > 0)
		{
			str = br.readLine().split(" ");
			int a = Integer.parseInt(str[0]);
			int b = Integer.parseInt(str[1]);
			
			int c = lca(a, b);
			
			long res = dist[a] + dist[b] - dist[c] * 2 + w[c];
			
			bw.write(res + "\n");
		}
		
		bw.flush();
	}
	
	public static void add(int a, int b)
	{
		e[idx] = b; ne[idx] = h[a]; h[a] = idx++;
	}
	
	public static void bfs()
	{
		Arrays.fill(dist, INF);
		Arrays.fill(depth, 0x3f3f3f3f);
		depth[0] = 0;
		Queue<Integer> q = new LinkedList<>();
		
		q.add(1);
		dist[1] = 0;
		depth[1] = 1;
		
		while(q.size() > 0)
		{
			int t = q.remove();
			
			for(int i=h[t] ; i!=-1 ; i=ne[i])
			{
				int j = e[i];
				
				if(depth[j] > dist[t] + 1)
				{
					depth[j] = depth[t] + 1;
					dist[j] = dist[t] + w[j];
					q.add(j);
					f[j][0] = t;
					
					for(int k=1 ; k<=16 ; k++)
						f[j][k] = f[f[j][k - 1]][k - 1];
				}
			}
		}
	}
	
	public static int lca(int a, int b)
	{
		if(depth[a] < depth[b])
		{
			int temp = a;
			a = b;
			b = temp;
		}
		
		for(int k=16 ; k>=0 ; k--)
			if(depth[f[a][k]] >= depth[b])
				a = f[a][k];
		
		if(a == b) return a;
		
		for(int k=16 ; k>=0 ; k--)
			if(f[a][k] != f[b][k])
			{
				a = f[a][k];
				b = f[b][k];
			}
		
		return f[a][0];
	}
}