Це інтерактивна задача (де ваша програма взаємодіє з програмою журі через ввід та вивід).
У королівстві Дюлок, Лорд Фаркуад розвиває мережу веж для моніторингу кожного куточка своєї землі. У нього є карта веж та доріг, що їх з’єднують, утворюючи неорієнтований простий граф G=(V,E), де кожна вежа — це вершина, а кожна дорога — це ребро між двома вежами. Однак Фаркуад хвилюється, що деякі частини Дюлока можуть бути ізольовані, що зробить неможливим доступ до кожної вежі з будь-якої іншої.
Щоб забезпечити повну зв’язність, він доручає вам перевірити, чи є його мережа з’єднаною. Проте є одна умова: вам дозволено обмежений доступ до інформації про граф.
Ви можете робити запити про мережу, щоб перевірити її зв’язність. Запит дозволяє вибрати підмножину веж і отримати кількість веж, що не належать і напряму з’єднані з хоча б однією вежею з . Тобто, query(S) = |N(S) \setminus S|, де S \subseteq V і N(S) = \{x \vert \exists y \in S \text{ such that } (x, y) \in E\}.
Ваше завдання — ефективно використовувати ці запити, щоб перевірити, чи мережа є зв’язною.
Чи можете ви допомогти Лорду Фаркуаду підтвердити безпеку його королівства, перевіривши, що кожна вежа досяжна з будь-якої іншої в мережі Дюлока?
У першому рядку задано одне ціле число — кількість веж в кололівстві Дюлок.
Після зчитування числа починається взаємодія. Ви можете робити запити вигляду: "? s" (без лапок), де — це бінарний рядок довжини , такий що символ s_i є 1 якщо i \in S і 0 в іншому випадку. Після запиту, зчитайте одне число — відповідь на ваш запит.
1 \leq |V| \leq 200.
Ви можете зробити не більше ніж 3500 запитів.
Коли ви визначите чи є зв’язним чи ні, виведіть відповідь у форматі: "! x" (без лапок), де це 1 якщо є зв’язним і 0 в іншому випадку.
Приклад
Приклад 1
У першому прикладі, |V| = 4, G = (V, E), V = \{1, 2, 3, 4\}, E = \{(1, 2), (2, 3), (3, 4), (2, 4)\}.
Input | Output | Description |
| Дано . | |
| Запит про підмножину . | |
| Відповідь журі 2. | |
| Запит про підмножину . | |
| Відповідь журі 2. | |
| Запит про підмножину . | |
| Відповідь журі 2. | |
| Алгоритм виявив, що G є зв’язним. |
У другому прикладі, |V| = 2, G = (V, E), V = \{1, 2\}, E = \emptyset.
Input | Output | Description |
| Дано . | |
| Запит про підмножину . | |
| Відповідь журі 0. | |
| Запит про підмножину . | |
| Відповідь журі 0. | |
| Алгоритм виявив, що G не є зв’язним. |