Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

AL_25_11 - Ukraina kontratakuje dzięki Adamowi

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;105], m ∈ [1;105] i q ∈ [1;105] 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] (ab) 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

Dodane przez:Maciej Boniecki
Data dodania:2015-11-07
Limit czasu wykonania programu:2s
Limit długości kodu źródłowego50000B
Limit pamięci:1536MB
Cluster: Cube (Intel G860)
Języki programowania:All except: ASM64 GOSU JS-MONKEY
Pochodzenie:ALGOLIGA

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.