通るルートは \(C,A_1A_2,\cdots,A_K,D,B_1B_2,\cdots,B_L,C\) と表すことができます。

\(A, B\)はそれぞれ重複する要素を持たないことがわかります。

また、\(A, B\)には\(C, D\)が現れないので\(K,L \leq N-2\)です。

そのため\(A,B\)それぞれで\((N-2)!\)通りのルートを構築し、ありうるかの判定をすれば良いです。

\((N-2)!^2\)は最大で\(720 \times 720 = 518400\)ですが、\(D\) を挿入する位置を考慮する必要があるため、最大で\(8 \times 8 \times 518400 = 33177600\)通りを確認することになりますが、適切に枝刈りすることで間に合わせることができます。

解答例(C#): https://atcoder.jp/contests/yuha-c88/submissions/21845168