дп

Дан связный неориентированный граф из \(n\) вершин. Изначально в \(i\)-й вершине (\(1 \leq i \leq n\)) записано целое положительное число \(a_i\). Боб хочет за минимальное время попасть из вершины с номером \(1\) в вершину с номером \(n\). Время, которое требуется, чтобы пройти по ребру, соединяющему вершины \(u\) и \(v\), составляет \(|a_u - a_v|\).

Перед тем, как начать обход, Боб может поменять значение \(a_i\) в не более чем \(k\) вершинах. За какое минимальное время можно попасть из \(1\) в \(n\), поменяв значения оптимальным образом?

Формат входных данных
В первой строке входных данных записаны три целых числа \(n, m, k\) (\(2 \leq n \leq 2000, 1 \leq m \leq 2000, 0 \leq k \leq 10\)) — количество вершин графа, количество ребер и параметр \(k\) соответственно.

В следующей строке содержится \(n\) целых чисел \(a_i\) (\(0 \leq a_i \leq 10^9\)) — начальные значения в вершинах.

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

Формат выходных данных
В единственной строке выходных данных выведите ответ на задачу.

Примечание

В первом тестовом примере одним из оптимальных способов получения ответа может быть изменение значения в вершине с номером \(2\) с числа \(15\) на число \(3\). В таком случае путь \(1 \rightarrow 2 \rightarrow 5 \rightarrow 6\) будет иметь стоимость \(|1 - 3| + |3 - 4| + |4 - 10| = 9\).

Второй пример отличается от первого лишь значением \(k\). Во втором примере можно поменять значения записанные в вершинах с номерами \(2, 3, 6\) на \(1\). Тогда стоимостью пути станет \(|1 - 1| + |1 - 1| + |1 - 1| + |1 - 1| = 0\).

Последовательность \(X = [x_1, x_2, \ldots, x_t]\) является подпоследовательностью последовательности \(Y = [y_1, y_2, \ldots, y_s]\), если можно удалить некоторые (возможно ни одного) элементы \(Y\), чтобы получить \(X\). Иначе говоря, существует последовательность индексов \(1 \le i_1 < i_2 < \ldots < i_t \le s\), что \(x_j = y_{i_j}\) для всех \(j\) от \(1\) до \(s\). Например, последовательность \([1, 2, 3, 2]\) является подпоследовательностью последовательности \([\mathbf{1}, 1, \mathbf{2}, 2, 1, \mathbf{3}, \mathbf{2}, 1]\), а последовательность \([1, 2, 3, 1, 2]\) "— нет.

Рассмотрим две последовательности \(A = [a_1, a_2, \ldots, a_m]\) и \(B = [b_1, b_2, \ldots, b_n]\), состоящие из целых чисел от \(1\) до \(k\).

Требуется найти минимальную по длине последовательность \(C = [c_1, c_2, \ldots, c_p]\), которая не являлась бы подпоследовательностью ни \(A\) ни \(B\). Элементы последовательности \(C\) также должны являться целыми числами от \(1\) до \(k\).

Формат входных данных
Первая строка ввода содержит число \(k\) — максимальное значение элемента последовательности (\(1 \le k \le 5\,000\)).

Вторая строка содержит число \(m\) — длину последовательности \(A\) (\(1 \le m \le 5\,000\)). Третья строка содержит \(m\) целых чисел от \(1\) до \(k\) — последовательность \(A\).

Четвертая строка содержит число \(n\) — длину последовательности \(B\) (\(1 \le n \le 5\,000\)). Пятая строка содержит \(n\) целых чисел от \(1\) до \(k\) — последовательность \(B\).

Формат выходных данных
На первой строке выведите \(p\) — длину искомой последовательности. На второй строке выведите последовательность \(C\). Если оптимальных ответов несколько, выведите любой из них.