頂点 \(u\) をケンケンパの0歩目, 1歩目, 2歩目の3種類に分ける.

これを \(u_0, u_1, u_2\) とすると, \(u\) から \(v\) へ辺を追加するということは, \(u_0\) から \(v_1\), \(u_1\) から \(v_2\), \(u_2\) から \(v_0\) へ辺をそれぞれ追加するということになる.

あとは dijkstra なりを使って \(S_0\) から \(T_0\) への最短距離を求めて \(3\) で割ればいい.