Задача №115449. "Галактический Таймлайн"
В Далёкой Галактике в Далёком будущем всё еще популярны старые настольные игры. Гуманоид Хёмуль играет в «Галактический Таймлайн».
Как известно, в игре «Таймлайн» есть карточки, на которых указан год и событие, которое произошло в этот год. Карточки необходимо выложить последовательно так, чтобы порядок событий получился правильным: каждое следующее событие не может быть раньше предыдущего.
В Далёкой Галактике экономят бумагу, поэтому в «Галактическом Таймлайне» карточки для игры двусторонние — на каждой карточке написано по два года и события — по одному на каждой из сторон карточек.
У Хёмуля есть \(n\) карточек, которые он выкладывает на стеклянный стол. Хёмуль заметил, что если выкладывать двусторонние карточки на стеклянный стол, то таймлайн формируется с двух сторон: сверху стола из лицевых сторон карточек и снизу стола из оборотных.
Изначально все карточки выложены в произвольном порядке в ряд слева направо. Хёмуль может выбрать любую карточку на столе и перевернуть ее. Также Хёмуль может выбрать две любые карточки на столе и поменять их местами, не переворачивая ни одну из них.
Хёмулю стало интересно, можно ли такими действиями выложить карточки так, чтобы события шли в правильном порядке слева направо как сверху стола, так и снизу стола. Помогите ему это сделать или определите, что выложить карточки в правильном порядке с обеих сторон невозможно.
В первой строке вводится число \(n\) (\(1 \le n \le 10^5\)). Во второй строке вводятся \(n\) чисел \(a_i\) (\(1 \le a_i \le 10^9\)) — годы, написанные на лицевой стороне \(i\)-й карточки. В третьей строке вводятся \(n\) чисел \(b_i\) (\(1 \le b_i \le 10^9\)) — годы, написанные на обратной стороне \(i\)-й карточки.
Выведите информацию о карточках в том порядке, в котором их необходимо выложить.
В первой строке выведите \(n\) годов, находящихся на лицевой стороне карточек, во второй строке — \(n\) годов, находящихся на оборотной стороне карточек. Если выполнить цель игры невозможно, выведите \(-1\).
В первом примере Хёмуль может действовать, например, так. Сначала он переворачивает первую карту, затем переворачивает вторую карту. На столе оказываются выложены карты слева направо (лицевая и обратная сторона указаны через \(|\)): \(2|6\), \(4|8\), \(1|5\) и \(3|7\). Далее Хёмуль поменяет первую и третью карту, вторую и третью карту, третью и четвертую и получит правильный порядок с обеих сторон.
4 6 8 1 3 2 4 5 7
1 2 3 4 5 6 7 8
3 30 10 20 10 30 20
-1