A. Фишки на графе
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Вам предоставили граф, состоящий из $$$n$$$ вершин, пронумерованных целыми числами от $$$1$$$ до $$$n$$$, соединенных $$$n+m$$$ ребрами. Первые $$$n$$$ ребер соединяют соседние по номерам вершины, то есть $$$i$$$-е ребро соединяет $$$i$$$-ю и $$$(i+1)$$$-ю вершины, а $$$n$$$-е соединяет $$$n$$$-ю и $$$1$$$-ю вершины. В некоторых вершинах расположены $$$n-2$$$ фишки, пронумерованные целыми числами от $$$1$$$ до $$$n-2$$$, причем ни в одной вершине не может быть более одной фишки.

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

Ваша задача заключается в том, чтобы определить последовательность ходов, чтобы в результате фишки оказались на требуемых позициях. Обратите внимание, что минимизировать количество ходов не требуется.

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

Каждый тест состоит из нескольких наборов входных данных. Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 20$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

В первой строке каждого набора входных данных задано два целых числа $$$n$$$ и $$$m$$$ ($$$4 \le n \le 100$$$, $$$1 \le m \le 2\,000$$$) — количество вершин и дополнительных ребер соответственно.

Во второй строке задано $$$n-2$$$ целых числа $$$a_i$$$ ($$$1 \le a_i \le n$$$, $$$a_i \ne a_j$$$ для $$$i \ne j$$$), где $$$i$$$-е число означает начальную позицию $$$i$$$-й фишки.

В третьей строке задано $$$n-2$$$ целых числа $$$b_i$$$ ($$$1 \le b_i \le n$$$, $$$b_i \ne b_j$$$ для $$$i \ne j$$$), где $$$i$$$-е число означает требуемую позицию $$$i$$$-й фишки.

В следующих $$$m$$$ строках задано по два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — номера вершин, соединенных ребром. Гарантируется, что полученный граф не содержит кратных ребер и петель.

Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превышает $$$100$$$.

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

Для каждого набора входных данных в первой строке выведите единственное целое число $$$k$$$ ($$$k \ge 0$$$) — количество ходов. В следующих $$$k$$$ строках выведите по два целых числа $$$c_i$$$ и $$$p_i$$$ ($$$1 \le c_i \le n - 2$$$, $$$1 \le p_i \le n$$$) — номер фишки и вершина, в которую ее требуется переместить на $$$i$$$-м ходу соответственно.

Суммарное количество ходов по всем наборам входных данных не должно превышать $$$2 \cdot 10^6$$$. Гарантируется, что такой ответ всегда существует.

Пример
Входные данные
1
4 1
1 3
2 1
2 4
Выходные данные
3
2 4
1 2
2 1