Zadanie

Krotitelia grafov

Počet bodov: 50

V tomto kole ste sa už stretli s Fibonacciho číslami. Podobný postup vytvárania z posledných dvoch sa dá však aplikovať aj na iné objekty, než len čísla. V tejto úlohe sa pozrieme napríklad na (neoficiálne nazývané) Fibonacciho grafy.

Ako prvý graf označíme graf obsahujúci jediný vrchol s číslom \(0\). Ako druhý označíme graf s dvomi spojenými vrcholmi s číslami \(0\) a \(1\). Každý ďalší graf skonštruujeme z predošlých dvoch. Konkrétne \(N\)-tý nasledovne:

1. Vezmeme \((N-1)\)-vý a \((N-2)\)-hý graf a vrcholy s rovnakým číslom spojíme hranou

2. K číslam vrcholov pochádzajúcich z \((N-2)\)-hého grafu pripočítame \((N-1)\)-vé Fibonacciho číslo (rozmyslite si, že týmto zaručíme, že pre každé číslo od \(0\) po \(F_N - 1\) budeme mať práve jeden vrchol s týmto číslom).

Pre potreby tejto úlohy určíme prvé dve Fibonacciho čísla nasledovne: \(F_1 = 1\) a \(F_2 = 2\).

Vašou úlohou bude zistiť, aká je najkratšia cesta medzi dvojicou vrcholov v niektorom Fibonacciho grafe.

Vstup a výstup

Vstup pozostáva z dvoch riadkov. Na prvom je číslo \(N\), \((N \leq 1000)\) označujúce, koľký graf berieme. Na druhom riadku vstupu dostanete dve čísla \(a\) a \(b\), \((0 \leq a, b < F_N)\).

Aspoň 30 bodov môžete získať za riešenie, ktoré stihne v časovom limite spracovať tie vstupy, v ktorých bude mať graf nanajvýš \(10^6\) vrcholov.

Pozor, čísla vyskytujúce sa vo vstupoch tejto úlohy budú veľké a nezmestia sa do bežných \(32\) a \(64\)-bitových premenných.

Príklad

Input:

5
4 7

Output:

4

Input:

29
100000 200000

Output:

10

Toto je príklad najväčšieho grafu s menej ako \(10^6\) vrcholmi.