Велика стіна#2084
Король Людовик має двох синів, які ненавидять один одного. Побоюючись, що після його смерті країна буде зруйнована жахливими війнами, він вирішує розділити свої володіння на дві частини, кожною з яких буде правити один із синів. Він саджає їх у міста і та бажає побудувати мінімальну кількість сегментів стіни так, щоб жодного шляху з міста до міста не існувало.
Королівство можна зобразити у вигляді прямокутника розміром m \times n. Деякі клітини містять гори, які непрохідні, інші — вільно прохідні. Окрім цього, деякі клітини придатні для будівництва стін, а на деяких будівництво неможливе.
Переміщення країною дозволене лише між клітинами, які мають спільну сторону, за умови, що жодна з них не містить гори чи сегмента стіни.
Перший рядок містить цілі числа та (1 \leq m, n \leq 50). Другий рядок містить числа та , де 0 \leq k, l, k + l \leq m \cdot n - 2. Тут — кількість клітин з горами, а — кількість клітин, придатних для будівництва стін. На горах стіни будувати не можна. Наступні рядків містять координати клітин з горами: x_i та y_i. Далі йдуть рядків з координатами клітин, на яких можна будувати стіни: x_j та y_j. Останні два рядки містять координати міст (x_A, y_A) та (x_B, y_B). Усі ці k+l+2 клітини різні. Гарантується, що 1 \leq x_i, x_j, x_A, x_B \leq m та 1 \leq y_i, y_j, y_A, y_B \leq n.
У першому рядку виведіть мінімальну кількість сегментів стіни , які потрібно збудувати. У наступних рядках виведіть можливий набір координат клітин для будівництва стін.
Якщо зробити це неможливо, виведіть лише .
Приклад 1