Шестикутні палички#5702

Шестикутні палички

1 секунда

256 мегабайтів

Дуже складна

У цій задачі розглядається нескінченна шестикутна сітка. Сітка складається з однакових правильних шестикутних комірок, як показано нижче. На рисунку також показана система координат, яка використовується для ідентифікації кожної комірки. Кожна комірка сітки може бути або порожньою, або заблокованою.

Рисунок: Частина сітки

На цій сітці випадковим чином розміщено декілька паличок. Довжина кожної палички — одна "шестикутна одиниця", тобто її кінці розташовані у центрах сусідніх комірок. Ваше завдання — перемістити палички так, щоб утворити замкнений правильний шестикутник.

Нижче наведено ілюстрації із прикладами замкнених шестикутних фігур із паличок.

Вам надаються початкові координати паличок, розміщених на сітці. Також вказуються координати заблокованих комірок. За один хід можна виконати одну з наступних дій:

Обрати одну паличку та видалити її;
Обрати одну паличку та повернути її на $60$ градусів за чи проти годинникової стрілки навколо одного з кінців;
Обрати одну паличку та пересунути її вздовж її довжини на одну шестикутну одиницю.

Палички не можуть займати заблоковані комірки. Водночас дві палички можуть одночасно бути у тих самих комірках.

Розгляньмо наведений вище сценарій: перепона розташована у комірці з координатами $(1, 1)$ , а паличка з'єднує $(0, 0)$ і $(1, 0)$ . Чотири можливі ходи для цієї палички показано на рисунку.

Після всіх дій на сітці має утворитися замкнений правильний шестикутник, без зайвих паличок. Тобто на сітці повинно бути рівно $6 \times x$ 6 \times x паличок, де $x$ — додатне ціле число. Чи зможете ви зробити це за мінімальну кількість ходів?

Вхідні дані

Перший рядок містить ціле число $T$ ( $T < 50$ T < 50) — кількість тестів.

Кожен тест починається з невід'ємного числа $S$ ( $S < 9$ S < 9) — кількості паличок. Далі йдуть $S$ рядків, кожен із яких описує паличку у форматі $x_{1} y_{1} x_{2} y_{2}$ x_1\ y_1\ x_2\ y_2, тобто паличку від $(x_{1}, y_{1})$ (x_1, y_1) до $(x_{2}, y_{2})$ (x_2, y_2). Усі координати коректні, довжина кожної палички — одна шестикутна одиниця.

Наступний рядок містить невід'ємне ціле $B$ ( $B < 20$ B < 20) — кількість перепон. Потім йдуть $B$ рядків із координатами перепон у форматі $x_{1} y_{1}$ x_1\ y_1. Гарантується, що жодна перепона не перетинається з паличками. Всі координати (паличок і перепон) — цілі числа від $- 4$ до $4$ .

Примітка: сітка нескінченна. У підсумковому результаті шестикутник може виходити за межі відрізку $[- 4, 4]$ .

Вихідні дані

Для кожного тесту виведіть номер тесту та мінімальну кількість необхідних ходів. Якщо утворити шестикутник неможливо, виведіть impossible. Дотримуйтеся формату наведених прикладів вхідних та вихідних даних.

Приклади

Приклад 1