F. Арсен и солдатики
ограничение по времени на тест
3 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Арсен командует отрядом из $$$n$$$ игрушечных солдат. Каждое утро и каждый вечер проводится построение. На каждом построении каждому солдату выдают ружье одного из $$$n$$$ видов.

Перед началом дня у Арсена есть два частично заполненных расписания: $$$a_1,\ldots,a_n$$$ и $$$b_1,\ldots,b_n$$$. Здесь $$$a_i$$$ — вид ружья, который получает $$$i$$$-й солдат на утреннем построении, а $$$b_i$$$ — вид ружья, который он получает на вечернем построении. Если $$$a_i$$$ или $$$b_i$$$ равно $$$-1$$$, это означает, что вид ружья на соответствующее построение ещё не назначен. Арсен может заменить каждое $$$-1$$$ любым числом от $$$1$$$ до $$$n$$$.

После того, как расписания выдачи ружей полностью определены, Арсен проводит еще один ритуал: он решает для каждого солдата, выдать ему мыло или нет. Формально, он создает бинарный массив $$$c$$$, где $$$c_i = 0$$$ или $$$c_i = 1$$$. Этот массив должен удовлетворять двум условиям баланса:

  • Для каждого вида ружья $$$k$$$ (от $$$1$$$ до $$$n$$$), среди всех солдат, которые получили ружье вида $$$k$$$ на утреннем построении, количество солдат с мылом ($$$c_i = 1$$$) должно совпадать с количеством солдат без мыла ($$$c_i = 0$$$).
  • Аналогично, для каждого вида ружья $$$k$$$, среди всех солдат, которые получили ружье вида $$$k$$$ на вечернем построении, также должно быть поровну солдат с мылом и без.

Помогите Арсену определить, можно ли так дозаполнить расписания $$$a$$$ и $$$b$$$ (заменив все $$$-1$$$ на числа от $$$1$$$ до $$$n$$$), чтобы существовал хотя бы один способ выдачи мыла (массив c), удовлетворяющий условиям баланса. Если это возможно, восстановите пример подходящих массивов $$$a$$$, $$$b$$$ и $$$c$$$.

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

Первая строка содержит целое число $$$n$$$ ($$$1 \le n \le 10^6$$$) — количество солдат.

Вторая строка содержит $$$n$$$ целых чисел $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le n$$$ или $$$a_i = -1$$$) — назначения ружей для утреннего построения.

Третья строка содержит $$$n$$$ целых чисел $$$b_1, b_2, \ldots, b_n$$$ ($$$1 \le b_i \le n$$$ или $$$b_i = -1$$$) — назначения ружей для вечернего построения.

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

В первой строке выведите «Yes», если можно дозаполнить массивы $$$a$$$ и $$$b$$$, чтобы пара массивов стала хорошей. В противном случае выведите «No».

Если ответ «Yes», выведите три дополнительные строки:

  • Во второй строке выведите $$$n$$$ целых чисел — полный массив $$$a$$$ после заполнения всех $$$-1$$$.
  • В третьей строке выведите $$$n$$$ целых чисел — полный массив $$$b$$$ после заполнения всех $$$-1$$$.
  • В четвертой строке выведите $$$n$$$ целых чисел ($$$0$$$ или $$$1$$$) — массив $$$c$$$, удовлетворяющий условиям баланса.

Если существует несколько возможных ответов, выведите любой из них.

Примеры
Входные данные
6
-1 1 -1 2 -1 2
1 -1 2 -1 2 -1
Выходные данные
YES
1 1 1 2 1 2 
1 1 2 1 2 1 
0 1 0 1 1 0
Входные данные
4
1 1 1 1
1 1 1 2
Выходные данные
NO