Это сложная версия задачи. Единственное отличие между версиями — ограничение на \(k\). Вы можете делать взломы, только если обе версии задачи решены.
Вам дано неориентированное дерево из \(n\) вершин. На каждой вершине \(v\) записано значение \(a_v\). Вы должны ответить на запросы, связанные с деревом.
Вам дано \(q\) запросов. В каждом запросе дается \(5\) целых чисел, \(u_1, v_1, u_2, v_2, k\). Обозначим количество вершин со значением \(c\) на пути \(u_1 \rightarrow v_1\) как \(x_c\), а количество вершин со значением \(c\) на пути \(u_2 \rightarrow v_2\) как \(y_c\). Пусть существует \(z\) таких значений \(c\), что \(x_c \neq y_c\). Тогда выведите любые \(\min(z, k)\) таких значений в любом порядке.
Выходные данные
Для каждого запроса выведите ответ на отдельной строке. Для каждого запроса сначала выведите \(\min(z, k)\), а затем в той же строке выведите любые \(\min(z, k)\) значений, которые встречаются разное количество раз на путях, в любом порядке.
Примечание
Для \(1\) запроса первый путь: \(1 \rightarrow 2 \rightarrow 4\), на котором встречается мультинабор значений \(\{5, 2, 4\}\). На втором пути \(4 \rightarrow 2 \rightarrow 5\) мы имеем мультинабор \(\{4, 2, 3\}\). Два числа — \(3\) и \(5\) встречаются разное количество раз, поэтому мы выводим оба числа.
Во \(2\) запросе пути совпадают, поэтому выводим \(0\).
В \(3\) запросе у нас те же пути, что и в запросе \(1\), но нам нужно вывести только \(1\) значение, поэтому мы выводим \(5\).
В \(4\) запросе первый путь — только вершина \(5\), что приводит к мультинабору \(\{3\}\), а второй путь — \(4 \rightarrow 2 \rightarrow 1 \rightarrow 3\) дает \(\{4, 2, 5, 3\}\). Числа \(5\), \(2\) и \(4\) встречаются разное количество раз.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
5 2 3 4 3
1 2
1 3
2 4
2 5
4
1 4 4 5 3
2 3 2 3 1
1 4 4 5 1
5 5 4 3 10
|
2 3 5
0
1 5
3 5 2 4
|