În țară sunt N stațiuni de schi, numerotate de la 1 la N, legate între ele prin N − 1 drumuri bidirecționale, cu proprietatea că între oricare două stațiuni există drum direct sau indirect (n.b. țara nu investește în turism mai mult decât este minim necesar). Sezonul de schi este format din M săptămâni, numerotate de la 1 la M. În fiecare săptămână Marcel Schiorul vizitează câte o stațiune de schi, notându-și în agendă pentru fiecare stațiune care a fost ultima data când a schiat acolo. Deoarece costurile deplasării pe drumurile patriei sunt destul de mari, în săptămâni consecutive Marcel va schia în stațiuni între care există drum direct (unul dintre cele N − 1 amintite mai sus). Observați că Marcel nu va schia niciodată în două săptămâni consecutive în aceeași stațiune — ar fi plictisitor.

La finalul sezonului Marcel extrage din agendă N numere: $v_1, ... v_N$ , unde $v_i$ semnifică numărul săptămânii când a schiat pentru ultima dată în stațiunea i ∈ {1, ... , N}. Voi, văzând numerele din șirul v, nu îl credeți pe cuvânt, și vreți să verificați dacă nu cumva acesta a comis o greșeală.

Date fiind N, cele N − 1 drumuri din țară, și numerele $v_1, ... ,v_N$ , determinați dacă Marcel cu siguranță a greșit transcriind numerele v, sau dacă cele spuse de el ar putea fi adevărate. Mai mult, va trebui să rezolvați problema pentru T scenarii independente.

Date de intrare

Pe prima linie se va găsi T, numărul de scenarii. Urmează apoi T grupe de linii, fiecare descriind câte un scenariu de rezolvat. Pe prima linie a unui scenariu se află N, numărul de stațiuni din țară. Pe a doua linie se află N numere separate prin spații: $v_1 v_2 ... v_N$ . Pe următoarele N − 1 linii se află câte două numere a b, semnificând existența unui drum bidirecțional între stațiunile a și b.

Date de ieșire

Se va afișa o singură linie, formată din T cifre binare. A i-a cifră, pentru 1 ≤ i ≤ T va fi 1 dacă în cel de-al i-ulea scenariu cele spuse de Marcel ar putea fi adevărate, și 0 altfel.

Restricții și precizări

• 1 ≤ T ≤ 15 000
• 2 ≤ N ≤ 100 000
• 2 ≤ M ≤ 100 000 000 000
• Marcel vizitează fiecare stațiune cel puțin o dată: $1 ≤ v_i ≤ M$ pentru i ∈ {1, ... , N}.
• Suma valorilor N pentru cele T scenarii este cel mult 400 000.

Subtask 1 (7 puncte)

• N ≤ 3

Subtask 2 (19 puncte)

• Există exact 2 stațiuni care sunt “rupte de lume”—există câte un singur drum bidirecțional care pleacă din fiecare dintre aceste 2 stațiuni

Subtask 3 (18 puncte)

• N ≤ 2 000
• Suma valorilor N pentru cele T scenarii este cel mult 8 000.

Subtask 4 (19 puncte)

• Pentru oricare două stațiuni a, b ∈ {1, .. . , N} se poate ajunge din a în b folosind cel mult 200 de drumuri directe.

Subtask 5 (37 puncte)

• Fără restricții suplimentare.

Exemple

stdin

1
6
11 6 5 3 10 9
1 2
2 3
2 4
1 5
5 6

stdout

1

stdin

2
9
10 9 8 13 1 7 12 14 6
1 2
1 4
2 3
3 5
3 6
6 9
4 7
4 8
4
5 4 5 3
1 2
1 3
2 4

stdout

10

Explicații

Pentru primul scenariu din primul exemplu, Marcel ar putea trece, în ordine, prin stațiunile:
4, 2, 4, 2, 3, 2, 1, 5, 6, 5, 1

Pentru primul scenariu din al doilea exemplu, Marcel ar putea trece, în ordine, prin stațiunile:
5, 3, 6, 9, 6, 9, 6, 3, 2, 1, 4, 7, 4, 8

Pentru al doilea scenariu din al doilea exemplu, este imposibil ca Marcel să fie atât în stațiunea 1 cât și în stațiunea 3 în același timp.