Mały Z jest początkującym zawodnikiem OI. Posiada prosty, spójny graf nieskierowany o $n$ wierzchołkach i $m$ krawędziach. Wierzchołki są ponumerowane od $0$ do $n-1$, a krawędzie od $0$ do $m-1$. Krawędź o numerze $i$ łączy wierzchołki $U_i$ oraz $V_i$.

Mały Z nie chce rozwiązywać zadań, więc wymyślił plan obijania się: najpierw zapisuje na kartce permutację $p_0, \ldots, p_{n-1}$ liczb od $0$ do $n-1$. Następnie wielokrotnie wykonuje operację: losowo wybiera krawędź $(u, v)$ w grafie i zamienia wartości $p_u$ oraz $p_v$.

Z pewnych powodów, jeśli w dowolnym momencie permutacja $p$ spełnia warunek $p_i=i$ dla wszystkich $0\le i \le n-1$, Mały Z nagle przypomina sobie, jak słaby jest, i przestaje się obijać. Mały Z nie chce, aby do tego doszło. Jeśli wskażesz mu strategię wykonania $k$ takich operacji, po których permutacja $p$ spełnia $p_i=i$, to po co najwyżej $k-1$ operacjach przestanie się obijać. Wtedy przyjmujemy, że koszt obijania się Małego Z wynosi $k$. W szczególności, jeśli przed pierwszą operacją $p$ już spełnia $p_i=i$, koszt obijania się wynosi $0$.

Ponieważ wiesz, że Mały Z jest słaby i zbliża się finał wojewódzki, chcesz zepsuć jego plan. Podchodzisz do niego, tłumaczysz mu zagadnienia i jednocześnie sabotujesz jego plan: w każdej swojej operacji możesz wybrać dwie liczby całkowite $0 \le u,v < n$ i zamienić wartości $p_u$ oraz $p_v$. Wartości $u, v$ mogą być takie same, co oznacza, że operacja nie zmienia permutacji $p$. Po każdej swojej operacji możesz zdecydować, czy kontynuować, czy zakończyć i wskazać Małemu Z strategię, która po $k$ jego operacjach doprowadzi do stanu $p_i=i$, tak aby koszt obijania się wynosił $k$. Jeśli zdecydujesz się kontynuować, Mały Z może wykonać jedną operację (może też ją pominąć): wybrać krawędź $(u, v)$ i zamienić $p_u$ oraz $p_v$, a następnie ponownie przychodzi kolej na Ciebie. (Mały Z nie może zmusić Cię do zakończenia operacji).

Mały Z chce, aby po zakończeniu przez Ciebie operacji, koszt jego obijania się był jak największy. Ty chcesz, aby był jak najmniejszy. Mały Z poprosił wcześniej Małego U o obliczenie kosztu, jaki poniesie, jeśli obie strony będą grały optymalnie. Jeśli uda Ci się sprawić, że koszt obijania się Małego Z będzie mniejszy lub równy tej wartości, Mały Z poczuje różnicę poziomów i przestanie się obijać, za co otrzymasz $100\%$ punktów za ten test. Jeśli jedynie obliczysz poprawny koszt, ale nie podasz strategii, Mały Z również poczuje różnicę poziomów, ale nie przestanie się obijać, za co otrzymasz $30\%$ punktów.

Jeśli po $T$ Twoich operacjach nie zdecydujesz się zakończyć, Mały Z odmówi dalszej współpracy, uznając, że nie potrafisz podać poprawnej strategii. W takim przypadku otrzymasz co najwyżej $30\%$ punktów.

Szczegóły implementacji

Twój kod musi zawierać plik graph.h.

Nie musisz implementować funkcji main. Wystarczy, że zaimplementujesz następującą funkcję:

std::pair<std::pair<int, int>, std::vector<int> > Solve(int n, int m, int T, std::vector<int> U, std::vector<int> V, std::vector<int> p, int subtask);

Znaczenie parametrów $n, m, T, U, V, p$ jest zgodne z opisem zadania. subtask oznacza numer podzadania.

Funkcja ta może wywoływać dwie poniższe funkcje:

void Answer(int x);

int Swap(int u, int v);

Przed powrotem z funkcji Solve musisz wywołać dokładnie raz funkcję Answer, przekazując jako argument $x$ koszt obijania się Małego Z przy optymalnej grze obu stron. Wywołując Swap, musisz upewnić się, że Answer zostało już wywołane dokładnie raz.

Przy wywołaniu funkcji Swap argumenty muszą spełniać $0 \le u, v < n$, co oznacza wykonanie zamiany $p_u$ i $p_v$. Jeśli funkcja zwraca $r$, gdzie $0 \le r < m$, oznacza to, że Mały Z wybrał krawędź o numerze $r$. W przeciwnym razie (gdy $r = -1$) Mały Z pominął operację.

Jeśli zdecydujesz się zakończyć po wykonaniu operacji, nie wywołuj Swap, lecz zwróć tę operację jako wynik funkcji. Wartością zwracaną przez Solve jest para składająca się z pary liczb (Twoja ostatnia operacja) oraz wektora (strategia dla Małego Z). $k$ to długość tego wektora. $i$-ty element wektora (o indeksie $i-1$) oznacza numer krawędzi użytej w $i$-tej operacji.

Punktacja

Jeśli funkcja Solve nie zwróci wyniku poprawnie (np. RE, TLE), otrzymasz $0$ punktów.

Jeśli przy powrocie z funkcji nie wywołałeś Answer, wywołałeś ją więcej niż raz lub wywołałeś Swap przed Answer, otrzymasz $0$ punktów.

Jeśli argument przekazany do Answer nie jest równy kosztowi przy optymalnej grze, otrzymasz $0$ punktów.

W pozostałych przypadkach, jeśli Twoja operacja jest niepoprawna, sekwencja operacji jest niepoprawna lub po wykonaniu wszystkich operacji $p$ nie spełnia $p_i=i$, otrzymasz $0.3$ punktów.

Jeśli wywołałeś Swap $T$ razy, przy $T$-tym wywołaniu biblioteka interakcyjna natychmiast zakończy program, a Ty otrzymasz $0.3$ punktów.

W przeciwnym razie otrzymasz $1$ punkt.

Wynik za podzadanie to iloczyn łącznej liczby punktów za podzadanie oraz minimalnej punktacji ze wszystkich testów w tym podzadaniu.

Opis plików

W katalogu graph znajdują się dwa pliki: graph.h oraz grader.cpp.

W systemie Linux możesz skompilować program poleceniem:

g++ -std=c++11 graph.cpp grader.cpp -o grader

Następnie uruchom:

./grader

Format wejścia grader:

Pierwsza linia zawiera cztery liczby całkowite $n, m, T, subtask$.

Druga linia zawiera $n$ liczb całkowitych, gdzie $i$-ta liczba to $p_{i-1}$.

Kolejne $m$ linii zawiera po dwie liczby całkowite, oznaczające $U_{i-1}$ oraz $V_{i-1}$.

Funkcja Swap w dostarczonym grader.cpp zawsze zwraca $-1$ i sprawdza jedynie poprawność operacji. Zaleca się zmianę strategii w grader.cpp przed testowaniem. Grader używany do oceny różni się od tego dostarczonego.

Podzadania

Dla wszystkich danych: $2 \le n, m \le 100000, 0 \le p_i, U_i, V_i < n$, $\forall 0\le i < j < n, p_i \neq p_j$, $1 \le subtask \le 7$. Gwarantuje się, że przy optymalnej grze koszt obijania się Małego Z nie przekracza $10^7$. Graf jest spójny.

Gwarantuje się, że biblioteka interakcyjna stosuje pewną strategię optymalną.

Subtask 1 ($10$ pkt): $n \le 8, T = 11$

Subtask 2 ($15$ pkt): Graf jest ścieżką, krawędź $i$ łączy $i$ oraz $i+1$, $n \le 400, T = 100001$

Subtask 3 ($15$ pkt): Graf jest ścieżką, krawędź $i$ łączy $i$ oraz $i+1$, $n \le 400, T = 1001$

Subtask 4 ($15$ pkt): Graf jest ścieżką, krawędź $i$ łączy $i$ oraz $i+1$, $T = 100001$

Subtask 5 ($10$ pkt): Graf jest drzewem, $T = 100001$

Subtask 6 ($15$ pkt): $n, m \le 400, T = 100001$

Subtask 7 ($20$ pkt): $T = 100001$

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