Fibonacci Tour

Image by Maklay62

Charles is traveling to the fantastic Fibonacci City. The city has $n$ mansions of various heights and $m$ bi-directional roads connecting the mansions. One of the most exciting tourist attraction in the city is the Fibonacci Tour, which is a simple path visiting a sequence of distinct mansions, so that every pair of consecutively visited mansions are directly connected by a road, and the heights of the mansions in the path form a continuous subsequence of the Fibonacci sequence:

\[ 1, 1, 2, 3, 5, 8, \dots \]

Each number in the Fibonacci sequence equals the sum of the previous two numbers, except for the first two numbers which are defined to be one.

Charles will be happier if his tour is longer. What is the maximum length of a Fibonacci Tour he can take? The length of a tour is the number of mansions visited in the tour. Charles can start the tour at any mansion.


The first line has two integers $n$ ($1\leq n\leq 10^5$) and $m$ ($0\leq m\leq 10^5$), giving the number of mansions and the number of roads in the city. The next line has $n$ positive integers no larger than $10^{18}$. The $i$-th integer gives the height of mansion $i$. The next $m$ lines each has two integers $a$ and $b$ ($1\leq a, b \leq n$, $a \neq b$), indicating that there is a bi-directional road between mansion $a$ and mansion $b$. Each pair of mansions is directly connected by at most one road.


Output the length of the longest Fibonacci Tour Charles can take in the city. If there is no tour Charles can take, output zero.

Sample Input 1 Sample Output 1
5 6
1 3 2 1 5
1 3
2 3
1 4
3 5
4 5
2 5
Sample Input 2 Sample Output 2
4 3
4 4 8 12
1 2
2 3
3 4
Sample Input 3 Sample Output 3
3 3
6 6 6
1 2
1 3
2 3
CPU Time limit 1 second
Memory limit 1024 MB
Difficulty 5.5hard
Statistics Show
License Creative Commons License (cc by-sa)

Please log in to submit a solution to this problem

Log in