паро8

29.05.2023 08:24 •  Информатика

4. Не подпоследовательность Ограничение времени 2 секунды
Ограничение памяти 244Mb
Ввод стандартный ввод или input.txt
Вывод стандартный вывод или output.txt
Назовем последовательность X = (x1, x2, …, xt) подпоследовательностью другой последовательностиY = (y_1, y_2, …, y_s), если какие-то элементы (возможно ни одного) можно удалить из последовательности Y, чтобы получить последовательность X.

Например, последовательность (1, 2, 3, 2) является подпоследовательностью последовательности (1, 1, 2, 2, 1, 3, 2, 1), а последовательность (1, 2, 3, 1, 2) – нет.

Заданы две последовательности A = (a1, a2, …, am) и B = (b1, b2, …, bn), состоящие из целых чисел в диапазоне от 1 до k. Необходимо найти наименьшую по длине последовательность C = (c1, c2, …, cp), которая не являлась бы подпоследовательностью ни A, ни B. Элементы последовательности C также должны являться целыми числами в диапазоне от 1 до k.

Формат ввода
В первой строке стандартного ввода содержится число k – максимальное значение элемента последовательности (1 ≤ k ≤ 5 000).

Во второй строке содержится число m – длина первой последовательности А (1 ≤ m ≤ 5 000). В третьей строке содержатся m целых чисел в интервале от 1 до k – последовательность A.

В четвертой строке содержится число n – длина второй последовательности B (1 ≤ n ≤ 5 000). В пятой строке содержатся n целых чисел в диапазоне от 1 до k — последовательность B.

Формат вывода
В первой строке стандартного вывода необходимо вывести p – длину искомой последовательности. Во второй строке — саму последовательность C. Если последовательностей такой длины несколько, можно вывести любую из них.