Jesteś Wielką Rybą i zarządzasz ogromnym państwem.

W tym państwie znajduje się wiele miast oraz wiele rzek łączących te miasta. Po dokładnych obserwacjach zauważono, że z każdego miasta wypływa jedna rzeka, która albo wpada do morza, albo do innego miasta. Ponieważ woda zawsze płynie w dół, nie istnieją żadne cykle rzeczne, a rzeka wpadająca do morza jest tylko jedna.

W pewnym momencie nad wybranym miastem może przejść ulewa. Wówczas rzeka wypływająca z tego miasta gwałtownie wezbrać, co spowoduje również wezbranie rzek wypływających ze wszystkich miast położonych w dół biegu rzeki od tego miasta.

Nie ma skutecznego sposobu na zabezpieczenie miasta, nad którym przechodzi ulewa, ale każde miasto położone w dół biegu rzeki może przygotować się na jedną z rzek do niego wpływających. Jeśli miasto przygotuje się na konkretną rzekę wpływającą do niego, uniknie ogromnych szkód spowodowanych jej wezbraniem.

Na początku możesz wydać polecenie każdemu miastu, aby przygotowało się na jedną z wpływających do niego rzek (oczywiście można też nie przygotowywać się na żadną). Przed i po każdej ulewie, ze względu na pilność sytuacji, możesz wydawać jedynie polecenia awaryjne. Istnieją dwa rodzaje poleceń awaryjnych:

1. Nakazanie miastu anulowania przygotowania na rzekę wpływającą do niego.
2. Nakazanie miastu przygotowania się na konkretną rzekę wpływającą do niego.

Ze względu na ograniczenia kadrowe, nie możesz pozwolić miastu przygotować się na dwie rzeki jednocześnie. Dlatego, jeśli chcesz, aby miasto, które jest już przygotowane na jedną rzekę, przygotowało się na inną, musisz najpierw anulować jego obecne przygotowanie.

Obecnie nadchodzi $q$ ulew, jedna po drugiej. Przed każdą ulewą możesz zaobserwować, nad którym miastem ona wystąpi. Przed każdą ulewą możesz wydać kilka poleceń awaryjnych, aby uniknąć ogromnych szkód w miastach położonych w dół biegu rzeki, a po ulewie możesz wydać kolejne polecenia, aby przygotować się na przyszłość. Oczywiście chcesz, aby liczba wydanych poleceń była jak najmniejsza. Czy potrafisz znaleźć optymalne rozwiązanie?

Zadanie

Musisz zaimplementować dwie funkcje, aby wykonać zadanie:

• init(n, father):
  • Ta funkcja zostanie wywołana na samym początku zadania, tylko raz. Przekaże Ci informacje o państwie, a Ty musisz określić początkowe przygotowania każdego miasta.
  • n oznacza liczbę miast, miasta są numerowane od $1$ do $n$.
  • father to tablica o długości $n - 1$ z indeksami $[0 \dots n-2]$, gdzie $father_i$ oznacza numer miasta, do którego wpływa rzeka z miasta $i + 2$. Rzeka z miasta $1$ wpływa do morza. Gwarantuje się, że $father_i < i + 2$.
  • Zwróć tablicę o długości $n$, reprezentującą początkowe przygotowania każdego miasta. $i$-ty element tablicy oznacza, że miasto $i+1$ przygotowuje się na rzekę z miasta o tym numerze. Jeśli wartość wynosi $0$, oznacza to brak przygotowania.
• solve(x):
  • Ta funkcja może być wywoływana wielokrotnie po wywołaniu init, co oznacza, że ulewa nadchodzi nad miasto $x$. Musisz użyć funkcji set, aby wydać polecenia awaryjne i uniknąć ogromnych szkód w miastach położonych w dół biegu rzeki.
  • Musisz zagwarantować, że w tej funkcji liczba wywołań set nie przekroczy $60$.
  • W tej funkcji powinieneś wywołać funkcję wait dokładnie raz. Polecenia wydane przed wywołaniem wait zostaną wykonane przed nadejściem ulewy, a polecenia wydane po wait zostaną wykonane po ulewie.

Możesz wywołać następujące dwie funkcje, aby zaimplementować solve:

• set(x, p):
  • Można wywołać tylko wewnątrz funkcji solve. Oznacza przygotowanie miasta $x$ na rzekę wypływającą z miasta $p$. Jeśli $p$ wynosi $0$, oznacza to anulowanie przygotowania miasta $x$ na jakąkolwiek rzekę.
  • W każdym wywołaniu solve można użyć maksymalnie $60$ razy.
  • Zabrania się wywoływania wewnątrz init.
• wait()
  • Należy wywołać dokładnie raz w każdym solve. Oznacza zakończenie przygotowań przed ulewą. W momencie wywołania musisz zagwarantować, że wszystkie miasta położone w dół biegu rzeki od miasta, nad którym przechodzi ulewa, są przygotowane na odpowiednią rzekę.
  • Po wywołaniu tej funkcji można kontynuować operacje, aby przygotować się na kolejną ulewę.
  • Zabrania się wywoływania wewnątrz init.

Uwaga: miasto albo nie przygotowuje się na nic, albo przygotowuje się na rzekę z jednego konkretnego miasta.

Jeśli Twoje operacje są nieprawidłowe lub nie spełniają wymagań, test otrzyma natychmiast $0$ punktów.

W razie wątpliwości zapoznaj się z przykładami i pobraną biblioteką testującą, która zawiera przykładowy program.

Szczegóły implementacji

To zadanie wspiera tylko język C++.

Musisz przesłać jeden plik źródłowy implementujący funkcje init i solve zgodnie z powyższym opisem oraz dołączyć plik nagłówkowy river.h.

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

Interfejsy funkcji set i wait są następujące:

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

Przykład

System testujący wczyta drzewo i wszystkie operacje w następującym formacie:

Pierwsza linia zawiera dwie liczby całkowite $n, q$, oznaczające liczbę wierzchołków drzewa i liczbę zapytań.

Druga linia zawiera $n-1$ liczb oznaczających tablicę father.

Kolejne $q$ linii zawiera po jednej liczbie $x$, oznaczającej wywołanie solve(x).

Przykład 1 Wejście

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

Przykład 1 Wyjście

2 6
ok you are right!

Uwagi do przykładu 1

Jest to komunikat podany po pomyślnym zakończeniu wszystkich operacji, gdzie pierwsza liczba całkowita oznacza maksymalną liczbę wywołań set w jednej rundzie, a druga to łączna liczba wywołań set.

Podzadania

$1\leq n \leq 50000$, $1 \leq q \leq 500000$.

Nie możesz wywołać więcej niż $60$ poleceń w jednej rundzie.

Jeśli nie wykonasz zadania w określonym czasie i limicie pamięci, otrzymasz $0$ punktów.

W przeciwnym razie, niech $x$ będzie maksymalną liczbą wywołań set w każdym solve ($\max$). Otrzymasz punkty zgodnie ze wzorem:

$$ 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} $$

Twój wynik będzie minimalnym wynikiem ze wszystkich testów.

Jeśli liczba wywołań set w każdym solve nie przekracza $60$ i wszystkie operacje są poprawne:

Gwarantuje się, że czas działania biblioteki interakcyjnej nie przekroczy $1\,\mathrm{s}$.

Gwarantuje się, że zużycie pamięci przez bibliotekę interakcyjną nie przekroczy $10\,\mathrm{MB}$.