---
title: Hamilton
---

Rozważmy graf skierowany z $n$ wierzchołkami ponumerowanymi $1,2,\dots,n$. Graf nazwiemy _turniejem_, jeżeli między każdą parą wierzchołków istnieje krawędź w pewną stronę. Dokładniej, dla dowolnej pary różnych wierzchołków $u$ i $v$, istnieje krawędź z $u$ do $v$ lub z $v$ do $u$.

Cyklem Hamiltona nazwiemy ciąg $c_1, c_2, \dots, c_n$, który odwiedza wszystkie wierzchołki i kończy tam, gdzie zaczął, podążając krawędziami grafu. Dla wszystkich $1 \le i \le n-1$, musi istnieć krawędź z $c_i$ do $c_{i+1}$. Ponadto, musi istnieć krawędź z $c_n$ do $c_1$.

Możesz dowolnie skonstruować graf będący turniejem złożonym z $n$ wierzchołków. Następnie, wierzchołki są przenumerowane. Możesz zadawać zapytania o skierowanie krawędzi w przenumerowanym grafie. Czy potrafisz znaleźć cykl Hamiltona?

# Interakcja

To jest zadanie interaktywne. Twój program powinien najpierw wczytać dwie liczby całkowite $n$ i $t$ oznaczające liczbę wierzchołków i przypadków testowych.

Następnie wypisz $n$ wierszy opisujących graf będący turniejem. W $u$-tym z tych wierszy wypisz $n$ znaków "`0`" lub "`1`". Znak "`1`" na pozycji $v$ oznacza, że istnieje krawędź z $u$ do $v$. Nie może istnieć krawędź z $u$ do siebie samego.

Dalej jest $t$ przypadków testowych. Każdy z nich korzysta z tego samego grafu, który podałeś, ale wierzchołki są przenumerowywane. Możesz zrobić pewną liczbę zapytań, po których powinieneś podać cykl Hamiltona.

Aby zrobić zapytanie wypisz "`?` $u$ $v$", gdzie $1 \le u,v \le n$ są różnymi wierzchołkami w przenumerowanym grafie. Grader odpowie "`>`" jeżeli krawędź jest skierowana z $u$ do $v$ lub "`<`" jeżeli krawędź jest skierowana z $v$ do $u$.

Kiedy znajdziesz cykl Hamiltona, wypisz "`!`" a następnie $n$ liczb całkowitych $c_1, c_2, \dots, c_n$. Zauważ, że liczby $c_i$ powinny odpowiadać przenumerowanym wierzchołkom. 
Kolejny przypadek testowy rozpocznie się od razu po wypisaniu przez Ciebie odpowiedzi.

Skrypt do testowania można pobrać [tutaj](files/hamilton-test.py). Na początku skryptu znajduje się instrukcja jak go używać.

# Ograniczenia

- $4 \le n \le 500$
- $1 \le t \le 200$

# Przykładowa interakcja

```
5 2

01110
00101
00010
01001
10100

? 1 2
>
? 2 3
>
? 3 4
>
? 4 5
>
? 5 1
>
! 1 2 3 4 5

? 1 2
<
? 1 5
>
? 4 3
>
? 4 5
<
? 3 2
>
! 1 5 4 3 2
```

_Wyjaśnienie_: Wierzchołki nie zostały przenumerowane, więc $1,2,3,4,5$ to cykl Hamiltona.

W drugim przypadku testowym wierzchołki $1,2,3,4,5$ są przenumerowane do $2,4,1,5,3$, w tej kolejności. Ciąg $1,5,4,3,2$ to cykl Hamiltona, ponieważ $3,4,2,5,1$ był cyklem Hamiltona w oryginalnym grafie.

Na obrazku poniżej, oryginalny graf jest pokazany po lewej, a przenumerowany z drugiego przypadku po prawej. Oba cykle Hamiltona są pokazane na czerwono.

![Przykładowa wizualizacja](files/example.svg "=420x")

# Ocenianie

W każdym podzadaniu jest tylko jeden test z $t = 200$ przypadkami testowymi. W każdym przypadku testowym numeracja wierzchołków jest przenumerowana losowo z rozkładem jednostajnym. Zrobienie ponad $10^4$ zapytań skutkuje werdyktem WRONG ANSWER.

Niech $Q$ to średnia liczba zapytań zrobionych przez Twój program pośród wszystkich przypadków testowych w podzadaniu. Za podzadanie dostaniesz punkty, jeżeli $Q$ nie przekroczy podanego limitu.

| Podzadanie | Ograniczenia | Punkty    |
| :-----: | ----------- | :-------: |
| 1       | $n = 4, Q \le 12$ | [score=1] |
| 2       | $n = 50, Q \le 1225$ | [score=2] |
| 3       | $n = 50, Q \le 300$ | [score=3] |
| 4       | $n = 500, Q \le 1500$ | 1&ndash;76 |

W podzadaniu 4 punkty otrzymujesz zgodnie z poniższym wzorem:

$$
\left\lfloor \frac {25\,000} {\max(750, Q) - 500} - 24 \right\rfloor
$$

Przykładowo, jeżeli średnia liczba zapytań zrobionych przez Twój program to $Q=1500$, dostaniesz 1 punkt za to podzadanie. Jeżeli $Q=1000$, dostaniesz 26 punktów, a jeżeli $Q=750$, dostaniesz 76 punktów.
