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.
Subtasks
Subtask 1 [30%]
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