公式解説の

\(d_u+1-d_v \not\equiv 0 \pmod a\) を満たす辺をちょうど \(1\) つだけ含むような(引用者注：頂点 \(1\) を含む)サイクルを \(1\) つ取り、

が非自明だと感じたので自分用に補足しておきます。

「\(d_u+1-d_v \not\equiv 0 \pmod a\) を満たす辺 \((u,v)\)」は長いので、以下単に「条件を満たす辺」と呼びます。

示すべきことは、「条件を満たす辺が存在するとき、頂点 \(1\) を含むサイクルであって、条件を満たす辺をちょうど \(1\) つ含むようなものが存在する」です。

条件を満たす辺を任意の \(1\) つとり \(e=(u,v)\) とします。グラフは強連結であることから、パス \(1\to u\)、辺 \(e\)、パス \(v\to 1\) をこの順につなげることで、辺 \(e\) と頂点 \(1\) を含むサイクル \(C\) がとれます。

（パス \(1\to u\) は\(d_*\) の定義から条件を満たす辺を含まないように取ることができますが、パス \(v\to 1\) はそうとは限らないので、\(C\) が \(e\) の他に条件を満たす辺を含まないように取れるとは限りません）

\(C\) に含まれる条件を満たす辺 \(e'=(u',v')\) であって、「\(C\) において、\(e'\) を通ったあと頂点 \(1\) に着くまで条件を満たす他の辺を通らない」ものを任意に \(1\) つとります。

（\(C\) は条件を満たす辺を \(1\) つ以上含んでいるので、頂点 \(1\) から\(C\) を逆に辿っていくことでこのような \(e'\) は必ずとれます）

これにより、パス \(v'\to 1\) であって、条件を満たす辺を \(1\) つも含まないものがとれます。また \(d_*\) の定義から、パス \(1\to u'\) であって、条件を満たす辺を \(1\) つも含まないものが存在します。よってこのパス \(1\to u'\)、辺 \(e'\)、パス \(v'\to 1\) をこの順につなげることで、頂点 \(1\) を含むサイクルであって、条件を満たす辺をちょうど \(1\) つ含むサイクルを構成できます。