Background

Problem T3 of this contest set is P8053.

Problem Description

A $k$-ary tree with $n$ nodes is constructed in the following way:

• First, create a root node and label it as $1$.
• Then repeat the following steps until the total number of nodes is exactly $n$:
  • Let the label of the last newly added node be $x$.
  • In the previous level, scan from left to right to find the first node whose number of children is $< k$.
    • If this node has no children, add a child node under it, label it as $x + 1$, and connect node $x + 1$ and the parent node we found with an edge of length $1$.
    • Otherwise, add a new child node immediately to the right of the most recently added child of this node, label it as $x + 1$, and connect node $x + 1$ and the parent node we found with an edge of length $1$.
  • If no node with number of children $< k$ is found in the current level, move to the next level.

For example, the figure below shows a $3$-ary tree with $9$ nodes constructed by the method above:

Now you are given this $k$-ary tree with $n$ nodes, and you need to answer $q$ queries. Each query gives two integers $x, y$, and you need to output the length of the shortest path from node $x$ to node $y$ in this tree.

Input Format

The first line contains three integers $n, k, q$, representing the number of nodes in the tree, the arity, and the number of queries.
Then follow $q$ lines, each containing two integers $x, y$, representing the two nodes in the query.

Output Format

Output $q$ lines, each containing one integer, the length of the shortest path between node $x$ and node $y$.

7 2 3
1 2
2 1
4 7

1
1
4

9 3 3
8 9
5 7
8 4

2
2
3

Hint

[Sample 1 Explanation]

The figure below shows the tree constructed in sample 1:

It is easy to see that for the $1$st and $2$nd queries, since node $2$ is a child of node $1$, the shortest path length between these two nodes is exactly $1$. For the $3$rd query, one shortest path is $4\rightarrow 2\rightarrow 1\rightarrow 3\rightarrow 7$. Therefore, the shortest path length is $4$.

[Sample 2 Explanation]

The tree constructed in sample 2 can be found in the “Description” section.

[Constraints]

For $20\%$ of the testdata, $1\leqslant n, q\leqslant 1000$ is guaranteed.
For $50\%$ of the testdata, $1\leqslant n\leqslant 10^5$ is guaranteed.
For all testdata, $1\leqslant n\leqslant 10^{15}$, $1\leqslant k\leqslant 1000$, $1\leqslant q\leqslant 10^5$.

[Source]

This problem comes from COCI 2015-2016 CONTEST 4 T4 CHEWBACCA. Using the original problem’s data configuration, the full score is $120$ points.

Translated and organized by Eason_AC.

Translated by ChatGPT 5