C. Дое Графууд

хугацааны хязгаарлалт 3 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Жон Дое зарим математикийн обьектууд түүний нэртэй байх ёстой гэж шийджээ. Ингээд тэр Дое графийг зохиосон. Дое граф чиглэлгүй графын бүлд хамаарах ба энэ төрлийн граф тус бүр нь түүний зэрэг болох нэг ширхэг эерэг тоогоор тодорхойлогдоно.

Бид $k$ зэрэгтэй графыг $D(k)$ гэж тэмдэглэх ба $D(k)$ граф дахь оройнуудын тоог $|D(k)|$ гэж тэмдэглэнэ. Ингээд Доеийн графыг дараах байдлаар тодорхойлье:

  • $D(0)$ нь нэг оройгоос бүрдэх ба оройн дугаар нь $1$.
  • $D(1)$ нь хоёр оройгоос бүрдэх ба дугаарууд нь $1$ ба $2$ бөгөөд хоорондоо ирмэгээр холбогдсон.
  • $n ≥ 2$ байх $D(n)$ графыг $D(n - 1)$ болон $D(n - 2)$ графуудаас гаргаж авна. $D(n - 1)$ ба $D(n - 2)$-г нэг граф болгож нэгтгэх ба $D(n - 2)$ графийн бүх оройнуудын дугаар нь $|D(n - 1)|$-аар нэмэгдэнэ (жишээлбэл $D(n - 2)$ графийн $1$ дугаартай орой нь $1 + |D(n - 1)|$ дугаартай болох юм). Үүний дараа графд хоёр ирмэг нэмэгдэнэ: эхний ирмэг нь $|D(n - 1)|$ ба $|D(n - 1)| + 1$ дугаартай оройнуудыг холбоно, хоёр дахь ирмэг нь $|D(n - 1)| + 1$ ба $1$ дугаартай оройнуудыг холбоно. Зурагт зүүнээс баруун тийш 1,2,3,4 зэрэгтэй Дое графуудыг үзүүлсэн байна.

Жон бодохдоо Хамилтоны замын хайлтад зориулсан олон гишүүнт алгоритм Док графуудад оршин байгаа учраас графууд гайхалтай гэж бодсон. Гэсэн ч таны ажил бол $D(n)$ граф дахь $a_{i}$ ба $b_{i}$ оройнуудын хоорондох хамгийн богино замуудыг олох асуулгуудад хариулах юм.

Граф дахь $u$ ба $v$ хос оройн хоорондох зам нь $x_{1} = u$, $x_{k} = v$ болон дурын $i$ $(i < k)$-н хувьд $x_{i}$ ба $x_{i + 1}$ оройнууд нь ирмэгээр холбогдсон байх $x_{1}$, $x_{2}$, $...$, $x_{k}$ $(k > 1)$ оройнуудын дараалал юм. $x_{1}$, $x_{2}$, $...$, $x_{k}$ замын урт нь $(k - 1)$ байна.

Оролт

Эхний мөрөнд хоёр бүхэл тоо $t$ ба $n$ ($1 ≤ t ≤ 10^{5}; 1 ≤ n ≤ 10^{3}$) байх ба өгөгдсөн графын асуулгуудын тоо болон зэрэг байна. Дараагийн $t$ мөрүүдийн $i$-р мөрөнд хоёр бүхэл тоо $a_{i}$ ба $b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ 10^{16}$, $a_{i} ≠ b_{i}$) байх буюу $i$-р асуулгын хоёр оройн дугаар юм. $a_{i}, b_{i} ≤ |D(n)|$ байна.

C++ хэлэнд 64 битийн бүхэл тонуудыг унших болон бичихдээ $\%lld$ тодорхойлогчийг битгий ашиглаарай. $cin$, $cout$ урсгалууд болон $\%I64d$ тодорхойлогчийг ашиглаарай.

Гаралт

Асуулга бүрийн хувьд нэг мөрөнд нэг бүхэл тоо хэвлэх ба энэ нь $a_{i}$ ба $b_{i}$ оройнуудын хоорондох хамгийн богино замын урт юм. Асуулгуудын хариултыг тэдгээрийн оролтонд өгсөн дарааллаар хэвлэ.

Орчуулсан: Г.Мэндбаяр

Жишээ тэстүүд

Оролт
10 5
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5
Гаралт
1
1
1
2
1
2
3
1
2
1
Сэтгэгдлүүдийг ачааллаж байна...