{"raw_statement":[{"iden":"statement","content":"On the magical land Byteland, there is an ancient kingdom called Fibonacci Kingdom.\n\nThere are $n$ cities in the kingdom(numbered from $1$ to $n$), and $\"Fib\"_i$ residents in the $i$-th city.\n\n$\"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$.\n\nUnfortunately, one day, an earthquake occurred. \n\nThe earthquake destroyed the whole kingdom's transportation system.\n\nTo deliver disaster relief supplies, the king decided to reconstruct the road. \n\n$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)$. \n\nThe magic is that it takes exactly $\"Fib\"_(x_i) + \"Fib\"_(y_i)$ bitcoins to reconstruct the road $(x_i, y_i)$. \n\nThe king wants to choose some plans to implement, but the rules below must be followed: \n\nSetsuna, 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.\n\nIt's guaranteed that the answer always exists. \n\nThe 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))$.\n\nThe $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)$.\n\nOutput one integer which indicates the minimum $D$ Setsuna can get.\n\nThe graph of the sample is as follows. \n\nIn 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$.\n\nIt can be proved that such solution is the best, so the answer is $3$.\n\n"},{"iden":"input","content":"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)$."},{"iden":"output","content":"Output one integer which indicates the minimum $D$ Setsuna can get."},{"iden":"note","content":"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$."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ D \\in \\mathbb{Z}^+ $ be the target charge on the final day.  \nLet $ m \\in \\mathbb{Z}^+ $ be the minimum number of days required.  \nLet $ 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\\} $:  \n$$ c_{i+1} \\in \\{ 2c_i,\\ 3c_i,\\ c_i + 1 \\} $$  \nand $ c_m = D $.\n\n**Constraints**  \n1. $ 1 \\leq T \\leq 10^5 $  \n2. $ 1 \\leq D \\leq 10^6 $  \n\n**Objective**  \nFor each test case, find the minimal $ m $ and any valid sequence $ c $ such that:  \n- $ c_1 = 1 $,  \n- $ c_m = D $,  \n- Each transition satisfies $ c_{i+1} \\in \\{ 2c_i, 3c_i, c_i + 1 \\} $,  \n- $ m $ is minimized.","simple_statement":"You start with Rs. 1 on day 1.  \nEach next day, you can either:  \n- double the previous day’s charge,  \n- triple it, or  \n- add 1 to it.  \n\nGiven a target amount D, find the **minimum number of days** needed to reach exactly D on the last day.  \nAlso, output **any valid sequence** of charges for those days.","has_page_source":false}