あなたは「大魚」であり、巨大な国家を統治しています。

この国には多くの都市があり、都市間には多くの川が流れています。注意深く観察すると、各都市からは1本の川が流れ出ており、海に流れるか、あるいは別の都市に流れていることがわかります。水は常に低い方へ流れるため、川が環状になることはありません。また、海に流れる川は1本だけであることがわかっています。

ある時刻に、特定の都市の上空で豪雨が発生することがあります。その都市から流れ出る川の水量は急増し、その都市の下流にあるすべての都市から流れ出る川の水量も急増します。

豪雨が発生する都市に対して有効な防衛手段はありませんが、下流の各都市は、自分に流れ込む川のうちの1本に対して準備を行うことができます。ある都市が自分に流れ込む特定の川に対して準備をしていれば、その川の急増による甚大な被害を防ぐことができます。

最初、あなたは各都市に対して、自分に流れ込む川のうち1本に準備をするよう命令できます（もちろん、何も準備しないことも可能です）。その後の各豪雨の前後には、時間が限られているため、緊急命令しか出すことができません。緊急命令には以下の2種類があります。

1. ある都市に対し、現在準備している川への準備を解除させる。
2. ある都市に対し、自分に流れ込む特定の川への準備をさせる。

人的資源の制約により、1つの都市が同時に2本の川に対して準備をすることはできません。したがって、すでに準備をしている都市が別の川に対して準備をしたい場合は、現在の川への準備を先に解除しなければなりません。

今、$q$ 回の豪雨が次々と発生します。あなたは豪雨が発生する前に、どの都市で豪雨が起こるかを観測できます。各豪雨の前に緊急命令を出して下流の都市が甚大な被害を受けるのを防ぐことができ、豪雨の後にも次の豪雨に備えて緊急命令を出すことができます。もちろん、出す緊急命令の数はできるだけ少なくしたいところです。あなたは効率的な方法を見つけられるでしょうか？

任務

あなたは以下の2つの関数を実装して、この問題を解決する必要があります。

• init(n, father):
  • この関数はタスクの開始時に一度だけ呼び出されます。国に関する情報が与えられるので、各都市の初期状態を決定してください。
  • n は都市の数であり、都市番号は $1$ から $n$ です。
  • father は長さ $n - 1$ の配列で、添字は $[0 \dots n-2]$ です。$father_i$ は都市 $i + 2$ から流れ出る川が到達する都市の番号を表します。都市 $1$ から流れ出る川は海に流れます。$father_i < i + 2$ であることが保証されています。
  • 長さ $n$ の配列を返してください。各要素は各都市の初期準備状態を表します。$i-1$ 番目の値は、第 $i$ 都市が準備している流入元の都市番号であり、$0$ の場合は何も準備していないことを意味します。
• solve(x):
  • この関数は init の後に複数回呼び出されます。都市 $x$ で豪雨が発生することを意味します。set 関数を使用して緊急命令を出し、下流の都市が甚大な被害を受けるのを防いでください。
  • この関数内での set 関数の呼び出し回数は $60$ 回を超えてはなりません。
  • この関数内では wait 関数をちょうど1回呼び出す必要があります。wait を呼び出す前に出した命令は豪雨の前に実行され、wait を呼び出した後に出した命令は豪雨の後に実行されます。

solve を実装するために、以下の2つの関数を呼び出すことができます。

• set(x, p):
  • solve 関数内でのみ呼び出し可能です。都市 $x$ が都市 $p$ からの川に対して準備を行うことを意味します。$p$ が $0$ の場合、都市 $x$ は現在準備している川への準備を解除します。
  • 1回の solve で最大 $60$ 回まで呼び出せます。
  • init 関数内では呼び出し禁止です。
• wait():
  • 各 solve でちょうど1回呼び出します。豪雨前の準備が完了したことを示します。呼び出し時点で、豪雨が発生する都市の下流にあるすべての都市が、自分に流れ込む川に対して準備を完了している必要があります。
  • この関数呼び出し後も操作を継続し、次の豪雨に備えることができます。
  • init 関数内では呼び出し禁止です。

注意：各都市は、何も準備しないか、あるいは自分に流れ込む特定の川に対して準備をするかのいずれかです。

操作が不正であるか、要件を満たさない場合、そのテストケースは直ちに $0$ 点となります。

不明な点がある場合は、サンプルおよび配布された評価用ライブラリ内のサンプルプログラムを参照してください。

実装の詳細

本問題は C++ 言語のみをサポートしています。

上記の init および solve 関数を実装したソースファイルを1つだけ提出してください。ヘッダーファイル river.h をインクルードする必要があります。

std::vector<int> init(int n, std::vector<int> father);
void solve(int x);

set および wait 関数のインターフェースは以下の通りです。

void set(int x, int p);
void wait();

入出力例

配布されたサンプル評価システムは、木構造とすべての操作を読み込みます。形式は以下の通りです。

1行目に2つの正整数 $n, q$ が入力され、それぞれ木の頂点数とクエリ数を表します。

2行目に father 配列を表す $n-1$ 個の整数が入力されます。

続く $q$ 行には、各行に solve(x) の呼び出しを表す整数 $x$ が入力されます。

入出力例 1

入力 1

8 8
1 1 3 3 4 5 3
7
1
1
7
3
6
5
1

出力 1

2 6
ok you are right!

注記 1

これはすべての操作が正常に完了した後に表示される情報です。最初の正整数は1回の solve における set 呼び出し回数の最大値、2番目は set 呼び出しの合計回数です。

小課題

$1\leq n \leq 50000$、$1 \leq q \leq 500000$。

1回の solve で $60$ 回を超える命令を呼び出すことはできません。

規定の時間制限およびメモリ制限内にタスクを完了できなかった場合、$0$ 点となります。

それ以外の場合、各 solve における set 呼び出し回数の最大値を $\max$ とすると、得点は以下の式で計算されます。

$$ f \left( x \right) = \begin{cases} 0 & 60 \lt x \\ 100 - 18 \times \sqrt{x - 35} & 36 \leq x \leq 60 \\ 100 & \operatorname{otherwise} \end{cases} $$

最終的な得点は、すべてのテストケースにおける得点の最小値となります。

各 solve における set の呼び出し回数が $60$ 回以下であり、すべての操作が正当である場合：

評価用ライブラリの実行時間は $1\,\mathrm{s}$ 以内であることが保証されます。

評価用ライブラリの使用メモリは $10\,\mathrm{MB}$ 以内であることが保証されます。