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 nodes. A tree is a graph, such that all nodes are connected, and there is only one simple path between any nodes.

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

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

Input Specification

The first line will contain integers , the number of nodes in the tree, and the number of questions, respectively.

The next lines will each contain integers, , which means that nodes and node are connected.

The next lines will each contain integers, .

Output Specification

For each question, print the length of the path between node and node on its own line. 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