В небольшом классе ученики организовали игру «Тайный Санта». Каждый ученик зарегистрировался на сайте SecretSanta, где случайным образом получил имя того, кому нужно подарить подарок. Жеребьёвка завершилась успешно, и все участники узнали, кого им нужно поздравить.
Но внезапно появилась проблема: некоторые ученики решили стать плохишами и отказались дарить подарки. Перед праздником магическая сова принесла письмо с именами плохишей детей. Теперь праздник под угрозой, так как подарки могут оказаться у тех, кто их не заслуживает.
Ваша задача — перераспределить список дарителей и получателей подарков так, чтобы:
- Каждый хороший ребёнок дарил подарок только хорошему.
- Каждый плохиш дарил подарок только плохишу.
- Количество изменений в первоначальном списке было минимальным.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \leq t \leq 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$4 \leq n \leq 10^5$$$) — количество детей.
В следующей строке находятся $$$n$$$ чисел $$$p_i$$$ ($$$1 \leq p_i \leq n$$$, $$$p_i \neq i$$$). Каждое $$$p_i$$$ обозначает ребёнка, которому дарит подарок $$$i$$$-й ребенок. Гарантируется, что каждый ребенок получит только один подарок, и ни один ребенок не дарит подарок самому себе.
В следующей строке находится одно число $$$m$$$ ($$$2 \leq m \leq n - 2$$$) — количество плохишей.
В следующей строке находятся $$$m$$$ попарно различных чисел $$$a_i$$$ ($$$1 \leq a_i \leq n$$$) — список детей, которые решили не дарить подарки.
Гарантируется, что сумма $$$n$$$ по всем наборам входных данных не превосходит $$$10^5$$$.
В единственной строке выведите $$$n$$$ чисел $$$p_i$$$ — новый список, где каждое $$$p_i$$$ обозначает ребёнка, которому дарит подарок $$$i$$$-й ребенок.
Каждый ребенок согласно списку должен получить ровно один подарок, и ни один ребенок не должен дарить подарок самому себе.
Можно показать, что в указанных ограничениях это всегда возможно сделать.
363 4 2 1 6 544 3 2 566 1 4 2 3 533 2 663 4 2 1 6 533 5 6
6 4 2 5 3 1 4 3 6 5 1 2 2 4 5 1 6 3
Разберём первый набор входных данных первого теста:
 |
 |
