Î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: , unde 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 , 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: . 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ă: pentru
i ∈ {1, ... , N}
. - Suma valorilor
N
pentru celeT
scenarii este cel mult400 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 aceste2
stațiuni
Subtask 3 (18 puncte)
N ≤ 2 000
- Suma valorilor
N
pentru celeT
scenarii este cel mult8 000
.
Subtask 4 (19 puncte)
- Pentru oricare două stațiuni
a, b ∈ {1, .. . , N}
se poate ajunge dina
înb
folosind cel mult200
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.