И вот Зельда зашла в новую локацию, и перед ней внезапно появилось $$$n$$$ противников: засада Нулла, не иначе. Для удобства в бою Зельда дала каждому противнику свой номер, кроме этого она быстро выяснила вид каждого противника. Вид противника с номером $$$i$$$ равен $$$k_i$$$, при этом у разных противников может быть один и тот же вид.
Поскольку на Зельду напали внезапно, она не смогла основательно подготовиться к сражению. Однако, благодаря наблюдениям за сражениями Линка, Зельда смогла вспомнить, что некоторые противники образуют между собой связи, делающие их уязвимыми к атакам. Значит, при правильной стратегии можно победить всех одним ударом!
К несчастью, Зельда не очень внимательно следила за сражениями Линка, поэтому смогла заметить лишь $$$n - 1$$$ связь и тот факт, что любые два противника связаны напрямую или косвенно (по цепочке).
Из-за частых конфликтов с отцом принцесса не очень сильна в комбинированных атаках, которые поражают многих врагов за раз. А именно, она может выбрать два вида противников $$$k_i$$$ и $$$k_j$$$, после чего выстрелить в какого-либо врага. Как только выстрел долетает до врага,
Иными словами, за одну атаку Зельда может поразить множество связанных напрямую или косвенно врагов, каждый из которых принадлежит одному из выбранных ей до атаки видов.
Зельда хочет победить за наименьшее количество атак, так как она хочет поскорее прийти на помощь Линку. Она неплохо стреляет, но не уверена, какие виды противников выбирать для каждой атаки и кого ей нужно атаковать. Помогите Зельде с планом битвы, чтобы у неё точно получилось спасти Линка и весь Хайрул.
В первой строке ввода дано одно число $$$n$$$ — количество противников Зельды ($$$1 \leq n \leq 2 \cdot 10^5$$$).
Во второй строке перечислены $$$n$$$ целых чисел $$$k_1, \ldots, k_n$$$ — виды противников ($$$1 \leq k_i \leq n$$$).
В $$$i$$$-й из следующих $$$n - 1$$$ строках даны два целых числа $$$v_i$$$ и $$$u_i$$$, означающие, что атака по противнику $$$v_i$$$ перейдёт на противника $$$u_i$$$ и наоборот ($$$1 \le v_i, u_i \le n$$$; $$$v_i \neq u_i$$$). Гарантируется, что такие связи косвенно связывают любую пару противников.
В первой строке необходимо вывести минимальное количество атак $$$a$$$.
В следующих $$$a$$$ строках необходимо вывести список противников, пораженных каждой атакой. Строка, описывающая $$$i$$$-ю атаку, должна начинаться с числа $$$n_i$$$ — количества поверженных противников, за которым через пробел должны быть перечислены $$$n_i$$$ номеров поверженных противников от $$$1$$$ до $$$n$$$.
Каждый враг должен быть выведен ровно один раз.
66 6 2 1 6 41 64 31 23 52 3
3 4 1 2 3 5 1 4 1 6
54 5 4 4 54 52 55 13 5
1 5 1 2 5 3 4