2020 年 “联想杯”全国高校程序设计在线邀请赛暨第三届上海理工大学程序设计竞赛

On the magical land Byteland, there is an ancient kingdom called Fibonacci Kingdom.

There are $n$ cities in the kingdom(numbered from $1$ to $n$), and $\text{Fib}_i$ residents in the $i$-th city.

$\text{Fib}_i$ denotes the $i$-th number of Fibonacci sequence, such that each number is the sum of the two preceding ones, starting from $1$ and $1$. That is, $\text{Fib}_0=1,\text{Fib}_1=1$ and $\text{Fib}_n=\text{Fib}_{n-1}+\text{Fib}_{n-2}$ for $n>1$. The beginning of the sequence is thus: $1,1,2,3,5,8,13,21,34,55,89,144,\cdots$.

Unfortunately, one day, an earthquake occurred.

The earthquake destroyed the whole kingdom’s transportation system.

To deliver disaster relief supplies, the king decided to reconstruct the road.

$m$ plans have been proposed, and the $i$-th plan is to reconstruct the bidirectional road linking $x_i$ and $y_i$, denoted as $(x_i,y_i)$.

The magic is that it takes exactly $\text{Fib}_{x_i}+\text{Fib}_{y_i}$ bitcoins to reconstruct the road $(x_i,y_i)$.

The king wants to choose some plans to implement, but the rules below must be followed:

1. After the reconstruction, the cities are mutually reachable (i.e., there is at least one path connecting any two cities).
2. Minimize the bitcoin consumption.
3. In the premise of the least bitcoin consumption, the largest degree $D$ among all the cities should be minimized(suppose $d_i$ is the degree of $i$-th city, $D=\max\limits_{1\leq i \leq n} d_i$), because the residents of the kingdom are not good at looking for ways. The definition of the degree of a city is the number of roads directly connected to the city.

Setsuna, the savior of the kingdom, has easily calculated the minimum consumption of bitcoin, but she desperately wants to know the minimum $D$ she can get after reconstruction.

It’s guaranteed that the answer always exists.