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.