本題考驗基本迴圈和運算處理能力，只要照著題目敘述提供的步驟做計算，並利用 std::map 等工具紀錄數字已經出現與否，就可以在 $O(步驟數\log(步驟數))$ 的時間內找到循環的第一個數字。由於題目保證總步驟數不超過 $10^5$，故可以在時間內通過。
實作上需要小心題目輸入的數字可能沒有前導零，筆者這裡建議選手多注意輸入格式來迴避這個可能的陷阱。
本題存在一個透過電腦爆搜後得出的特殊性質：對於 $d\leq 10$，所有的數字都至多只需要花上 $27$ 步就可以進入循環，因此在檢查數字出現與否時，暴力花費 $O(步驟數)$ 來一一比對也可以在時間內通過本題。
我們可以將問題先轉化成計算「奇數個 $1$ 的 $k\times k$ 子矩陣個數」，注意到當 $k$ 為偶數時，該計算出來的值即為答案；當 $k$ 為奇數時，所有的 $k\times k$ 子矩陣減去該計算出來的值即為答案。
由於所有 $1$ 皆在同一列，當 $m, n \leq 10^5$ 時，我們可以窮舉所有長度為 $k$ 的欄區間，並直接維護該區間內 $1$ 個數的奇偶性。當找到一個擁有奇數個 $1$ 的區間時，透過簡單的列式就可以 $O(1)$ 得出有哪些長度為 $k$ 的列區間包含這些 $1$ 來貢獻進答案內。
當 $m, n$ 大至 $10^9$ 時，想像長度 $k$ 的欄區間從左掃到右，途中會至多 $2t$ 個「有 $1$ 進入或離開區間」的事件，對於相鄰的兩個事件，區間內 $1$ 的個數是不會改變的，只要該個數為奇數，就可以將前一段的列式乘上這兩個事件的距離同樣在 $O(1)$ 得出該次答案的貢獻。對於時間複雜度，該演算法在花費 $O(t\log t)$ 對事件進行排序後，可以在 $O(t)$ 的時間內完成計算。
當我們僅需要考慮最大步法使用次數最多時，可以定出以下狀態：dp[i]=v，其中：
對於轉移，我們能簡單的窮舉可用步法，去看可以從哪個非坑洞座標跳到 $i$，總時間複雜度便為 $O((e-n)\times k)\leq 3\times 10^5$。
這裡的做法意外的單純，我們使用同樣的狀態長相：dp[i]=v，但對於 $v$，我們將其定義為一個長度為 $k$ 的陣列，其中 v[i] 的值代表著第 $i$ 種步伐的使用次數。
如此一來，貿然進行相同的轉移手段確實能得出解答，但想像上的時間複雜度為 $O((e-n)\times k^2)$，這裡存在兩種優化方式：
注意到落腳在 $i$ 時，至多只有 $O(\sqrt{i})$ 種使用到的步法種類，利用 std::vector 等資料結構儲存並進行字典序比較，就可以在 $O((e-n)\times k\times \sqrt{e})$ 的時間內通過本題。
實際上，只要在轉移時忽略那些會轉移到坑洞處的步法，總時間複雜度就會是 $O((e-n)\times \min(e-n, k)\times k)$，由於 $\min(e-n, k)\leq \sqrt{3\times 10^5}$，因此能在合理的時間內通過本題。
至於該時間複雜度是怎麼得出的呢？上述演算法的花費時間為轉移次數乘上 $k$，也就是說我們宣稱總共的轉移次數只有 $O((e-n)\times \min(e-n, k))$，而這是一個很自然的結論：對於一個非坑洞處，合法的轉移次數會同時被其他非坑洞處的個數 $e-n$、以及步法數 $k$ 限制住。
該方法也是修改起來最為單純又容易忽略其時間複雜度正確性的做法。
以上提到的演算法都需要在最後回溯出 dp 最佳解的轉移過程，一個簡單的實作方法便是直接對每個狀態再紀錄一個當前最佳解的轉移來源，就可以從最終解答一路查表回到初始狀態。
實際上，可以利用一些雜湊技巧搭配線段樹等資料結構來維護每個 dp[i] 的步法使用次數，並讓兩種步法次數的大小關係在資料結構上二分搜「最長共同前綴」來在 $O(\log k)$ 的時間內完成比較，總時間複雜度可以進一步優化到 $O((e-n)\times k\log k)$，但由於該演算法常數較大，在一般範圍下不太能與前述的演算法分出勝負。
對於一棵有根樹，對根執行深度優先搜尋遍歷整棵樹時，可以得到每個點的「進入時間 dfs_in[u]」和「離開時間 dfs_out[u]」，我們稱之為時間戳記。
對於兩個點 $u, v$，$u$ 為 $v$ 的祖先若且唯若
dfs_in[u] <= dfs_in[v] && dfs_in[v] <= dfs_out[u]這裡我們為求方便，定義節點自身同為該節點的祖先。
原題退化為「計算在其中一棵樹互為祖先關係、另一棵樹不互為祖先關係」的節點對個數，我們不失一般性只計算「在第一棵樹互為祖先關係、第二棵樹不互為祖先關係」的節點對個數。
我們試圖在第一棵樹上進行深度優先搜尋，在遍歷到其中一個節點 $u$ 時，我們需要計算他有多少祖先在第二棵樹不互為祖先關係，而這其實就是對第二棵樹處理出時間戳記後，寬鬆的當成以下問題。
[dfs_in[u], dfs_out[u]] 和 [dfs_in[v], dfs_out[v]] 沒有交集。同時等價計算
dfs_out[v] < dfs_in[u] $v$ 的數量，加上dfs_in[v] > dfs_out[u] $v$ 的數量對於該問題，我們可以直接將其視為一資料結構問題，遍歷到一個節點時即為一詢問操作、並接著進行資料結構的修改操作來讓接下來遍歷的子樹可以獲得該節點的貢獻，離開時再進行撤銷操作即可。
以上資料結構問題可以簡單的利用 Fenwick Tree 搭配時間戳記 dfs_in 的順序來在 $O(\log n)$ 的時間內完成每一項操作，總時間複雜度為 $O(n\log n)$。
本題存在不只一種滿分做法，這裡只提供最為單純又乾淨的做法。
首先我們可以忽略所有距離根節點 $<k$ 步的節點，這些節點跟其他節點的祖先關係距離會直接被到根節點的距離限制住，因此不會貢獻進答案內。
對於沒被忽略的節點們，可以觀察到，令 $u$ 往上 $k$ 步的祖先為 $kf_u$，$u$ 與 $v$ 的祖先關係距離 $> k$ 若且唯若
因此，將 $k=0$ 的演算法全部改針對 $kf_u$ 去進行操作後，即可得到同樣的 $O(n\log n)$ 演算法。
本題若不花一點心思實作，會得到很可怕的實作量，由於兩棵樹需要計算的東西是對稱的，將計算演算法包成函式後，用不同的順序傳入兩棵樹即可以直接省下一半的實作量。諸如此類的方法可以節省大量的實作，並在 debug 時迴避只為了解決單一邏輯、卻需要同時修改多處的狀況。
注意：本題有著 $m\leq 2n-4$ 的特殊限制。
考慮分配完的三個節點群，這三個節點群之間的邊不能有環同時也等價這些邊會形成一個森林。
透過子任務，我們可以取得有效的提示：考慮隨意一個生成樹，該生成樹會使用 $n-1$ 條邊來獲得一個沒有環的圖，此時至多剩下 $n-3$ 條邊。而當我們只考慮這 $n-3$ 條邊時，可以觀察到至少會有三個連通塊，因此，直接取三個連通塊分成三群（其他的點可以隨意全部塞進其中一群），就可以消除掉這 $n-3$ 條邊，留下不會形成環的 $n-1$ 條邊。
不過，上述理論存在一個細小的漏洞：當圖不連通時，我們是找不到生成樹的，這也是子任務二存在的理由。
若整張圖的連通塊超過兩個，可以直接根據連通塊進行分群來消除所有邊；若連通塊恰為兩個，可以任取其中一個有超過兩個點的連通塊，將單一一個點拆出來當做第三群並結束分群，這是因為整張圖沒有重邊，也因此不會形成任何環。
若忽略了不連通的 case，直接實作尋找生成樹的演算法的話，使用深度優先搜尋所找到的生成樹會在只有兩個連通塊的時候構造錯誤；但如果使用廣度優先搜尋來找出生成樹，其實可以直接獲得一個正確的做法。正確性留給讀者自行思考。
實際上可以證明必定存在大小為 $1, 1, n-2$ 的分群方法，因此可以窮舉大小為 $1$ 的兩個點、透過驗證剩下的邊是否有形成環來在 $O(n^3)$ 的時間內通過子任務三。
這裡將證明留給讀者自行練習，若證明的手法夠巧妙，也可以直接獲得 $O(n)$ 的構造演算法來直接得出大小為 $1, 1, n-2$ 的分群方法並通過本題。