Телефонная сеть
Компания связи планирует построить новую телефонную сеть в городе. Цель состоит в том, чтобы каждый житель мог связаться с любым другим. Однако, прямые соединения между каждой парой людей невозможны, поэтому компания использует многоуровневую сеть.
Каждый сетевой коммутатор на уровне j обозначается как S(j). Коммутатор S(0) имеет один вход, один выход и кабель, соединяющий их. Коммутатор S(j) для j > 0 имеет 2^j входов, 2^j выходов и состоит из двух коммутаторов S(j-1). Вход i коммутатора S(j) (0 ≤ i < 2^j) соединяется с входами i mod 2^{j-1} каждого из двух коммутаторов S(j-1). Аналогично, выход i коммутатора S(j) соединяется с выходами i mod 2^{j-1} каждого из двух коммутаторов S(j-1).
Соединения между коммутатором S(j) и двумя коммутаторами S(j-1), из которых он состоит.
Мы рассматриваем сеть с одним коммутатором S(n) на внешнем уровне. Можно доказать, что любой вход и выход коммутатора S(n) имеет уникальный путь к любому из коммутаторов S(0). Таким образом, любой вход S(n) может быть соединен с любым из его выходов, и путь определяется уникально через конкретный коммутатор S(0).
Коммутаторы S(0), принадлежащие коммутатору S(n), нумеруются от 0 до 2^{n-1}. i-й коммутатор S(0) определяется следующим образом: число i записывается в двоичной системе как b_{n-1} b_{n-2} ... b_0. Это определяет путь от входа S(n) к i-му коммутатору S(0) через следующую процедуру: для каждого j, b_j = 0 указывает, что путь продолжается к первому коммутатору S(j), а b_j = 1 — ко второму. Независимо от выбранного входа S(n), путь всегда приводит к одному и тому же коммутатору S(0), которому присвоен номер i. См. рисунок ниже для примера нумерации.
Иногда требуется несколько соединений одновременно. Чтобы избежать помех, каждый вход и выход всех коммутаторов S(j) (0 ≤ j ≤ n) может быть использован не более чем одним соединением. Дано множество запросов на соединение, можете ли вы определить пути для каждого запроса так, чтобы они не пересекались?
Входные данные
Первая строка содержит положительное целое число: количество тестов, не более 100. Для каждого теста:
Одна строка с двумя целыми числами n (1 ≤ n ≤ 16) и m (1 ≤ m ≤ 2^n): уровень внешнего коммутатора и количество запросов на соединение.
m строк, каждая с двумя целыми числами a_i и b_i (0 ≤ a_i, b_i < 2^n). Каждая строка представляет запрос на соединение от входа номер a_i коммутатора S(n) к выходу номер b_i. Гарантируется, что числа a_i и b_i попарно различны.
Выходные данные
Для каждого теста:
Одна строка с m целыми числами s_1, ..., s_m, где s_i — это номер коммутатора S(0), через который устанавливается соединение входа a_i с выходом b_i.
Пути соединения должны быть непересекающимися. Вы можете вывести любое допустимое решение, и гарантируется, что хотя бы одно решение существует.
Подсказка
Возможная схема соединения для второго примера, с выделенными жирным шрифтом используемыми кабелями.
Примечание: Задача со специальным судьей, вы можете получить "Неправильный ответ", если вывод в неправильном формате.