All submissions for this problem are available.
lakshmi8 and ara46rossi are friends. Recently lakshmi8 solved a problem named "k-Tree". lakshmi8 suggested ara46rossi to solve that problem. Being a very good programmer, ara46rossi solved that problem very efficiently than lakshmi8. Now, lakshmi8 decides to challenge ara46rossi with a newer version of that problem, "Given a k-Tree with 'n' nodes. k-Tree is a rooted tree (The first node is always the root) in which each node can have atmost 'k' children. The nodes are labelled as integers from 1 to n with '1' being the first node. This k-Tree is complete, in the sense that every level before the current level is completely filled and the current level is filled from left to right. You are given 'q' queries. Each query has two integer 'x' and 'y'. You have to find the length of the shortest path between node 'x' and node 'y'. Length is measured in terms of number of edges". Now, assume you are ara46rossi. Accept lakshmi8's challenge and solve this problem.
The first line consists of two integers 'n' and 'k', denoting the number of nodes in the tree and the 'k' in the k-tree
The second line consists of 'q', the number of queries.
Next q lines consists of two integers 'x' and 'y' for which you have to find the length of the shortest path.
For ith query, print in a separate line the length of the shortest path between xi and yi.
2 <= n <= 10^15
1 <= k <= 10^3
1 <= q <= 10^5
1 <= x, y <= n, x != y
Input: 7 2 4 1 2 5 6 2 3 3 4 Output: 1 4 2 3
|Time Limit:||0.5 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, SCM chicken, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.