2023-2024 ICPC NERC (NEERC), Чемпионат Кыргызстана
A. Иррациональность
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Для целого числа $$$D$$$ найдите координаты всех целочисленных точек $$$(x, y)$$$ c неотрицательными координатами таких, что Евклидово расстояние от $$$(x, y)$$$ до начала координат $$$(0, 0)$$$ равно $$$D \sqrt{2}$$$.

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

В единственной строке содержится целое число $$$D$$$ $$$(1 \le D \le 10^6)$$$ — параметр задачи.

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

В первой строке выведите целое число $$$K$$$ $$$(0 \le K \le 10^7)$$$ — количество найденных точек.

В следующих $$$K$$$ строках необходимо вывести через пробел по два целых числа $$$x_i$$$, $$$y_i$$$ $$$(0 \le x_i \le y_i \le 2 \cdot D)$$$ — координаты $$$i$$$-й найденной точки.

Точки должны быть отсортированы по возрастанию координаты $$$x$$$ $$$(x_1 \lt x_2 \lt \dots \lt x_k)$$$.

Примеры
Входные данные
5
Выходные данные
2
1 7
5 5
Входные данные
9
Выходные данные
1
9 9
Входные данные
85
Выходные данные
5
17 119
35 115
41 113
71 97
85 85
Примечание

Определение: Евклидово расстояние от точки $$$(x, y)$$$ до точки $$$(a, b)$$$ вычисляется по формуле $$$\sqrt{(x - a)^2 + (y - b)^2}$$$.

Первый тестовый пример.

Для $$$D = 5$$$ существует две точки, удовлетворяющие условиям задачи:

$$$5 \sqrt{2} = \sqrt{25} \cdot \sqrt{2} = \sqrt{50}$$$:

  • $$$(1, 7)$$$: $$$\sqrt{1^2 + 7^2} = \sqrt{50}$$$;
  • $$$(5, 5)$$$: $$$\sqrt{5^2 + 5^2} = \sqrt{50}$$$.

Второй тестовый пример.

Для $$$D = 9$$$ существует только одна точка $$$(9, 9)$$$, удовлетворяющая условию задачи.

B. Занавеска
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Алихан решил повесить новую занавеску. Занавеска держится на $$$N$$$ крючках вдоль всей гардины.

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

Поэтому Алихан придерживается следующей стратегии:

  • Сначала он одновременно вешает занавеску на крючки $$$1$$$ и $$$N$$$.
  • Далее, пока есть хотя бы один неиспользованный крючок:
    • Алихан ищет непрерывный отрезок из неиспользованных крючков.
      • Среди таких отрезков Алихан выбирает отрезок наибольшей длины.
      • Среди отрезков наибольшей длины Алихан выбирает самый левый.
    • Пусть Алихан выбрал отрезок с $$$L$$$-го по $$$R$$$-й крючок, всего на нём $$$S = R - L + 1$$$ крючков. Алихан старается подвесить занавеску в центр отрезка.
      • Если количество крючков $$$S$$$ нечетное, то Алихан вешает занавеску на крючок $$$\frac{L + R}{2}$$$.
      • Иначе Алихан одновременно вешает занавеску на крючки $$$\frac{L + R - 1}{2}$$$ и $$$\frac{L + R + 1}{2}$$$.

После того, как Алихан повесил занавеску, его заинтересовало, а на каком шаге были использованы крючки под номерами $$$A_1, A_2, \dots, A_Q$$$.

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

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

В первой строке через пробел даны два целых числа $$$N$$$ и $$$Q$$$ $$$(1 \le N \le 10^{18}; 1 \le Q \le 10^4)$$$  — количество крючков на гардине и количество интересующих Алихана крючков.

Во второй строке через пробел записаны $$$Q$$$ различных целых чисел $$$A_1, A_2, \dots, A_Q$$$ $$$(1 \le A_i \le N)$$$  — интересующие Алихана крючки.

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

В единственной строке через пробел выведите $$$Q$$$ чисел $$$T_i$$$  — на каком шаге был использован крючок $$$A_i$$$.

Примеры
Входные данные
10 10
1 10 2 9 3 8 4 7 5 6
Выходные данные
1 1 5 8 3 4 6 7 2 2
Входные данные
9876543210 3
3456789120 5678912340 7891234560
Выходные данные
5798205414 6764530002 3863296238
Примечание

Первый тестовый пример.

На гардине $$$N = 10$$$ крючков.

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

  1. На первом шаге вешаем на крайние крючки $$$1$$$ и $$$10$$$;
  2. На втором шаге есть один отрезок крючков $$$[2; 9]$$$, вешаем на центральные крючки $$$5 = \frac{2 + 9 - 1}{2}$$$ и $$$6 = \frac{2 + 9 + 1}{2}$$$;
  3. На третьем шаге есть два отрезка $$$[2; 4]$$$, $$$[7; 9]$$$:
    • оба имеют длину $$$3$$$, выбираем самый левый $$$[2; 4]$$$;
    • вешаем на центральный крючок $$$3 = \frac{2 + 4}{2}$$$;
  4. На четвертом шаге есть три отрезка $$$[2;2]$$$, $$$[4;4]$$$, $$$[7;9]$$$:
    • выбираем отрезок $$$[7;9]$$$, так как он имеет наибольшую длину $$$3$$$ (длина остальных $$$1$$$);
    • вешаем на центральный крючок $$$8 = \frac{7 + 9}{2}$$$;
  5. Остались крючки $$$2$$$, $$$4$$$, $$$7$$$ и $$$9$$$ — вешаем на самый левый $$$2$$$;
  6. Остались крючки $$$4$$$, $$$7$$$ и $$$9$$$ — вешаем на самый левый $$$4$$$;
  7. Остались крючки $$$7$$$ и $$$9$$$ — вешаем на самый левый $$$7$$$;
  8. Остался единственный крючок $$$9$$$ — вешаем на него и заканчиваем процесс.

C. Делимость на 2023
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Даны две различные десятичные цифры $$$A$$$ и $$$B$$$.

Выведите любое целое положительное число $$$N$$$, составленное только из этих цифр (или одной из них), которое нацело делится на $$$2023$$$.

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

В единственной строке даны через пробел два целых числа $$$A$$$ и $$$B$$$ $$$(0 \le A \lt B \le 9)$$$ — разрешенные десятичные цифры.

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

Выведите целое положительное число $$$N$$$ $$$(1 \le N \lt 10^{100})$$$, которое

  • нацело делится на $$$2023$$$;
  • состоит только из цифр $$$A$$$ и $$$B$$$ (или одной из них).

Число $$$N$$$ не должно иметь ведущих нулей (старшая цифра должна быть отлична от $$$0$$$).

Если корректных ответов несколько — выведите любой из них.

Примеры
Входные данные
2 3
Выходные данные
322322332332
Входные данные
5 7
Выходные данные
777775577775

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

Чтобы скоротать время в долгой поездке, Айзат придумала следующую игру.

В начале игры у Айзат есть клетчатый лист бумаги размером $$$W$$$ клеток в ширину и $$$H$$$ клеток в высоту (всего $$$W \times H$$$ клеток).

За один ход Айзат может разорвать лист на две части по границе клеток (по вертикали или по горизонтали). Из двух получившихся листов Айзат оставляет в игре лист с большим количеством клеток.

Айзат интересуется, за какое минимальное количество ходов она сможет получить лист, на котором будет не более чем $$$S$$$ клеток.

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

В первой строке находится единственное целое число $$$T$$$ $$$(1 \le T \le 10^3)$$$ — количество игр, в которые Айзат успеет сыграть в поездке.

Следующие $$$T$$$ строк содержат через пробел три целых числа $$$W_i$$$, $$$H_i$$$, $$$S_i$$$ $$$(1 \le W_i, H_i \le 10^9; 1 \le S_i \le 10^{18})$$$ — количество клеток в ширину и высоту на $$$i$$$-м листе, а также верхняя граница для количества клеток в конце $$$i$$$-й игры.

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

Выведите через пробел $$$T$$$ чисел $$$D_i$$$ — минимальное количество ходов, необходимое для того, чтобы из листа размером $$$W_i \times H_i$$$ клеток получился лист, содержащий не более $$$S_i$$$ клеток.

Примеры
Входные данные
3
3 25 2
6 6 50
9 7 19
Выходные данные
6 0 2
Входные данные
4
123456789 567891234 912345678
912345678 123456789 567891234
567891234 912345678 123456789
987654321 876543219 123456789123456789
Выходные данные
27 28 32 3
Примечание

Первый тестовый пример

Айзат сыграет в три игры:

  1. Из листа размером $$$3 \times 25$$$ можно получить лист размером не более чем в $$$2$$$ клетки, например, следующим образом:
    • $$$3 \times 25$$$ $$$\rightarrow$$$ $$$3 \times 14$$$ (отбросили $$$3 \times 11$$$);
    • $$$3 \times 14$$$ $$$\rightarrow$$$ $$$3 \times 7$$$ (отбросили $$$3 \times 7$$$);
    • $$$3 \times 7$$$ $$$\rightarrow$$$ $$$3 \times 4$$$ (отбросили $$$3 \times 3$$$);
    • $$$3 \times 4$$$ $$$\rightarrow$$$ $$$2 \times 4$$$ (отбросили $$$1 \times 4$$$);
    • $$$2 \times 4$$$ $$$\rightarrow$$$ $$$2 \times 2$$$ (отбросили $$$2 \times 2$$$);
    • $$$2 \times 2$$$ $$$\rightarrow$$$ $$$1 \times 2$$$ (отбросили $$$1 \times 2$$$).

    Возможны и другие варианты ходов, но быстрее, чем за шесть ходов получить лист из $$$2$$$ или менее клеток нельзя.

  2. Лист размером $$$6 \times 6$$$ содержит $$$36$$$ клеток, что уже меньше, чем $$$50$$$. Поэтому игра заканчивается без единого разрыва.
  3. Лист размером $$$9 \times 7$$$ можно привести к листу из $$$18 \le 19$$$ клеток следующим образом:
    • $$$9 \times 7$$$ $$$\rightarrow$$$ $$$9 \times 4$$$ (отбросили $$$9 \times 3$$$);
    • $$$9 \times 4$$$ $$$\rightarrow$$$ $$$9 \times 2$$$ (отбросили $$$9 \times 2$$$).

    Можно показать, что никакая другая последовательность из двух ходов не может привести к листу, содержащему не более 19 клеток.

E. Цифровизация
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

При рождении каждому теленку присваивается идентификационный номер. Этот номер вместе с номерами отца и матери теленка записывается в паспорте теленка.

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

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

  • повторяющиеся идентификационные номера в рамках одной породы;
  • один и тот же идентификационный номер в одном паспорте фигурирует как отец какого-то теленка, а в другом – как мать (или даже в одном и том же паспорте);
  • теленок оказался родителем cебя и/или своего отца и/или своей матери.
Входные данные

Первая строка содержит единственное натуральное число $$$N$$$ $$$(N \le 100)$$$– количество пород коров (и ящиков).

Далее следуют описания $$$N$$$ ящиков, описание $$$i$$$-го ящика состоит из двух строк:

  • в первой строке описания идёт одно целое число $$$P_i$$$ $$$(1 \le P_i \le 10^4)$$$ — количество паспортов в $$$i$$$-м ящике.
  • во второй строке описания дано через пробел $$$P_i$$$ троек целых чисел $$$A_{ij}$$$ $$$B_{ij}$$$ $$$C_{ij}$$$ $$$(1 \le A_{ij}, B_{ij}, C_{ij} \le 10^9)$$$ — паспортные данные $$$j$$$-го телёнка в $$$i$$$-м ящике: идентификатор теленка, его отца и матери соответственно.

Гарантируется, что общее количество паспортов $$$\sum{P_i} \le 10^5$$$.

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

Выведите $$$N$$$ строк, $$$i$$$-я строка содержит (без кавычек)

  • «CORRECT», если данные в $$$i$$$-м ящике корректны;
  • «INCORRECT», если данные в $$$i$$$-м ящике содержат одну из описанных в условии ошибок.
Примеры
Входные данные
3
2
5 4 7 4 6 5
2
5 4 7 3 4 6
3
1 2 3 1 3 2 3 4 5
Выходные данные
INCORRECT
CORRECT
INCORRECT
Входные данные
3
3
5 4 7 3 4 6 1 3 5
3
5 4 7 3 4 6 1 4 5
3
5 4 7 3 4 6 1 5 4
Выходные данные
CORRECT
CORRECT
INCORRECT
Примечание

Первый тестовый пример

  • Первый ящик — теленок $$$5$$$ имеет отца $$$4$$$, но в то же время является матерью $$$4$$$;
  • Третий ящик — теленок $$$1$$$ указан два раза, а также $$$2$$$ и $$$3$$$ выступают поочередно отцом и матерью.

Второй тестовый пример

  • Третий ящик — бык $$$4$$$ указан сначала отцом теленка $$$5$$$, а потом матерью теленка $$$1$$$.

F. Справедливый разрез
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Близнецам подарили треугольник на день рождения. Но они ходят в разные школы и каждый хочет показать свой подарок одноклассникам как можно скорее. Поэтому они хотят разрезать треугольник на две части справедливо.

Разрез считается справедливым, если площади двух фигур, полученных путем разреза, имеют равную площадь.

Для упрощения близнецы расположили треугольник следующим образом:

  1. Первая вершина — начало координат $$$(0, 0)$$$;
  2. Вторая — точка $$$(a, b)$$$;
  3. Третья — точка $$$(c, 0)$$$.

Также родители близнецов уже зафиксировали начало разреза — точку $$$P$$$ на одной из сторон треугольника.

Ваша задача — найти координаты точки $$$Q$$$ на одной из сторон треугольника такой, что отрезок $$$PQ$$$ разделяет треугольник на две фигуры равной площади.

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

Первая строка содержит через пробел три целых числа $$$a$$$, $$$b$$$ и $$$c$$$ $$$(0 \le a, b, c \le 10^6)$$$ — координаты второй вершины и $$$X$$$-координата третьей вершины треугольника соответственно.

Во второй строке записаны через пробел два целых числа $$$px$$$ и $$$py$$$ $$$(0 \le px, py \le 10^6)$$$ — координаты начала разреза $$$P$$$.

Гарантируется, что треугольник имеет ненулевую площадь.

Гарантируется, что точка $$$P$$$ лежит на одной из сторон треугольника.

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

Если не существует точки $$$Q$$$, удовлетворяющей условию — выведите через пробел без кавычек «-1 -1».

В ином случае выведите через пробел два вещественных числа $$$qx$$$ и $$$qy$$$ $$$(0 \le qx, qy \le 10^6)$$$ — координаты точки $$$Q$$$.

Ответ будет засчитан, если абсолютная и/или относительная погрешность координат не превосходит $$$10^{-4}$$$.

Примеры
Входные данные
3 7 8
5 0
Выходные данные
2.40000000 5.60000000
Входные данные
5 10 12
4 8
Выходные данные
7.50000000 0.00000000
Входные данные
3 4 5
5 0
Выходные данные
1.50000000 2.00000000
Входные данные
17 31 49
23 0
Выходные данные
18.84615385 29.21153846
Примечание

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

Пример Для вывода числа $$$z$$$ с $$$6$$$ знаками после запятой можно воспользоваться следующими командами:

  • C++: std::cout « std::fixed « std::setprecision(6) « z;

    (Требуются <iostream>, <iomanip>);

  • Java: System.out.printf(Locale.US, "%.6f", z);
  • Python: print(f'{z:.6f}').

Первый тестовый пример.

В первом примере точка Q имеет координаты $$$(2.4, 5.6)$$$.

Удвоенная площадь всего треугольника равна $$$7 \cdot 8 = 56$$$.

Удвоенная площадь синего треугольника после разреза равна $$$5.6 \cdot 5 = 28$$$.

Разрез выглядит подобным образом

Второй тестовый пример.

Во втором примере точка Q имеет координаты $$$(7.5, 0.0)$$$.

Удвоенная площадь всего треугольника равна $$$10 \cdot 12 = 120$$$.

Удвоенная площадь синего треугольника после разреза равна $$$8 \cdot 7.5 = 60$$$.

Третий тестовый пример.

В третьем примере точка Q имеет координаты (1.5, 2.0).

Удвоенная площадь всего треугольника равна $$$4 \cdot 5 = 20$$$.

Удвоенные площади синего и красного треугольников после разреза равны $$$2.0 \cdot 5 = 10$$$.

Последний тестовый пример.

G. Найти слона
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Это интерактивная задача — ваша программа будет обмениваться данными с программой жюри через стандартный ввод и вывод (консоль).

Айбек агай спрятал Слона на шахматной доске $$$8 \times 8$$$. Вы очень хотите узнать его координаты.

Столбцы на шахматной доске обозначаются латинской заглавной буквой от $$$A$$$ до $$$H$$$, а строки — целым числом от $$$1$$$ до $$$8$$$. Например, клетка $$$D7$$$ расположена в $$$4$$$-м столбце и $$$7$$$-й строке.

Чтобы найти координаты Слона, вы можете задать Айбек агаю не более 10 раз следующий вопрос:

«За какое минимальное количество ходов Слон достигнет столбца $$$X_1$$$ и строки $$$Y_1$$$?

После вопросов вам необходимо вывести позицию, на которой предположительно располагается Слон.

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

Обратите внимание, что

  • Любое ваше сообщение должно завершаться переводом строки.
  • После вывода каждого сообщения ваша программа должна очищать потоковый буфер, чтобы выведенная вами информация дошла до программы жюри:
    • C++: cout « endl (перевод строки + очистка буфера), cout.flush() или fflush(stdout);
    • Java: System.out.println() (перевод строки + очистка буфера), System.out.flush();
    • Python: print() (перевод строки + очистка буфера), stdout.flush().
    • Pascal: flush(output).
  • При решении на С++ не отключайте синхронизацию cin/cout.
Протокол взаимодействия

Все координаты столбцов должны выводиться только заглавными буквами.

Вопрос задаётся в формате $$$\textbf{?}$$$ $$$X_1Y_1$$$ $$$(A \le X_1 \le H$$$, $$$1 \le Y_1 \le 8)$$$ — вопросительный знак и координаты клетки из вопроса.

Всего вы можете задать вопрос не более 10 раз.

В ответ на вопрос программа жюри выводит целое число $$$K$$$ :

  • $$$K = -1$$$: Слон не может достигнуть клетки $$$X_1$$$$$$Y_1$$$.
  • Иначе $$$K$$$ равно количеству ходов от позиции Слона до клетки $$$X_1$$$$$$Y_1$$$.

Окончательный ответ выводится в формате $$$\textbf{!}$$$ $$$X_RY_R$$$ $$$(A \le X_R \le H$$$, $$$1 \le Y_R \le 8)$$$ — восклицательный знак и предполагаемые координаты Слона.

После вывода окончательного ответа ваша программа обязательно должна завершиться.

Пример
Входные данные
2
-1
1
0
Выходные данные
? B6
? F3
? H6
? G5
! G5
Примечание

Определение: шахматная фигура «Слон» за один ход может переместиться на любую клетку по диагонали.

Формально, если Слон стоит на клетке $$$X$$$$$$Y$$$, то он может переместиться в клетку $$$U$$$$$$V$$$ только в случае, если $$$|U - X| = |V - Y|$$$.

Первый тестовый пример.

Айбек агай спрятал Слона на клетке G5.

  • От клетки G5 до B6 можно добраться только за два хода — или через клетку D8, или через E3, так как Слон ходит только по диагоналям.
  • До клетки F3 из G5 никак не добраться, так как Слон ходит только по клеткам одного и того же цвета.
  • До клетки H6 Слон добирается за один ход.
  • До своей позиции Слону не надо делать ходов, поэтому ответ на вопрос равен $$$0$$$.

H. Равномерное кодирование
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Компания Naudio планирует создание и выпуск нового производительного процессора для обработки аудио-данных. Набор команд процессора должен содержать $$$K$$$ команд.

Каждая команда процессора — двоичная строка некоторой фиксированной длины $$$Len$$$. Вам поручено определить кодировку каждой из $$$K$$$ команд, то есть определить их двоичный вид, соблюдая следующие условия:

  1. (Запатентованная фишка) Длина $$$Len$$$ должна быть четной;
  2. (Корректность работы) Все команды должны быть различны между собой;
  3. (Контроль качества передачи) Каждая команда должна содержать одинаковое число единичных бит;
  4. (Равномерный отвод тепла) Количество строк, содержащих каждый бит, должно отличаться не более чем на $$$1$$$.

    Формально, пусть $$$i$$$ и $$$j$$$ $$$(1 \leq i, j \leq len)$$$ — номера каких-то бит в команде. Тогда $$$|cnt_k(i) - cnt_k(j)| \leq 1$$$ для любой пары $$$i, j$$$.

    Здесь $$$cnt_k(i)$$$ определяется как количество команд, в которых $$$i$$$-й бит был равен единице.

  5. (Оптимизация памяти) Среди всех возможных кодировок, удовлетворяющих условиям выше, выберите ту, в которой длина $$$Len$$$ минимально возможная.
Входные данные

В первой строке входные данных содержится одно целое число $$$T$$$ ($$$1 \leq T \leq 10$$$) — количество прототипов процессора.

Каждая из следующих $$$T$$$ строк состоит из одного целого числа $$$K_i$$$ ($$$1 \leq K_i \leq 10^4$$$) — требуемого количества команд в наборе команд $$$i$$$-го прототипа процессора Naudio.

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

Для $$$i$$$-го прототипа выведите:

  • В первой строке одно целое четное число $$$Len$$$ $$$(2 \le Len \le 100)$$$  — минимальную длину, которую можно использовать для построения $$$K_i$$$ различных команд, удовлетворяющих всем условиям;
  • Во второй строке через пробел выведите $$$K_i$$$ двоичных строк $$$S_j$$$ $$$(|S_j| = Len)$$$ — различные команды длины $$$Len$$$.

Если корректных ответов несколько, выведите любой.

Гарантируется, что ответ всегда существует в заданных ограничениях задачи.

Пример
Входные данные
3
1
2
3
Выходные данные
2
01
2
01 10
4
1110 1101 0111
Примечание

Первый прототип

В данном случае необходима одна команда.

Минимальная подходящая длина $$$Len$$$ равна $$$2$$$ (т.к. она обязана быть четной).

Всего возможно четыре варианта:

  • 00
  • 01
  • 10
  • 11

Можно вывести любую из них.

Второй прототип

Длина и набор возможных команд аналогичен первому прототипу.

В то же время подходит только пара команд 01 и 10 (в любом порядке), так как любая другая пара команд будет различаться по количеству единичных бит.

Третий прототип.

В данном случае длины $$$2$$$ уже не хватит, поэтому $$$Len = 4$$$.

Каждая из использованных команд содержит ровно $$$3$$$ единичных бита.

Рассмотрим, сколько команд содержат каждый бит:

  • $$$count(1) = 2$$$ — команды 1110 и 1101;
  • $$$count(2) = 3$$$ — команды 1110, 1101 и 0111;
  • $$$count(3) = 2$$$ — команды 1110 и 0111;
  • $$$count(4) = 2$$$ — команды 1101 и 0111.

Видно, что количество команд с каждым битом отличается не более, чем на 1.

I. Игра на дереве
ограничение по времени на тест
1 секунда
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Айбек и Айгуль играют в игру на дереве. Напомним, что дерево это связный граф без циклов. Дерево состоит из $$$n$$$ $$$(n \geq 2)$$$ вершин. Первым ходит Айбек - он выбирает любую вершину дерева, обозначим ее $$$u$$$. После чего ходит Айгуль и выбирает любую другую вершину дерева, обозначим ее $$$v$$$. После того, как оба игрока сделали свой выбор, случайно равновероятно выбирается какая-то одна из вершин дерева $$$w$$$ и затем:

  • Если $$$d(u, w) \lt d(v, w)$$$ — то Айбек объявляется победителем;
  • Если $$$d(u, w) \gt d(v, w)$$$ — то Айгуль объявляется победительницей;
  • Если $$$d(u, w) = d(v, w)$$$ — то объявляется ничья.

Здесь $$$d(a, b)$$$ — это расстояние между двумя вершинами дерева, то есть количество ребер на простом пути между $$$a$$$ и $$$b$$$. Айбек не очень хорош в играх на деревьях, поэтому помогите ему найти такую вершину, при выборе которой он максимизирует свою вероятность выигрыша. Если же таких вершин несколько, найдите вершину с минимальным номером.

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

В первой строке входных данных содержится одно целое число $$$t$$$ $$$(1 \leq t \leq 10^3)$$$ — количество раундов игры, в которую будут играть Айбек и Айгуль.

Далее следуют описания каждого раунда игры — в первой строке содержится целое число $$$n$$$ $$$(2 \leq n \leq 2\cdot10^5)$$$ — число вершин в дереве.

В следующих $$$n - 1$$$ строках, описывающих раунд, содержится по 2 целых числа $$$u_i$$$ и $$$v_i$$$ $$$(1 \leq u_i, v_i \leq n, u_i \neq v_i)$$$ — ребра дерева.

Гарантируется, что граф из каждого раунда игры образует структуру дерева.

Также гарантируется, что сумма $$$n$$$ по всем входными данными не превосходит $$$2\cdot10^5$$$

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

Для каждого раунда игры выведите одно целое число — номер вершины дерева, которую следует выбрать Айбеку, чтобы максимизировать свою вероятность выиграть. Если существует несколько таких вершин, то выведите вершину с наименьшим номером.

Пример
Входные данные
2
5
1 4
4 3
4 2
2 5
2
1 2
Выходные данные
4
1
Примечание
На картинке выше изображен граф из первого раунда игры первого набора входных данных. Как легко заметить, ни одна из вершин 1, 3, 5 не является оптимальной для Айбека, потому что тогда Айгуль возьмет себе её соседа. В таком случае Айбек победит только тогда, когда будет выбрана его вершина. Вероятность того, что будет выбрана его вершина  — 1/5. При выборе между вершинами 2 и 4 можно показать, что вершина 4 выгоднее. Действительно, если взять вершину 2, то Агуль выгодно взять вершину 4, и тогда её вероятность выиграть  — 1/3. Если же взять вершину 4, то Айгуль не может сделать свою вероятность выиграть выше 1/2.
На картинке выше изображен граф из второго раунда игры первого набора выходных данных. Из симметрии видно, что нет разницы, какую вершину взять  — 1-ю или 2-ю. Но так как из всех подходящих вершин требуется вывести вершину с наименьшим номером, то ответом является 1.