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 $"Fib"_i$ residents in the $i$-th city.
$"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, $"Fib"_0 = 1, "Fib"_1 = 1$ and $"Fib"_n = "Fib"_(n -1) + "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 $"Fib"_(x_i) + "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:
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.
The first line contains two integers $n, m (2 <= n <= 10^5, n -1 <= m <= min (frac(n times (n -1), 2), 2 times 10^5))$.
The $i$-th of the next $m$ lines contains two integers $x_i, y_i (1 <= x_i, y_i <= n, x_i eq.not y_i)$.
Output one integer which indicates the minimum $D$ Setsuna can get.
The graph of the sample is as follows.
In this situation, bitcoin consumption is $3 + 4 + 7 + 9 = 23$. The degree of city $1$ is $3$; the degree of city $2$ is $2$; the degree of city $3, 4, 5$ is $1$.
It can be proved that such solution is the best, so the answer is $3$.
## Input
The first line contains two integers $n, m (2 <= n <= 10^5, n -1 <= m <= min (frac(n times (n -1), 2), 2 times 10^5))$.The $i$-th of the next $m$ lines contains two integers $x_i, y_i (1 <= x_i, y_i <= n, x_i eq.not y_i)$.
## Output
Output one integer which indicates the minimum $D$ Setsuna can get.
[samples]
## Note
The graph of the sample is as follows. In this situation, bitcoin consumption is $3 + 4 + 7 + 9 = 23$. The degree of city $1$ is $3$; the degree of city $2$ is $2$; the degree of city $3, 4, 5$ is $1$.It can be proved that such solution is the best, so the answer is $3$.
**Definitions**
Let $ D \in \mathbb{Z}^+ $ be the target charge on the final day.
Let $ m \in \mathbb{Z}^+ $ be the minimum number of days required.
Let $ c = (c_1, c_2, \dots, c_m) $ be a sequence of daily charges, where $ c_1 = 1 $, and for each $ i \in \{1, \dots, m-1\} $:
$$ c_{i+1} \in \{ 2c_i,\ 3c_i,\ c_i + 1 \} $$
and $ c_m = D $.
**Constraints**
1. $ 1 \leq T \leq 10^5 $
2. $ 1 \leq D \leq 10^6 $
**Objective**
For each test case, find the minimal $ m $ and any valid sequence $ c $ such that:
- $ c_1 = 1 $,
- $ c_m = D $,
- Each transition satisfies $ c_{i+1} \in \{ 2c_i, 3c_i, c_i + 1 \} $,
- $ m $ is minimized.