COCI '15 Contest 4 #4 Chewbacca

View as PDF

Points: 12 (partial)
Time limit: 0.6s
Memory limit: 64M

Problem type

You are given a tree of order with nodes or, in other words, each node can have at most children. The tree is constructed so it's of the "lowest energy": the nodes are placed in a new depth of the tree only when all the places (from left to right) in the previous depth have been filled. This is also the order of enumerating the nodes, starting with . Image depicts an example of a tree of order with nodes.

You need to output answers to queries in the form of x y, where the answer is the minimal number of steps needed to get from node to node .

Input

The first line of input contains the integers , and from the task.

Each of the following lines contains pairs from the task.

Output

Output lines, each line containing the answer to a query from the task.

Scoring

In test cases worth 20% of total points, it will hold .

In test cases worth 50% of total points, it will hold .

Sample Input 1

7 2 3
1 2
2 1
4 7

Sample Output 1

1
1
4

Explanation for Sample Output 1

You are given a complete binary tree. Node is a direct child of node so the distance between them is exactly . Nodes and are on complete opposite sides of the tree, so the distance between them is : .

Sample Input 2

9 3 3
8 9
5 7
8 4

Sample Output 2

2
2
3

Explanation for Sample Output 2

This example corresponds to the image.