D. Батарейки
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача. Обратитесь к разделу «Протокол взаимодействия» ниже для лучшего понимания.

Есть $$$n$$$ ($$$2 \le n \le 40$$$) батареек, пронумерованных $$$1, 2, \ldots, n$$$. Некоторые из них работают, а другие — нет. Пусть $$$a$$$ — количество работающих батареек. Гарантируется, что $$$\mathbf{a \geq 2}$$$.

Вам дано $$$n$$$, но не $$$a$$$.

Есть фонарик, в который можно вставить две батарейки, и он включается только тогда, когда обе батарейки работают. Батарейки были перемешаны, и вы не знаете, какие из них работают, а какие нет. Вы можете выбрать две батарейки и попробовать их в фонарике.

Ваша задача — найти пару работающих батареек. Однако вы беспокоитесь о том, чтобы не сломать фонарик, поэтому хотите ограничить количество попыток.

Таким образом, вам нужно найти пару работающих батареек, используя не более чем $$$\left \lfloor \frac{n^2}{a} \right \rfloor$$$ попыток.

Взаимодействие адаптивно. Это означает, что работоспособность батарейки $$$i$$$ ($$$1 \le i \le n$$$) не фиксирована и может изменяться в процессе взаимодействия. Однако гарантируется, что всегда существует конфигурация из $$$a$$$ работающих батареек, которая согласуется с информацией, которую вы получили до данного момента.

Входные данные

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$2 \le n \le 40$$$) — количество батареек.

Гарантируется, что сумма значений $$$n$$$ по всем наборам входных данных не превосходит $$$200$$$.

Протокол взаимодействия

Взаимодействие для каждого набора входных данных начинается с чтения целого числа $$$n$$$.

Чтобы сделать запрос, выведите одну строку с двумя целыми числами в следующем формате:

  • $$$\mathbb{u}\,\mathbb{v}$$$ ($$$1 \leq u, v \leq n$$$ и $$$u \neq v$$$) — индексы батареек, которые вы хотите протестировать.

После этого прочитайте одно целое число $$$x$$$, указывающее, включился ли фонарик после вставки этих $$$2$$$ батареек. Если $$$x=1$$$, фонарик включился. В противном случае, если $$$x=0$$$, фонарик не включился.

После нахождения пары батареек, которые включают фонарик, взаимодействие набора входных данных считается успешным, и оно завершится. После этого взаимодействие продолжается со следующим набором входных данных.

После вывода каждого запроса не забудьте вывести перевод строки и сбросить буфер вывода$$$^{\text{∗}}$$$. В противном случае вы получите вердикт Решение «зависло».

На любом шаге взаимодействия, если вы считали $$$-1$$$ вместо корректных данных, ваше решение должно немедленно завершиться. Это означает, что ваше решение получит вердикт Неправильный ответ из-за некорректного запроса или любой другой ошибки. Если программа не завершится, вы можете получить любой вердикт, так как ваша программа продолжит чтение из закрытого потока.

Взломы

Взломы для этой задачи отключены.

$$$^{\text{∗}}$$$Чтобы сбросить буфер вывода, используйте:

  • fflush(stdout) или cout.flush() в C++;
  • sys.stdout.flush() в Python;
  • смотрите документацию для других языков.
Пример
Входные данные
2
3

0

1
10

0

0

1
Выходные данные


1 2

2 3


1 2

1 3

1 4
Примечание

В первом наборе входных данных есть $$$3$$$ батарейки. Работают только батарейки $$$2$$$ и $$$3$$$. Следовательно, $$$a=2$$$, и нам нужно найти пару работающих батареек за $$$\lfloor \frac{n^2}{a} \rfloor = \lfloor \frac{3^2}{2} \rfloor = 4$$$ запроса.

Взаимодействие проходит следующим образом:

УчастникЖюриОбъяснение
 —$$$3$$$В этом наборе входных данных $$$3$$$ батарейки
$$$1$$$   $$$2$$$$$$0$$$Решение спрашивает, включают ли батарейки $$$1$$$ и $$$2$$$ фонарик. Жюри отвечает, что нет.
$$$2$$$   $$$3$$$$$$1$$$Решение спрашивает, включают ли батарейки $$$2$$$ и $$$3$$$ фонарик. Жюри отвечает, что да. Пара работающих батареек найдена, поэтому взаимодействие первого набора входных данных завершается успешно.

Во втором наборе входных данных есть $$$10$$$ батареек. Работают только батарейки $$$1$$$, $$$4$$$, $$$6$$$ и $$$9$$$. Следовательно, $$$a=4$$$, и нам нужно найти пару работающих батареек за $$$\lfloor \frac{n^2}{a} \rfloor = \lfloor \frac{10^2}{4} \rfloor = 25$$$ запросов.

Взаимодействие проходит следующим образом:

УчастникЖюриОбъяснение
 —$$$10$$$В этом наборе входных данных $$$10$$$ батареек.
$$$1$$$   $$$2$$$$$$0$$$Решение спрашивает, включают ли батарейки $$$1$$$ и $$$2$$$ фонарик. Жюри отвечает, что нет.
$$$1$$$   $$$3$$$$$$0$$$Решение спрашивает, включают ли батарейки $$$1$$$ и $$$3$$$ фонарик. Жюри отвечает, что нет.
$$$1$$$   $$$4$$$$$$1$$$Решение спрашивает, включают ли батарейки $$$1$$$ и $$$4$$$ фонарик. Жюри отвечает, что да. Пара работающих батареек найдена, поэтому взаимодействие первого набора входных данных завершается успешно.

Обратите внимание, что переносы строк в примерах ввода и вывода добавлены для ясности и не присутствуют в реальном взаимодействии.