今日, 急激に経済発展しているK国で国際情報オリンピックが開かれることになった. K国では既に国際数学オリンピックが開催されていたのだが, その時は大会期間中にK国側のミスによって選手が乗ったバスをIMO[1]させてしまった. 選手を二度もIMOさせることは開催国として恥ずかしいことなので, 国際情報オリンピックでは絶対に選手をIMOさせないために対策を練ることになった.
K国では国際情報オリンピックに使用する土地として N 個の都市を使用する. N 個の都市は M 本の道で結ばれており, それらの道は両方向に通行可能である. どの道も異なる2つの都市を結んでおり, 道同士が都市以外の地点で交わることはない. また, K国の都市は全て数字で管理されている.
過去にIMOさせた原因を調査した結果, バスの移動中に運転手が都市の数字を読み間違えたことが原因であることが分かった. そのため今回の大会では読み間違いを少なくするため, 都市の番号をある程度わかりやすい順にして運転中にチェックしやすくなるようにすることにした. 具体的にはバスが巡ることが可能な経路, つまり幾つかの道を辿って都市をめぐる経路における, 経路上の都市の番号は常に単調増加または単調減少になるようにすることである. 大会のスケジュールは未定なのでバスの経路は全て考えなければならない. ただしバスの経路として同じ都市を複数回巡る経路は考えない. この条件を満たしたK国の状態を「良いK国の状態」と呼ぶことにする. バスの経路が存在しない場合もK国は「良いK国の状態」である.
しかし, 都市の番号は国民が慣れ親しんだものなので容易に変えることはできない. 議会での度重なる討論の結果, 1日に1回, ある1本の道上の2都市間の数字を入れ替えることのみが認められることになった. 大会開催までにはあまり時間がないので, できるだけ短い日数で「良いK国の状態」にしなければならない.
なお, この文章は事実を基にしたフィクションであり, K国は代表選手が友好的なあの国のことではない.
[1] IMOとは, 「国際道迷いオリンピック」というスラングのことで, 本文中では「国際大会で迷子になる」と解釈する.
都市と道の情報が与えられたとき, 道の両端の都市の番号を入れ替える操作を繰り返して, どの単純な経路もその経路上の都市の番号が昇順または降順である状態にするのに必要な操作回数 ( K国を「良いK国の状態」にするために必要な日数 ) の最小値を計算せよ.
次のパラメータをもつプロシージャ best_swap(N,M,E) を実装せよ:
best_swap(N,M,E) は必要な操作回数の最小値を返さなければならない. どのように交換してもK国が条件を満たすことができない場合は -1 を返す必要がある.
例として N = 3, M = 2,
| E = | 0 | 2 | |
| 1 | 2 |
の場合を考える. この場合, 都市 1 と都市 2 の番号を入れ替えることで「良いK国の状態」になるので best_swap(N,M,E) は 1 を返す必要がある.
例として N = 3, M = 3,
| E = | 0 | 1 | |
| 1 | 2 | ||
| 0 | 2 |
の場合を考える. この場合, どのように交換しても 0,2,1 と巡る経路が存在するため, K国は「良いK国の状態」になることができない. よって best_swap(N,M,E) は -1 を返す必要がある.
例として N = 6, M = 8,
| E = | 0 | 1 | |
| 3 | 2 | ||
| 1 | 2 | ||
| 4 | 5 | ||
| 5 | 2 | ||
| 3 | 0 | ||
| 2 | 4 | ||
| 5 | 4 |
の場合を考える. この場合も best_swap(N,M,E) は -1 を返す必要がある.