Kraje A i B są ze sobą skłócone. Kraj A chce poznać sieć kolejową B, aby dokonać inwazji. Wysyłał wielokrotnie szpiegów, lecz zawsze łapano ich przed zdobyciem istotnych informacji. A wie więc tylko, że:

• Sieć kolejowa B składa się z $N$ stacji ponumerowanych od $1$ do $N$.

• Dowolne dwie różne stacje są połączone bezpośrednio torem albo przez inne stacje połączone torami.

• Dowolne dwie stacje łączy dokładnie jedna ścieżka.

• Żaden tor nie łączy bezpośrednio stacji z nią samą.

Widząc ograniczenia szpiegostwa, A zamierza przekupić wysokiego urzędnika kolei B, aby zdobyć rysunek sieci. Wysłanie go wprost ujawniłoby zdrajcę, więc zdrajca zmodyfikuje rysunek następująco przed wysłaniem do A.

• Narysuje $K$ fałszywych torów. Wybierze różne stacje $a$ i $b$, które na rysunku nie są bezpośrednio połączone torem, i połączy je fałszywym torem. Powtórzy to $K$ razy.

• Specjalnie oznaczy jedną stację.

• Na koniec usunie wszystkie numery stacji.

Zdrajca prześle wynikowy rysunek do A. Ponieważ na podstawie samych tych informacji trudno rozpoznać sieć kolejową B, nikt nie dowie się o wycieku tajnych informacji.

Aby plan się powiódł, należy rozwiązać następujące problemy.

• Rysunek otrzymany przez A nie ma numerów stacji ani oznaczeń prawdziwych i fałszywych torów. Wiadomo jedynie, która stacja jest oznaczona oraz że dodano dokładnie $K$ fałszywych torów.

• Nadawca musi więc odpowiednio wybrać fałszywe tory i oznaczoną stację, aby odbiorca mógł odróżnić tory prawdziwe od fałszywych na podstawie samego rysunku.

• Odbiorca musi zrozumieć sposób modyfikacji rysunku i odzyskać rysunek pierwotnej sieci.

Potrzebne są zatem dwie funkcje: modyfikująca rysunek i odzyskująca z niego prawdziwą sieć kolejową. Kraj A chce powierzyć ci to zadanie.

Szczegóły implementacji

Zaimplementuj następujące dwie funkcje.

vector< pair<int, int> > encode_map(int N, int K, int &X,
                                            vector< pair<int, int> > E)

• Argument całkowity N to liczba $N$ stacji w sieci B. Stacje oznaczane są liczbami całkowitymi od $1$ do $N$ włącznie.

• Argument całkowity K to liczba $K$ fałszywych torów do dodania.

• Argument X służy do zapisania numeru oznaczonej stacji. Po zakończeniu funkcji musi zawierać dodatnią liczbę całkowitą od $1$ do $N$ włącznie.

• Tablica argumentu E ma rozmiar $N-1$ i opisuje sieć B. Para $(a,b)$ w E oznacza bezpośredni tor między stacjami $a$ i $b$.

• Zwróć tablicę $K$ par $(a,b)$, oznaczających fałszywe tory między różnymi stacjami $a$ i $b$. Nie wolno dodawać fałszywego toru między $a$ i $b$, jeśli już łączy je tor prawdziwy lub fałszywy.

vector< pair<int, int> > decode_map(int N, int K, int X,
                                            vector< pair<int, int> > E)

• Argument całkowity N to liczba $N$ stacji w sieci B. Stacje oznaczane są liczbami od $1$ do $N$ włącznie. Ponieważ podczas przesyłania usunięto numery, numery w tej funkcji mogą różnić się od rzeczywistych. Powstają przez zastosowanie pewnej bijekcji do numerów używanych w encode_map.

• Argument całkowity K to liczba $K$ dodanych fałszywych torów.

• Argument całkowity X to numer specjalnie oznaczonej stacji.

• Tablica E ma rozmiar $N+K-1$ i opisuje rysunek dostarczony do A. Para $(a,b)$ oznacza, że stacje $a$ i $b$ są bezpośrednio połączone prawdziwym lub fałszywym torem na rysunku. Kolejność elementów E nie ma znaczenia.

• Funkcja odtwarza pierwotny rysunek z rysunku utworzonego przez encode_map. Zwróć tablicę $N-1$ par $(a,b)$ opisujących sieć kolejową B.

W żadnym miejscu przesyłanego kodu nie wolno wywoływać funkcji wejścia ani wyjścia.

Każdy test zawiera co najmniej jeden niezależny scenariusz. Dla testu z $T$ scenariuszami program wywołujący powyższe funkcje jest uruchamiany dokładnie dwa razy, jak opisano poniżej.

Przy pierwszym uruchomieniu:

• encode_map jest wywoływana $T$ razy.

• Wyniki encode_map są zapisywane przez system oceniający.

• decode_map nie jest wywoływana.

Przy drugim uruchomieniu:

• decode_map jest wywoływana wielokrotnie. Przy każdym wywołaniu wybierany jest dowolny scenariusz, a rysunek utworzony dla niego przez encode_map jest wejściem decode_map.

• encode_map nie jest wywoływana.

Czas działania i zużycie pamięci oblicza się łącznie dla obu uruchomień.

Ograniczenia

• $1 \le T \le 200$

• $3 \le N \le 200$

• $1 \le K < \frac{N}{2}$

Podzadania

1. ($4$ punkty) $N \le 4$.

2. ($13$ punktów) $K=1$.

3. ($11$ punktów) Do każdej stacji dochodzą najwyżej dwa tory.

4. ($29$ punktów) Z dowolnej stacji można dotrzeć do dowolnej innej, przejeżdżając najwyżej $\lfloor N/2 \rfloor$ torów.

5. ($43$ punkty) Brak dodatkowych ograniczeń.

Podzadania

Test jest uznawany za poprawny tylko wtedy, gdy encode_map tworzy poprawny rysunek, a decode_map prawidłowo odtwarza sieć. W szczególności, jeśli wynik decode_map zawiera choć jeden fałszywy tor, wynik testu wynosi $0$. Kolejność elementów tablic zwracanych przez obie funkcje nie ma znaczenia.

Wynik podzadania jest minimum wyników wszystkich jego testów.

Przykład

• Rozważ $N=6$, $K=1$ i tory $E=[(1,2),(1,3),(1,4),(4,5),(4,6)]$.

Program oceniający wywołuje następującą funkcję.

encode_map(6, 1, X, [(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)])

Lewy rysunek przedstawia sieć B. Dodanie fałszywego toru $(4,2)$ i oznaczenie stacji $1$ daje prawy rysunek. Wtedy encode_map zwraca [(4, 2)] i zapisuje $1$ w X. Mogą istnieć inne odpowiedzi.

Następnie program oceniający wywołuje poniższą funkcję. Kolejność elementów tablicy w ostatnim argumencie może się zmienić.

decode_map(6, 1, 2, [(1, 5), (2, 3), (2, 4), (2, 5), (3, 5), (5, 6)])

Rysunek opisany przez wejście pokazano poniżej. Numery stacji różnią się od użytych w encode_map.

Funkcja zwraca [(3, 2), (4, 2), (5, 6), (1, 5), (5, 2)]. Kolejność elementów może być inna.

Ten przykład spełnia warunki podzadań $2$, $4$ i $5$.

Przykładowy program oceniający

Przykładowy program oceniający przyjmuje wejście w następującym formacie.

• Wiersz $1$: $T$

Dalej występuje $T$ bloków, po jednym na scenariusz. Każdy ma następujący format.

• Wiersz $1$: $N\ K$

• Wiersz $1+i$ ($1 \le i \le N-1$): $a_i\ b_i$

Para $a_i,b_i$ oznacza tor łączący stacje $a_i$ i $b_i$.

Dla każdego scenariusza przykładowy program oceniający wypisuje:

• Wiersz $1$: tablica zwrócona przez encode_map.

• Wiersz $2$: tablica zwrócona przez decode_map.

Przykładowy program oceniający może różnić się od używanego podczas oceny.