Telephone Network
Компанія телефонного зв'язку планує створити нову телефонну мережу в місті. Її мета — забезпечити можливість кожному мешканцю міста зателефонувати будь-якому іншому. Однак, прямі з'єднання між кожною парою осіб неможливі, тому компанія використовує багатошарову мережу.
Позначимо мережевий комутатор у шарі 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+1) до першого комутатора S(j), з яким він безпосередньо з'єднаний, а b_j = 1 вказує, що шлях продовжується до другого комутатора S(j). Зверніть увагу, що незалежно від того, який вхід 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.
Шляхи з'єднання повинні бути неперетинними. Ви можете вивести будь-яке допустиме рішення, і ви можете припустити, що існує принаймні одне допустиме рішення.
Підказка
Можлива схема з'єднання для другого зразкового випадку, з використаними кабелями, виділеними жирним шрифтом.
Примітка: Спеціальна задача з перевіркою, ви можете отримати "Неправильна відповідь", якщо вивід у неправильному форматі.