在一個 n×n 的棋盤上，王子和公主玩一個遊戲。棋盤上的方格按如下方式編號為 1, 2, 3, ... , n * n，如下所示：

王子站在第1個方格，跳p次後最終到達第nn個方格。他最多只能進入每個方格一次。所以如果用xp來表示他進入的第p個方格，那麼x1, x2, …, xp+1都是不同的數字。注意，x1=1且xp+1=nn。公主做類似的事情——站在第1個方格，跳q次後最終到達第n*n個方格。我們用y1, y2, …, yq+1來表示這個序列，所有這q+1個數字都是不同的。

下圖顯示了一個3×3的方格，王子的可能路徑以及公主的不同路徑。

王子沿著以下序列移動：1 → 7 → 5 → 4 → 8 → 3 → 9（黑色箭頭），而公主沿著這個序列移動：1 → 4 → 3 → 5 → 6 → 2 → 8 → 9（白色箭頭）。

國王——他們的父親，剛剛來到。“為什麼要分開走呢？你們是兄妹！”國王說，“忽略一些跳躍，確保你們總是一起走。”

例如，如果王子忽略他的第2、第3、第6次跳躍，他將按照以下路線走：1 → 4 → 8 → 9。如果公主忽略她的第3、第4、第5、第6次跳躍，她也將按照相同的路線走：1 → 4 → 8 → 9（如圖3所示）。這樣就滿足了國王的要求。國王想知道他們可以一起走的最長路徑是什麼，你能告訴他嗎？