---
title: Hamilton
---

Розглянемо орієнтований граф з $n$ вершинами, пронумерованими $1,2,\dots,n$. Граф називається _турніром_, якщо між кожною парою вершин є рівно одне ребро в одному з двох напрямків. Тобто, для будь-якої пари різних вершин $u$ та $v$ існує або ребро з $u$ в $v$, або з $v$ в $u$.

Гамільтонів цикл — це послідовність $c_1, c_2, \dots, c_n$, що відвідує всі вершини та повертається до початку, рухаючись по ребрах графа. Для всіх $1 \le i \le n-1$ має існувати ребро з $c_i$ в $c_{i+1}$. Крім того, має існувати ребро з $c_n$ в $c_1$.

Ви можете побудувати довільний турнір з $n$ вершин. Після цього нумерацію вершин буде перемішано. Здійснюючи запити про напрямки ребер у перемішаному графі, чи зможете ви знайти гамільтонів цикл?

# Інтерактивність

Це інтерактивна задача. Спочатку зчитайте два цілих числа $n$ та $t$: кількість вершин та кількість тестів.

Далі виведіть $n$ рядків для опису турніру. У $u$-му з цих рядків виведіть $n$ символів "`0`" або "`1`". Символ "`1`" на позиції $v$ означає, що існує ребро з $u$ в $v$. Ребра з $u$ в саму себе бути не повинно.

Після цього слідують $t$ тестів. Кожен тест використовує той самий граф, який ви надали, але нумерацію перемішано і вона тримається в секреті градером. Ви можете зробити деяку кількість запитів, після чого маєте передати градеру гамільтонів цикл.

Щоб зробити запит, виведіть "`?` $u$ $v$", де $1 \le u,v \le n$ — різні вершини у перемішаному графі. Градер відповість "`>`", якщо ребро йде з $u$ в $v$, або "`<`", якщо ребро йде з $v$ в $u$.

Коли ви знайдете гамільтонів цикл, виведіть "`!`", а після нього $n$ цілих чисел $c_1, c_2, \dots, c_n$. Зверніть увагу, що числа $c_i$ мають відповідати перемішаній нумерації. Наступний тест починається одразу після того, як ви вивели відповідь.

Скрипт для тестування можна завантажити [тут](files/hamilton-test.py). На початку скрипта містяться інструкції з його використання.

# Обмеження

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

# Приклад взаємодії

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

_Пояснення:_ У першому тесті вершини випадково виявились перемішаними у початковому порядку, тому $1,2,3,4,5$ є гамільтоновим циклом.

У другому тесті номери вершин $1,2,3,4,5$ перемішано у $2,4,1,5,3$, у такому порядку. Послідовність $1,5,4,3,2$ дійсно є гамільтоновим циклом, оскільки $3,4,2,5,1$ був ним у початковому графі.

На рисунку нижче початковий граф зображено ліворуч, а перемішаний граф з другого тесту — праворуч. Два гамільтонових цикли виділено червоним.

![Візуалізація прикладу](files/example.svg "=420x")

# Оцінювання

У кожній підзадачі є лише один тестовий вхід з $t = 200$ тестами. У кожному тесті нумерацію графа перемішано рівномірно випадково. Якщо в одному тесті зроблено більше ніж $10^4$ запитів, результатом буде WRONG ANSWER.

Нехай $Q$ — середня кількість запитів, зроблених вашою програмою серед усіх тестів, що належать до підзадачі. Ви отримуєте бали за підзадачу, якщо $Q$ не перевищує вказаного обмеження.

| Підзадача | Обмеження | Бали    |
| :-----: | ----------- | :-------: |
| 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 ви отримуєте бали за наступною формулою:

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

Наприклад, якщо середня кількість запитів вашої програми становить $Q=1500$, ви отримуєте 1 бал за підзадачу. Якщо $Q=1000$, ви отримуєте 26 бал, а якщо $Q=750$, ви отримуєте 76 балів.
