まず、この問題を解くための最初のポイントは 操作を繰り返したときに発生する状態数が少ない という点です。具体的には、発生する状態の個数は「高橋君が頂点 \(1\) ~ 頂点 \(N\) のどの頂点にいるか」\(\times\)「青木君が頂点 \(1\) ~ 頂点 \(N\) のどの頂点にいるか」の \(N \times N \leq 4 \times 10^6\) 通りで抑えられます。
このように取り得る状態数が十分小さいのを利用すると、最短路アルゴリズムにより最小の操作回数を求めるというアプローチを適用できます。グラフ \(G'\) を、状態を頂点として, 状態 \(u\) から状態 \(v\) へ遷移できるときに \(u \to v\) が辺を貼られたグラフとします。すると、最小の操作回数は、 初期状態に対応する頂点から終了状態に対応する頂点への \(G'\) 上の最短経路の長さと一致します。よって答えを BFS で \(\mathrm{O}(G' の頂点数 + 辺数)\) で計算できます。

• ここまでの考察は ABC235 D, ABC272 D などの類題が過去に出題されています。理解や練習にお使いください。

この問題のもう 1 つのポイントは計算量解析です。\(G'\) の頂点数は前述の通り \(N^2\) 頂点ですが、辺数が \(4M^2\) で抑えられることを以下で説明します。
問題文の入力で与えられるグラフを \(G\) とします。\(G\) の頂点 \(n\) に隣接する頂点からなる列を \(g_n\) と表します。
髙橋君が \(u\) に、青木君が \(v\) にいる状態を考えます。このとき、次の状態として必要な条件は「高橋君が \(u\) に隣接する頂点にいて、青木君が \(v\) に隣接する頂点にいる」というものです。(実際は頂点の色の制約があるため、遷移可能な状態は上の条件を満たす状態の一部です。

よって、\(G'\) の辺数 \(M'\) と \(g_u\) に関して次の式が成り立ちます。

\[ \begin{aligned} M' &\leq \sum_{u=1}^N \sum_{v=1}^N \sum_{x \in g_u} \sum_{y \in g_v} 1 \\ &=\sum_{u=1}^N \sum_{v=1}^N \left(|g_u| |g_v|\right) \end{aligned} \]

右辺を変形していきます。\(|g_u|\) は頂点 \(u\) の \(G\) 上の次数 \(\deg(u)\) と等しいので

\[ \begin{aligned} &=\sum_{u=1}^N \sum_{v=1}^N \left(\deg(u) \deg(v) \right) \end{aligned} \]

と変形出来て、二重和のシグマの順番を入れ替えて、

\[ \begin{aligned} &=\left(\sum_{u=1}^N \deg(u) \right) \left(\sum_{v=1}^N \deg(v) \right)\\ &=\left(\sum_{u=1}^N \deg(u) \right)^2 \end{aligned} \]

になり、\(\sum_{u=1}^N \deg(u) = 2M\) なので(握手の補題)、

\[= 4M^2\]

です。以上より \(M' \leq 4M^2\) であることが確認できました。よって BFS は \(\mathrm{O}(N^2 + M^2)\) で動作して、これは十分高速です。(なお、訪問可能な状態数を評価すると \(N^2/4\) 程度に抑えられることがわかるので、定数倍も軽いです)

Bonus : (上級者向けだと思います) BFS の性質から、答えの最大値は \(G'\) の頂点数, \(N^2\) オーダーであることが確認できます。では、答えが \(\mathrm{\Theta}(N^2)\) になるグラフの構成方法を 1 つ考案してください。