Tree Distance

View as PDF

Submit solution


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.

Subtasks

Subtask 1 [30%]

N, Q \le 1\ 000

Subtask 2 [70%]

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

Comments

There are no comments at the moment.