AT_ijpc_imo 国際道迷いオリンピック(International Michimayoi Olympic)

**感兴趣的建议直接去看原题面** Time Limit: 1 sec / Memory Limit: 256 MB 今日, 急激に経済発展している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とは, 「国際道迷いオリンピック」というスラングのことで, 本文中では「国際大会で迷子になる」と解釈する.

[problemUrl]: https://atcoder.jp/contests/ijpc2012-2/tasks/ijpc_imo

无

无

由 ChatGPT 4.1 翻译