## Tree Distance

View as PDF

Points: 15 (partial)
Time limit: 2.0s
Java 8 6.0s
Python 12.0s
Memory limit: 1G

Author:
Problem types

You are given a tree by your parents for Christmas. They want you to find the length of the path between some $$2$$ nodes. A tree is a graph, such that all nodes are connected, and there is only one simple path between any $$2$$ nodes.

Your parents will give you $$Q$$ questions, of the form $$a\ b$$. For each question, print the length of the path between node $$a$$ and node $$b$$.

The length of a path is defined as the number of edges between $$2$$ nodes.

#### Input Specification

The first line will contain $$2$$ integers $$N, Q\ (1 \le N,Q \le 10^5)$$, the number of nodes in the tree, and the number of questions, respectively.

The next $$N-1$$ lines will each contain $$2$$ integers, $$u_i, v_i\ (1 \le u_i, v_i \le N, u_i \ne v_i)$$, which means that nodes $$u_i$$ and node $$v_i$$ are connected.

The next $$Q$$ lines will each contain $$2$$ integers, $$a, b\ (1 \le a, b \le N)$$.

#### Output Specification

For each question, print the length of the path between node $$a$$ and node $$b$$ on its own line.

$$N, Q \le 1\ 000$$

No further constraints.

#### Sample Input

5 3
1 2
1 3
2 4
2 5
1 2
4 3
4 5

#### Sample Output

1
3
2