\(a\) と \(b\) の距離を \(d\) とします。実は、\(d\) が奇数ならAlice、 偶数ならBobが勝利します。

\(d\) が奇数の場合について説明します。まず、Alice は、Bobと同じ頂点に到達するまで、Bobの方向へ進みます。距離の頂点の偶奇を考えると、これは必ず可能です。

Alice が Bob と同じ頂点に到達した後は、Alice は Bob の動きを模倣すれば良いです。これらの動きを考えると、結局のところBobがどのように動いたとしてもAliceはゲームに勝利することができます。

\(d\) が偶数の場合も同様で、Alice を Bob に置き換えて同じ戦術を取ることで、Bob は必ず勝利することができます。よって、この問題を \(O(N)\) などで解くことができました。