All submissions for this problem are available.
Robin Paul invented a series of undirected graphs ,each given a single positive number -its order.He named them as Paul graphs.
A graph of order n will be denoted as P(n), and the number of vertices in the graph P(n) as |P(n)|. Then let's define the Paul graphs as follows:
P(0) consists of a single vertex, that has number 1.
P(1) consists of two vertices with numbers 1 and 2, connected by an edge.
P(m) for m ≥ 2 is obtained from graphs P(m - 1) and P(m - 2). P(m - 1) and P(m - 2) are joined in one graph, at that numbers of all vertices of graph P(m - 2) increase by |P(m - 1)| (for example, vertex number 1 of graph P(m - 2) becomes vertex number 1 + |P(m - 1)|). After that two edges are added to the graph: the first one goes between vertices with numbers |P(m - 1)| and |P(m - 1)| + 1, the second one goes between vertices with numbers |P(m - 1)| + 1 and 1. Note that the definition of graph
P(n) implies, that P(n) is a connected graph, its vertices are numbered from 1 to |P(n)|.
Robin thinks Paul graphs are that great because for them exists a polynomial algorithm for the search of Hamiltonian path. However, your task is to answer testcases of finding the shortest-length path between the vertices ui and vi in the graph P(m).
A path between a pair of vertices x and y in the graph is a sequence of vertices a1, a2, ..., ak (k > 1) such, that a1 = x, ak = y, and for any i (i < k) vertices ai and ai + 1 are connected by a graph edge. The length of path a1, a2, ..., ak is number (k - 1).
First line has two integers t (number of test cases)and n(order of the graph).The i-th of the next t lines contains two integers ui and vi - numbers of two vertices in the i-th test case. It is guaranteed that ui, vi ≤ |P(n)|.
Prefer %I64d specifier to %lld specifier to read/write 64 bit integers in C++.
1 ≤ t ≤ 100;
1 ≤ n ≤ 100
1 ≤ ui, vi ≤ 100000, ui ≠ vi
For each Test case print the length of the shortest path between vertices ui and vi.
Sample Test Case:
|Time Limit:||3 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP 4.3.2, CPP14, GO|
Fetching successful submissions
If you are still having problems, see a sample solution here.