きつねの次郎はゆたかな森林でほかのどうぶつたちと楽しく遊んで暮らしていました。

森林のなかにはどうぶつたちの遊び場がたくさんあって、遊び場どうしはいくつかの道で結ばれています。もちろんどの遊び場からどの遊び場にもいくつかの道をたどって行くことができて、ある遊び場からある遊び場へいくための経路は1通りだけあります。

しかしどうぶつたちの幸せな時間は長くは続きませんでした。人間たちがとつぜん森林へやってきて、どうぶつたちの遊び場を壊していくようになったのです。

ある遊び場が人間たちによって壊されてしまうと、そこはもうどうぶつたちには危ないので通ることができません。そうするとどうぶつたちの遊び場が分断されてしまって、ある遊び場からいくことのできない遊び場が現れることになります。

次郎をはじめとするどうぶつたちは何とかしてこれに抵抗したいのですが、彼らの力で人間を止めることは残念ですができません。

しかたがないのでどうぶつたちは、分断されてしまった遊び場たちの中で、これからいちばん長く残りそうなところへ行くことにしました。

どうぶつたちはとてもかわいそうですが、人間による森林の破壊はとどまるようすを見せません。せめて彼らどうぶつたちがすこしでも長く、より多くの遊び場で遊んでいられるように、彼らを助けてほしいのです。

N 頂点からなる木が与えられる。各頂点には 0 から N-1 までの異なる整数の番号がつけられている。

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

• 次のパラメータを持つプロシージャ init(N, E):
  • N -- 頂点の数。頂点には 0 から N-1 までの異なる整数の番号がつけられている。
  • E -- 辺の情報を表す整数の 2 次元配列。0 ≦ i ＜ N-1 に対し、辺 i は異なる2つの頂点 E[i][0] と E[i][1] を結んでいる。E は木構造を表していることが保証されている。すなわちどの頂点からどの頂点へも辺をたどって行くことが可能で、かつその経路は 1 通りしか存在しない。
  このプロシージャは最初に query(i) が呼び出される前に1度だけ呼び出される。このプロシージャは戻り値を持たない。
• 次のパラメータを持つプロシージャ query(i):
  • i -- 壊される頂点の番号。
  このプロシージャはちょうど N-1 回呼び出される。1回の呼び出しで1つの頂点が破壊される(この破壊は、それ以前のすべての破壊に続くものである)。すでに破壊された頂点 i がもういちど指定されることはない。ある頂点 i を破壊するとき、その頂点とそれに接続するすべての辺を削除する。それぞれの呼び出しは頂点の破壊の後に残った森(1つ以上の木の集合)について、それぞれの木の頂点数のうち最大のものを返す必要がある。存在する木すべて（いつ分断されたかに関わらず）の頂点数のうち最大のものを返すこと。

図1に示される N = 5,

最初、プロシージャ init は上記のパラメータで呼び出される。その後プロシージャ query が1回の破壊ごとに1回ずつ呼び出される。以下に呼び出しと正しい戻り値の例を示す:

図2に示される N = 5,

最初、プロシージャ init は上記のパラメータで呼び出される。その後プロシージャ query が1回の破壊ごとに1回ずつ呼び出される。以下に呼び出しと正しい戻り値の例を示す:

あなたは高校生向けの国際的なコンテストであと一歩のところで金メダルを逃し、帰国後に自分が受験生であることを発見するに至った。しかしあなたは、受験に必要な N 種類の勉強を全くこなしていない。

集中力に定評のあるあなたは、それぞれの勉強を連続した期間に行うことで、残り W 日の受験勉強を乗り切ることにした。

あなたはこの期間中に N 個の模擬試験を受験することにしている。

各模擬試験は開催日と影響力 d が決まっており、開催日前後 d 日未満の模試をあなたは意識している。そして、その日意識している模試の数があなたのやる気の数値となる。

i 種類目の勉強は i 以上のやる気がある時でないとできない。一日にできる勉強の個数には限りはないので、全ての種類の勉強について、連続して勉強できる最大の日数を調べたい。

W 日間中に N 個の模試が行われる。模試には 0 から N-1 までの異なる整数の番号がつけられている。

それぞれの模試 i には開催日 X[i] と 影響度 D[i] が決まっている。日付 t に対して X[i]-D[i] < t < X[i]+D[i] が成り立つ場合に限り、あなたは日付 t のときに模試 i を意識している。

それぞれの日において、あなたの勉強のやる気はその日にあなたが意識している模試の数である。

あなたがやるべき勉強は N 種類ある。勉強には 1 から N までの異なる整数の番号がつけられている。勉強 k を行えるのはあなたのやる気が k 以上の日だけである。

次のパラメータを持つプロシージャ schedule(W, N, X, D) を実装せよ:

• W -- 受験勉強の日数。受験勉強中の各日付は0以上W未満の整数で表される。
• N -- 模試および勉強の数。模試には 0 から N-1、勉強には 1 から N の異なる整数の番号がつけられている。
• X -- 模試の開催日を表す整数の配列。0 ≦ i < N に対し 0 ≦ X[i] < W を仮定してよい。
• D -- 模試の影響度を表す整数の配列。0 ≦ i < N に対し 1 ≦ D[i] ≦ W を仮定してよい。X[i]-D[i] < 0 や X[i]+D[i] ≧ W となることはあるかもしれない。

それぞれの勉強 k について、あなたが勉強 k を連続して行うことのできる最も長い期間を計算し answer(k, L, R) を呼び出せ。L, R はそれぞれ勉強 k を連続して行うことのできる最長の期間の最初の日と最後の日である。勉強 k を行える日が 1 日もない場合は answer(k, 0, 0) と呼び出さねばならない。最長の期間が複数ある場合は L が最も小さいものを選ばねばならない。 answer(k, L, R) はどのような k の順番で呼び出しても構わないが、すべての勉強についてちょうど 1 回ずつ呼び出される必要がある。

なお、あなたは 1 日に何種類でも勉強をすることができるのでそれぞれの勉強について独立に考えてよい。すなわち異なる k の値について、answer(k, L, R) 呼び出しの L, R が表す期間は共通部分を持っていてもよい。

W = 10, N = 3,

の場合を考える。schedule は次のようなパラメータで answer を呼び出す必要がある。(この順番に呼び出す必要はない。)

いもすは、14歳の時に魔法に目覚めた魔法少女である。

いもすは、161日後に来たるべき強敵「ウォーターリークス」を倒すために、魔力を高める訓練をしている。その訓練とは次のようなものである。

N 個の、それぞれ魔力の値が定められている石があり、1列に並んでいる。

連続したいくつかの石を選んで、それらを魔力の昇順になるように、すなわちより番号の小さい位置にはより魔力の小さい石が置かれるように並べ替えることができると、いもすの魔力を上げることができる。どの石もとても重いので、並べ替えるときは、魔法を使って隣り合う石同士を入れ替えることしかできない。

しかし、石は非常にたくさんあるため、並べ替えるのはとても大変である。魔力を上げることができる石の選び方はいくつかあるため、最も楽なものを選びたい。さらに、石の魔力の強さは時とともに変化することがある。魔力の強さの変化の仕方は、すでにいもすの魔法によりすべて予測されている。

いもすの魔法の訓練を助けるために、次に示すようなプログラムを書いてほしい。

N 個の整数からなる配列 A が与えられる。石の列の左端から i+1 個目の石を石 i と番号づけ、A[i] は石 i の魔力を表すとする。

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

• 次のパラメータを持つプロシージャ init(N, A):
  • N -- 石の数。石には左から順に 0 から N-1 までの異なる整数の番号がつけられている。
  • A -- 石の魔力を表す整数の配列。0 ≦ i < N に対し 1 ≦ A[i] ≦ N を仮定してよい。
  このプロシージャは最初に update(i, x) または train(p, q) が呼び出される前に1度だけ呼び出される。このプロシージャは戻り値を持たない。
• 次のパラメータを持つプロシージャ update(i, x):
  • i -- 魔力が変化する石の番号。
  • x -- 魔力が変化した後の石 i の魔力。1 ≦ x ≦ N を仮定してよい。
  このプロシージャは複数回呼び出される。1回の呼び出しは1回の魔力の変化に対応する。このプロシージャは戻り値を持たない。
• 次のパラメータを持つプロシージャ train(p, q):
  • p -- 並べ替える石の左端の番号。0 ≦ p < N を仮定してよい。
  • q -- 並べ替える石の右端の番号。p ≦ q < N を仮定してよい。
  このプロシージャは複数回呼び出される。1回の呼び出しは石 p から石 q (両端も含む)までの石を、隣り合う石を入れ替えることによって p の位置から q の位置に向かって魔力の昇順に並べ替える訓練に対応している。それぞれの呼び出しは対応する訓練のために必要な最小の石の入れ替え回数を戻り値として返す必要がある。ただし、実際には石の並べ替えは行わず、入れ替えの回数だけを求めるものとする。

N = 6, はじめの石の魔力の状態が

の場合を考える。

最初、プロシージャ init は上記のパラメータで呼び出される。その後、複数回の update または train の呼び出しが任意の順番で行われる。以下に呼び出しと正しい戻り値の例を示す: