---
title: Hamiltonas
---

Nagrinėkime kryptinį grafą su $n$ viršūnių, sunumeruotų $1,2,\dots,n$. Šis grafas vadinamas _turnyriniu_, jei tarp kiekvienos dviejų viršūnių poros yra lygiai viena tam tikros krypties briauna. Kitais žodžiais, kiekvienai skirtingų viršūnių porai $u$ ir $v$, egzistuoja briauna iš $u$ į $v$ arba iš $v$ į $u$.

Hamiltono ciklas yra seka $c_1, c_2, \dots, c_n$, kuri, eidama grafo briaunomis, aplanko visas viršūnes ir grįžta į pradinę viršūnę. Kiekvienam $1 \le i \le n-1$, privalo egzistuoti briauna iš $c_i$ į $c_{i+1}$. Taip pat privalo egzistuoti briauna iš $c_n$ į $c_1$.
 
Jūs turite sukonstruoti turnyrinį $n$ viršūnių grafą. Tada viršūnių tvarka yra išmaišoma. Ar galite surasti Hamiltono ciklą išmaišytame grafe, atlikdami briaunų krypčių užklausas?

# Bendravimas

Ši užduotis yra interaktyvi. Pradžioje nuskaitykite du sveikuosius skaičius $n$ ir $t$ – viršūnių ir testų skaičių.

Tada išveskite $n$ eilučių, apibūdinančių turnyrinį grafą. $u$-je iš šių eilučių išveskite $n$ simbolių "`0`" arba "`1`". Simbolis "`1`" pozicijoje $v$ reiškia, kad egzistuoja briauna iš viršūnės $u$ į $v$. Briaunos tarp $u$ ir savęs yra negalimos.

Po to seka $t$ testų. Kiekvienas testas naudoja jūsų pateiktą grafą su išmaišyta viršūnių numeracija, kuri yra žinoma tik vertintojui. Jūsų programa gali pateikti užklausų, po kurių turite išvesti Hamiltono ciklą.

Norėdami atlikti užklausą, išveskite "`?` $u$ $v$", kur $1 \le u,v \le n$ yra skirtingos išmaišyto grafo viršūnės. Vertintojas atsakys "`>`", jei briauna yra iš $u$ į $v$, arba "`<`", jei briauna yra iš $v$ į $u$.

Radę Hamiltono ciklą, išveskite "`!`" su $n$ sveikųjų skaičių $c_1, c_2, \dots, c_n$. Atkreipkite dėmesį, kad skaičiai $c_i$ turi atitikti išmaišytą viršūnių tvarką. Kitas testas prasideda iš karto po atsakymo išvedimo.

Testavimo programą galite parsisiųsti [čia](files/hamilton-test.py). Skripto pradžioje yra instrukcijos, kaip juo naudotis.

# Ribojimai

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

# Bendravimo pavyzdys

```
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
```

_Paaiškinimas:_ gavosi taip, kad pirmo testo išmaišyta viršūnių tvarka yra lygi pradinei viršūnių tvarkai, todėl $1,2,3,4,5$ yra Hamiltono ciklas.

Antrame teste pradinė viršūnių tvarka $1,2,3,4,5$ yra išmaišyta į tvarką $2,4,1,5,3$. Seka $1,5,4,3,2$ yra Hamiltono ciklas, nes $3,4,2,5,1$ buvo Hamiltono ciklas pradiniame grafe.

Žemiau esančioje iliustracijoje pradinis grafas yra pavaizduotas kairėje, o antro testo išmaišytas grafas pateiktas dešinėje. Abu Hamiltono ciklai paryškinti raudona spalva.

![Pavyzdžio iliustracija](files/example.svg "=420x")

# Vertinimas

Kiekvieną dalinę užduotį sudaro tik viena įvestis su $t = 200$ testų. Kiekviename teste viršūnių tvarka yra išmaišyta tolygiai atsitiktinai. Jei vienam testui atliksite daugiau nei $10^4$ užklausų, atsakymas bus neįskaitytas (WRONG ANSWER).

Pažymėkime $Q$ jūsų programos vienos dalinės užduoties visų testų metu atliktų užklausų vidurkį. Už dalinę užduotį gausite taškus, jei $Q$ yra ne didesnis negu duotas limitas.

| Dalinė užduotis | Ribojimai | Taškai    |
| :-----: | ----------- | :-------: |
| 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 |

4-os dalinės užduoties taškų skaičius bus paskaičiuotas pagal šią formulę:

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

Pavyzdžiui, jei jūsų programos atliktas užklausų skaičiaus vidurkis yra $Q=1500$, gausite 1 tašką iš šios dalinės užduoties. Jei $Q=1000$, gausite 26 tašką, ir jei $Q=750$, gausite 76 taškus.
