Pamiętaj, aby po każdej operacji wyjścia opróżnić bufor standardowego wyjścia. Sposoby opróżniania bufora dla różnych języków programowania:

• W C/C++ użyj fflush(stdout) lub cout.flush();
• W Javie użyj System.out.flush();
• W Pythonie użyj sys.stdout.flush().

Po naprawie sieci energetycznej, holograficzny projektor w końcu uruchomił się pomyślnie. Wraz z zapadającym zmrokiem, półprzezroczyste hologramy w powietrzu stały się niezwykle barwne i olśniewające. Gdy wszystko było gotowe, małe T i małe S oficjalnie rozpoczęły nocne wydarzenie, zapraszając wszystkich do wspólnego udziału w starannie przygotowanej grze świateł i cieni, testującej współpracę w duecie – „Rozszyfrowywanie strumieni światła”.

Wiązki światła w centrum placu przeplatają się, powoli zbiegając się w jedno drzewo świetlne. Drzewo składa się z pewnej liczby lewitujących węzłów świetlnych połączonych liniami strumieni światła, tworząc czystą strukturę drzewa. Na początku gry żadna z linii nie jest podświetlona, więc uczestnicy nie mogą zaobserwować żadnej z nich. Karuha, osoba obsługująca system, najpierw pokaże uczestnikowi stojącemu przed konsolą pewną tajemniczą liczbę. Następnie linie strumieni światła będą zapalać się jedna po drugiej, a uczestnik musi w momencie pojawienia się każdej linii zdecydować o kierunku jej przepływu. Partner stojący po drugiej stronie sceny musi, opierając się jedynie na ostatecznym kształcie drzewa, dokładnie odgadnąć tę tajemniczą liczbę.

Jako uczestnicy uroczystości, Neri i Noir postanowili współpracować, aby ukończyć to wyzwanie.

W tym wyzwaniu Neri będzie stać przed konsolą. Karuha najpierw poda jej dwie dodatnie liczby całkowite $n, s$ ($1 \le s \le 2^{n-1}$), oznaczające odpowiednio liczbę węzłów świetlnych w drzewie oraz tajemniczą liczbę.

Następnie Karuha będzie kolejno zapalać $n - 1$ linii strumieni światła, a Neri musi w momencie zapalenia każdej z nich natychmiast określić kierunek jej przepływu.

Dla Noir, stojącej po drugiej stronie głównej sceny, zaobserwuje ona ostateczny kształt drzewa wypełnionego strumieniami światła. Musi ona, na podstawie kierunków przepływu tych linii, odgadnąć tajemniczą liczbę $s$ przekazaną Neri.

Aby wygrać to wyzwanie, Neri i Noir muszą wcześniej ustalić strategię, która zapewni im pomyślne przejście tej gry sprawdzającej ich wzajemne porozumienie.

Szczegóły implementacji

Twój program zostanie uruchomiony dwukrotnie. W pierwszym uruchomieniu wcielisz się w rolę Neri, decydując o kierunku przepływu każdej linii, a w drugim wcielisz się w rolę Noir, odgadując tajemniczą liczbę na podstawie ostatecznego kształtu drzewa. Interaktor będzie wcielał się w rolę Karuha, przekazując informacje do Twojego programu.

W pierwszym uruchomieniu Twój program najpierw otrzyma liczbę węzłów świetlnych $n$ oraz tajemniczą liczbę $s$, a następnie kolejno otrzyma $n - 1$ zapalających się linii strumieni światła. Twój program musi natychmiast wyprowadzić do biblioteki interakcyjnej określony kierunek przepływu, aby przekazać informacje do drugiego uruchomienia.

W drugim uruchomieniu Twój program otrzyma od interaktora informacje z pierwszego uruchomienia, czyli kierunki przepływu linii strumieni światła na drzewie, a następnie musi na podstawie tych informacji odgadnąć tajemniczą liczbę $s$ przekazaną Neri.

Wejście i wyjście

Każdy zestaw testowy zawiera wiele przypadków testowych. Pierwsza linia wejścia zawiera dwie dodatnie liczby całkowite $T, r$ ($1 \le T \le 10^4, r \in \{1, 2\}$), oznaczające liczbę przypadków testowych oraz numer etapu. Dla każdego przypadku testowego:

• Jeśli $r = 1$:

  • Pierwsza linia zawiera dwie dodatnie liczby całkowite $n, s$ ($3 \le n \le 30, 1 \le s \le 2^{n-1}$), oznaczające odpowiednio liczbę węzłów świetlnych w drzewie oraz tajemniczą liczbę.
  • Następnie kolejno zapalane jest $n - 1$ linii strumieni światła. Przy każdym zapaleniu linii, wejście zawiera dwie dodatnie liczby całkowite $u, v$ ($1 \le u < v \le n$), oznaczające dwa węzły połączone linią. Musisz natychmiast wyprowadzić jedną linię zawierającą dwie dodatnie liczby całkowite $u, v$ lub $v, u$, oznaczające kierunek przepływu odpowiednio od $u$ do $v$ lub od $v$ do $u$.
  • Uwaga: Dla każdej linii strumienia światła musisz wyprowadzić kierunek jej przepływu i opróżnić bufor standardowego wyjścia, zanim będziesz mógł otrzymać kolejną linię.

• Jeśli $r = 2$:

  • Pierwsza linia zawiera jedną dodatnią liczbę całkowitą $n$ ($3 \le n \le 30$), oznaczającą liczbę węzłów świetlnych w drzewie.
  • Następnie w $n - 1$ liniach podawane są dwie dodatnie liczby całkowite $u, v$ ($1 \le u, v \le n$), oznaczające linię strumienia światła przepływającą od węzła $u$ do węzła $v$.
  • Musisz natychmiast wyprowadzić jedną linię z jedną dodatnią liczbą całkowitą, oznaczającą odgadniętą tajemniczą liczbę $s$.
  • Uwaga:
    • Kolejność danych wejściowych w pojedynczym teście może różnić się od tej z pierwszego uruchomienia.
    • Dla tego samego przypadku testowego kolejność linii strumieni światła w dwóch uruchomieniach może być inna, ale numery węzłów pozostają niezmienione.
    • Dla każdego przypadku testowego musisz wyprowadzić odgadniętą liczbę $s$ i opróżnić bufor standardowego wyjścia, zanim będziesz mógł otrzymać kolejny przypadek testowy.

Przykład

Wejście 1

2 1
7 21
1 6
3 5
2 4
3 4
1 2
6 7

Wyjście 1

6 1
3 5
4 2
3 4
1 2
7 6

Wejście 2

2 2
9 8
1 2
5 6
6 7
1 4
3 5
8 3
3 4
7 1
2 1
4 2
6 1
3 5
3 4
7 6

Wyjście 2

59
21

Uwagi

Rysunek 1: Pierwszy zestaw danych testowych

Rysunek 2: Drugi zestaw danych testowych

Szczegóły testowania

Dostarczony skrypt treedir_testing_tool.py może pomóc w lokalnym testowaniu w celu weryfikacji poprawności programu i wydrukowania szczegółowego procesu interakcji. Podczas testowania umieść ten skrypt w tym samym katalogu, co Twój skompilowany plik wykonywalny, a następnie uruchom w terminalu następujące polecenie:

python3 treedir_testing_tool.py [--quiet] <data_file> <program> <arguments>

Gdzie:

• -q, --quiet jest opcjonalnym parametrem. Po jego użyciu skrypt testowy nie będzie już drukował szczegółowego procesu interakcji.
• data_file to ścieżka do pliku wejściowego dostarczonego dla skryptu testowego. Plik ten musi spełniać następujący format:
  • Pierwsza linia zawiera dwie nieujemne liczby całkowite $T, seed$, reprezentujące odpowiednio liczbę zestawów testowych oraz ziarno losowości użyte do przemieszania kolejności testów i kolejności krawędzi w drzewie. Jeśli określono $seed = 0$, oznacza to brak przemieszania.
  • Format każdego zestawu danych jest dokładnie taki sam, jak format wejściowy „pierwszego uruchomienia” opisany powyżej.
• program to ścieżka do Twojego skompilowanego pliku wykonywalnego.
• arguments to dodatkowe argumenty wiersza poleceń przekazywane do tego pliku wykonywalnego.

Uwaga:

1. Implementacja interakcji skryptu testowego nie jest w pełni identyczna z rzeczywistą biblioteką oceniającą, wyniki testów lokalnych nie są rozstrzygające i służą jedynie jako odniesienie na etapie debugowania.
2. Skrypt testowy przeprowadza jedynie podstawową weryfikację formatu danych w data_file, nie sprawdza, czy poprawnie spełniają one ograniczenia zadania (np. nie sprawdza, czy $s$ spełnia ograniczenie $1 \le s \le 2^{n-1}$, ani czy linie strumieni światła poprawnie tworzą drzewo).
3. Skrypt testowy nie monitoruje zużycia czasu i pamięci przez program, więc nie może być użyty do sprawdzenia, czy spełnione są ograniczenia czasowe i pamięciowe zadania.