今日, 急激に経済発展している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) を実装せよ:

• N -- 都市の個数. 都市には 0 から N-1 までの番号がつけられている.
• M -- 道の本数. 道には 0 から M-1 までの番号がつけられている. 各々の道は 2 つの異なる都市を結んでおり, 結んでいる都市の対が同じ道が複数存在することもある(14:07 追記)　はどの道についても異なる.
• E -- 道の情報を表す 2 次元配列. 0 ≦ i ＜ M に対し, 道 i は都市 E[i][0] と E[i][1] を結んでいる.

best_swap(N,M,E) は必要な操作回数の最小値を返さなければならない. どのように交換してもK国が条件を満たすことができない場合は -1 を返す必要がある.

例として N = 3, M = 2,

の場合を考える. この場合, 都市 1 と都市 2 の番号を入れ替えることで「良いK国の状態」になるので best_swap(N,M,E) は 1 を返す必要がある.

例として N = 3, M = 3,

の場合を考える. この場合, どのように交換しても 0,2,1 と巡る経路が存在するため, K国は「良いK国の状態」になることができない. よって best_swap(N,M,E) は -1 を返す必要がある.

例として N = 6, M = 8,

の場合を考える. この場合も best_swap(N,M,E) は -1 を返す必要がある.

きつねの太郎と次郎はきつねの遊園地に遊びに来ています。

楽しそうなアトラクションがたくさんありますが、太郎は迷路のアトラクションに興味を持ったようです。次郎はあまり乗り気ではないようですが、太郎の熱意に負けていっしょに迷路に入ることにしました。

この遊園地の迷路はすこし特殊です。というのも、スタートとゴールがあって、スタート地点からゴール地点を目指して歩くというものではないからです。

2匹は迷路の異なる地点からスタートします。そしてどこでもよいのでふたたび出会うことが目的です。

迷路はとても暗いので、2匹は自分がどこにいるのかわかりません。周りをみても、非常に暗いので自分のすぐそばのこともわかりません。そんな迷路で2匹が出会うための道具として、Moffle社の便利なタブレット fPad が支給されています。

太郎の fPad には迷路の地図が入っていて見ることができますが、次郎の fPad には地図が入っていません。太郎の fPad から次郎の fPad にはデータを送信することができます。次郎は地図を見られませんが、太郎からの情報を受け取ることができます。

2匹の fPad にはもう1つ機能が備わっています。これを使うと自分の周囲の情報を少しだけ得ることができます。

次郎は暗いところがこわいので、できるだけはやく太郎と会いたいと思っています。2匹の間の距離がどのくらいあるのか計算することができるでしょうか。

それもできるだけはやく知りたいので、fPad の機能を使う回数はできるだけ少ないほうがよいです。

迷路の情報が与えられる。迷路は縦 H 横 W の長方形グリッドで表され、各マスは壁か通路のいずれかである。迷路の外側はすべて壁になっており通過することはできない。

迷路の通路は木構造をなしており、すべての通路の幅と壁の厚さは1である。より正確に言うと、ある大きさの長方形に含まれる格子点を頂点とし、距離が1であるような2点間に辺が存在するようなグラフにおける任意の全域木に対し、その頂点と辺を通路とし、そうでない部分を壁としたあとにまわりを外壁で囲ったものがこの場合の迷路である。

図 1

図 1 は迷路の例を示している。迷路の大きさには一周りぶんの外壁も含まれる、すなわちこの場合 H = 7, W = 7 となることに注意せよ。

この迷路のどこかに太郎と次郎がいるが、その2匹の場所はわからない。なお、2匹の場所は必ず迷路内の通路のマスであり、2匹のいるマスは異なることが保証されている。

次のプロシージャを実装せよ:

• 次のパラメータを持つプロシージャ taro(W, H, M):
  • W -- 迷路の横幅。3 ≦ W ≦ 1 000 を仮定してよい。
  • H -- 迷路の縦幅。3 ≦ H ≦ 1 000 を仮定してよい。W と H はともに 3 になることはない、すなわち少なくとも 2 つ以上通路のマスが存在することを仮定してよい。
  • M -- 迷路の情報を表す整数の2次元配列。0 ≦ i ＜ H, 0 ≦ j ＜ W に対して M[i][j] は、迷路の上から i+1 番目で左から j+1 番目の区画が壁であることを表す 1 か通路であることを表す 0 のいずれかである。
  このプロシージャ中で send(b) を繰り返し呼び出すことで次郎にデータを送信することが可能である。ただし b は 0 または 1 でなければならない。このプロシージャは jiro(W, H, S, X) よりも先に1度だけ呼び出され、戻り値を持たない。
• 次のパラメータを持つプロシージャ jiro(W, H, S, X):
  • W -- 迷路の横幅。この値は taro(W, H, M) が呼び出された際の W の値と一致している。
  • H -- 迷路の縦幅。この値は taro(W, H, M) が呼び出された際の H の値と一致している。
  • S -- 太郎から送られてきたデータの長さ(ビット数)。
  • X -- S 個の整数からなる1次元配列。0 ≦ i ＜ S に対して X[i] は taro(W, H, M) 中で send(b) が i+1 回目に呼び出された際の b の値に等しい。
  このプロシージャは taro(W, H, M) が呼び出された後に1度だけ呼び出される。このプロシージャは迷路における太郎と次郎の間の最短距離を計算して戻り値として返す必要がある。ただし辺を共有するマスどうしの距離を 1 とする。

taro(W, H, M) およびjiro(W, H, S, X) 中では query(dx, dy) を繰り返し呼び出すことができる。query(dx, dy) は taro(W, H, M) 中で呼び出された場合は太郎の現在位置、jiro(W, H, S, X) 中で呼び出された場合は次郎の現在位置から右に dx マス、下に dy マス移動したマスが壁であることを表す 1 か通路であることを表す 0 を返す。

query(dx, dy) 呼び出しにおいては -1 000 ≦ dx, dy ≦ 1 000 でなければならず、dx, dy によって指定されるマスが迷路の外側でも構わない。迷路の外側を指定した場合には壁を表す 1 が返される。

W = 5, H = 7,

の場合を考える。太郎の現在位置が (1, 1), 次郎の現在位置が (2, 5) であるとする。ただし迷路の上から y+1 番目で左から x+1 番目のマスを (x, y) と表す。taro 中で query を呼び出した際のパラメータと戻り値の例を次に示す。

また、taro 中で send が次のように呼び出されたとする。

このとき jiro 呼び出しにおいて S = 5 であり、

となる。

この場合 jiro は 7 を返さなければならない。

あなたはポーター・テレ・ポーターというロールプレイングゲームをプレイしている。

このゲームには、二つの正方形の陸マップと海マップがある。一辺の長さは陸マップがE、海マップがSであり、E＜Sである。
また、マップ上の地点は東向きをX軸、北向きをY軸として座標(X,Y)で表される。原点はマップの最も南西にある地点である．

２つのマップは下の図のように繋がっている。

この図での海マップは全て同じものを表している。例えば、図中のP点から東に１歩進むとQ点に到達する。

このゲームではあなたはポーター（荷物運搬人）というキャラクターとして行動する。
ポーターはマップ上で東西南北のいずれかの向きを向いていて，陸と海のどちらもマップ上も移動できる。

ゲームが始まった時、ポーターは陸マップの(0,0)にいて、ポーターには荷物を運ぶ目的地を表す陸マップの座標(X,Y)と、テレポーター(A,B)という装置が与えられる。
テレポーター(A,B)のスイッチを押すと、今いる位置からA歩前進し左に曲がってB歩前進したときの位置に一瞬で移動することができる。

ポーターは疲れたくないので、与えられたテレポーター(A,B)と方向転換だけを使って目的地(X,Y)へ移動したいと考えている。
テレポーターと方向転換だけで移動することが不可能な場合、ポーターは徒歩または泳ぎで目的地(X,Y)に移動する。

何らかの方法でポーターが目的地(X,Y)に到達すると、そこで新たな目的地の座標とテレポーターが与えられ、ゲームは続行する。
新たな目的地への移動では新たに与えられたテレポーターを使い、もともと持っていたテレポーターは使うことができない。

あなたは、目的地のそれぞれに行く過程において、ポーターがテレポーターと方向転換だけで目的地にたどり着けるか、またそのとき何回テレポーターを使えば良いかを知りたくなった。

一辺の長さEの正方形の陸のマップと、一辺の長さSの正方形の海のマップがある。 二つのマップ上の点は座標で表され、海のマップでは (S_x,S_y)(S_x,S_yは整数、0≦S_x＜S,0≦S_y＜S)、陸のマップでは(E_x,E_y)(E_x,E_yは整数、0≦E_x＜E,0≦E_y＜E)である。

この時、東西南北４方向への一歩の移動を次のように定義する。(注意：x軸は東向き、y軸は北向きである。)

また、キャラクターがいる位置と向きからA歩前に進み、左に曲がってB歩前に進むことを、合わせてテレポーター(A,B)を使うと定義する。

次のプロシージャを実装せよ:

• 次のパラメータを持つプロシージャ init(E,S):
  • E -- 陸のマップの大きさ。
  • S -- 海のマップの大きさ。
  このプロシージャは最初にmoveTo(X,Y,A,B)が呼び出される前に一度だけ呼び出される。
  このプロシージャは戻り値を持たない。
• 次のパラメータを持つプロシージャ moveTo(X,Y,A,B):
  • X -- 行き先の陸のマップのx座標。0≦X＜Eを仮定して良い。
  • Y -- 行き先の陸のマップのy座標。0≦Y＜Eを仮定して良い。
  • A,B -- キャラクターが使うテレポート(A,B)を表す。
  このプロシージャはQ回呼び出される。
  １回の呼び出しはキャラクターが今いる位置からテレポーター(A,B)と方向転換を複数回使って陸のマップの(X,Y)へ移動することに対応している。
  それぞれの呼び出しは、移動が可能な場合は必要なテレポーターの使用回数の最小値を、そのような移動が不可能な場合は -1 を戻り値として返す必要がある。
  また、移動が可能か不可能かに関わらず、このプロシージャが戻り値を返した後にはキャラクターは陸のマップの(X,Y)にいなければならない。