W klasycznej grze w dopasowywanie (ang. online matching), krawędzie grafu są ujawniane jedna po drugiej. Za każdym razem, gdy pokazywana jest krawędź, musisz natychmiast i nieodwołalnie zdecydować, czy włączyć ją do swojego dopasowania. Twoim celem jest zapewnienie, aby żadne dwie wybrane krawędzie nie dzieliły wierzchołka, przy jednoczesnej maksymalizacji całkowitej liczby wybranych krawędzi.
Jesteś ambitnym informatykiem, głodnym sławy. Jak dobrze wiesz, znalezienie dopasowania maksymalnego w trybie online jest udowodnione jako niemożliwe z wysokim prawdopodobieństwem — nawet dla najprostszych klas grafów, takich jak grafy dwudzielne. Jednak tam, gdzie inni widzą fundamentalną barierę, Ty widzisz szansę na chwałę. Dziś twierdzisz, że złamałeś długo otwarty problem dla drzew i jesteś gotowy zaprezentować światu swój przełomowy algorytm.
Jest tylko jeden problem: wczoraj odkryłeś błąd w swoim dowodzie i nadal nie masz pojęcia, jak go naprawić. Nie chcąc rezygnować z bycia w centrum uwagi, postanawiasz zamienić swój pokaz w magiczną sztuczkę — Twój asystent, ukryty za kulisami, przekaże małą wskazówkę dotyczącą całego drzewa o $n$ wierzchołkach, zanim gra się rozpocznie.
Twój pierwotny plan był prosty: niech Twój asystent wysyła odpowiedź na każde zapytanie o krawędź bezpośrednio. W tym celu zainstalowałeś tajną słuchawkę zdolną do odebrania pojedynczego ciągu binarnego o długości $(n - 1)$. Jednak publiczność jest sceptyczna wobec Twojego „przełomu”. Aby zapobiec wszelkim zaaranżowanym sztuczkom, żądają, aby krawędzie były prezentowane w kolejności losowej jednostajnej — takiej, której ani Ty, ani Twój asystent nie możecie przewidzieć ani kontrolować.
Scena jest gotowa. Światła są skierowane na Ciebie. Teraz udowodnij swoje twierdzenie — bez zmiany kanału.
Interakcja
Twoje rozwiązanie jest uruchamiane dwukrotnie w każdym teście. W rundzie prepare Twoje rozwiązanie będzie działać jako asystent. W rundzie play Twoje rozwiązanie będzie działać jako Ty, magik. W obu rundach Twoje rozwiązanie będzie oceniane jako procedura interaktywna.
Runda Prepare
Pierwsza linia wejścia zawiera słowo prepare. Druga linia zawiera liczbę całkowitą $n$ ($2 \le n \le 500$) — liczbę wierzchołków. Kolejne $(n - 1)$ linii zawiera po dwie liczby całkowite $u$ oraz $v$ ($1 \le u, v \le n, u < v$), oznaczające krawędź nieskierowaną między $u$ a $v$ w drzewie.
Musisz wypisać jedną linię zawierającą ciąg binarny $s$ o długości dokładnie $(n - 1)$, składający się wyłącznie ze znaków 0 i 1. Jest to ciąg przekazywany do drugiej rundy play. Jeśli Twoje wyjście nie jest zgodne z wymaganym formatem, otrzymasz werdykt Wrong Answer.
Runda Play
Twoje rozwiązanie zostanie zrestartowane dla rundy play.
Pierwsza linia zawiera słowo play. Druga linia zawiera liczbę całkowitą $n$. Trzecia linia zawiera ciąg binarny $s$, dokładnie taki, jaki wypisałeś w rundzie prepare.
Następnie gra rozpoczyna się od $(n - 1)$ tur. W każdej turze podawana jest linia zawierająca dwie liczby całkowite $u$ oraz $v$ ($1 \le u, v \le n, u < v$). W odpowiedzi powinieneś wypisać jedną linię zawierającą take lub ignore. Wszystkie krawędzie w pierwszej rundzie zostaną podane dokładnie raz, a kolejność krawędzi jest wybierana jednostajnie losowo z $(n - 1)!$ możliwych permutacji.
W przypadku wyjścia w nieprawidłowym formacie, gra zakończy się natychmiast bez dalszych informacji od interaktora.
Ocena poprawności
Niech $M$ będzie zbiorem krawędzi wybranych przez Twoje rozwiązanie. Uznaje się to za dopuszczalne, jeśli żaden wierzchołek nie jest incydentny z więcej niż jedną wybraną krawędzią oraz $|M| = |M^*|$, gdzie $M^*$ jest dopasowaniem maksymalnym grafu.
Istnieje dokładnie 50 testów, z wyłączeniem testów przykładowych. Aby zaliczyć problem, Twoje rozwiązanie musi być poprawne we wszystkich testach, w tym w testach przykładowych.
Wszystkie losowania są gwarantowane jako ustalone przed otrzymaniem wyjścia rozwiązania. Losowość jest ustalona dla każdego testu poprzez ustalenie ziarna generatora liczb pseudolosowych.
Dostępne jest narzędzie testujące, które pomoże Ci opracować i przetestować Twoje rozwiązanie.
Przykład
Wejście 1 (Runda Prepare)
prepare 3 1 2 1 3
Wyjście 1 (Runda Prepare)
00
Wejście 2 (Runda Play)
play 3 00 1 3
Wyjście 2 (Runda Play)
take
Wejście 3 (Runda Play)
1 2
Wyjście 3 (Runda Play)
ignore
Uwagi
Wyjaśnienie przykładu 1: Ponieważ $|M^*| = 1$, wybranie dowolnej krawędzi jest dopuszczalne, a wskazówka może być dowolna.
Magically Marked Matching Master