AlgoLiga 2018

Rząd Ukrainy postanowił raz na zawsze rozwiązać problem prorosyjskich separatystów w obwodach Donieckim i Ługańskim. W obwodach tych znajduje się n miast połączonych n-1 bezpośrednimi drogami. Pomiędzy każdą parą miast istnieje dokładnie jedna trasa. Władze Ukrainy posiadają listę m obiektów separatystów, które chcieliby zniszczyć. Wiedzą oni również w jakich miastach się one znajdują. Obiekty te ponumerowane są numerami od 1 do m, im niższy numer tym ważniejsze jest zniszczenie tego obiektu.

Wojsko Ukrainy przygotowało q planów ataku. Każdy atak zakłada zniszczenie maksymalnie 10 obiektów na trasie pomiędzy miastami a i b. Może się zdarzyć tak, że atak będzie dotyczył tylko jednego miasta. Jeżeli obiektów na trasie pomiędzy wybranymi miejscowościami będzie więcej niż 10 wojsko zaatakuje te najważniejsze czyli o najniższych numerach.

Pomóż ukraińskiej armii i dla każdego z q planów wyznacz ile i jakie obiekty zostaną zniszczone.

Wejście

W pierwszej linii wejścia znajdują się trzy liczby naturalne n ∈ [1;10⁵], m ∈ [1;10⁵] i q ∈ [1;10⁵] opisane powyżej. W kolejnych n-1 liniach znajdują się opisy dróg pomiędzy miastami. Każdy opis składa się z dwóch liczb całkowitych a ∈ [1;n] i b ∈ [1;n] (a ≠ b) określających numery miast połączonych bezpośrednią drogą. Następna linia zawiera m liczb całkowitych. Liczba i-ta w kolejności oznacza numer miasta, w którym znajduje się obiekt o numerze i. Ostatnie q linii zawiera plany ataków. Każdy plan ataku składa się z dwóch liczb całkowitych a ∈ [1;n] i b ∈ [1;n] określających numery miast pomiędzy którymi przebiega trasa ataku armii.

Wyjście

Na wyjściu dla każdego z q planów ataków należy w osobnej linii wypisać liczbę obiektów, które zostaną zaatakowane, a następnie ich listę w kolejności rosnących numerów.

Przykład

Wejście

10 25 5
3 2
2 1
1 7
7 9
10 7
8 6
6 1
5 4
4 2
3 5 4 6 10 7 1 1 7 6 3 5 2 1 1 1 1 1 1 1 1 1 1 1 1
1 1
8 8
3 5
8 10
9 3

Wyjście

10 7 8 14 15 16 17 18 19 20 21
0
6 1 2 3 11 12 13
10 4 5 6 7 8 9 10 14 15 16
10 1 6 7 8 9 11 13 14 15 16