首先，将一个斐波那契数写成两个斐波那契数之和的方案是唯一的。

并且不难发现将一棵大小为斐波那契数的数划分为两个大小为斐波那契数的子树，最多只有两种方案。

我们来证明，如果 Fib-tree 有两种划分方案，那么这两种划分方案都可以划出两个 Fib-tree 来，也即我们可以任意决策。

考察其中一种能够划出两个 Fib-tree 的划分方案，称两个子树中较大者为 $A$，较小者为 $B$，显然另一种方案中，断开的边落在 $A$ 中，并且 $A$ 照这条边断开后仍然能形成两个 Fib-tree，所以原树按照这条边断开后亦能形成两个 Fib-tree。得证。

所以暴力寻找要割开的边即可。

令 $a_i=\prod_{j=1}^iA_j$，那么条件转化为

• $a_i\in[0,m)$
• 对于 $i\not=j$ 有 $a_i\not=a_j$
• $a_i\not\in B$
• $\gcd(a_{i-1},m)\mid a_i$

朴素的想法是对 $[0,m)\backslash B$ 中所有满足 $\gcd(x,m)\mid y$ 的 $x$ 向 $y$ 连边，那么图上的最长链长度即为答案。

但是图上有环，难以处理。不过不难发现 $x,y$ 在同一环中当且仅当 $\gcd(x,m)=\gcd(y,m)$。也就是说如果能取 $x$，那么一定能取 $\gcd(y,m)=x$ 的所有 $y\not\in B$。

所以我们将所有 $x$ 按照 $\gcd(x,m)$ 划分等价类建图，在 DAG 上 DP 即可。