Problem description

Back
Show PDF
Radioaktywne chemikalia
(B)
Limit pamięci: 1024 MB
Limit czasu: 4.00 s

W piwnicach Uniwersytetu Wrocławskiego są przechowywane radioaktywne chemikalia. Stworzono dla nich N specjalnych pomieszczeń, ponumerowanych od 1 do N. Pomieszczenia są połączone N − 1 korytarzami tak, aby z każdego można było dotrzeć do dowolnego innego.

Ze względu na swoje radioaktywne właściwości, chemikalia nie mogą znajdować się zbyt blisko siebie. Ustanowiono, że układ jest bezpieczny, jeśli dowolne dwa radioaktywne chemikalia są oddalone od siebie o co najmniej dwa korytarze.

Podane przykłady przedstawiają dwie sytuacje: (a) układ bezpieczny oraz (b) układ niebezpieczny.

Pracownicy uczelni czasem muszą posprzątać, co wymaga przestawienia chemikaliów do innych pomieszczeń. Jedyną możliwą operacją jest przeniesienie radioaktywnych chemikaliów przez korytarz do sąsiadującego pomieszczenia. Warunkiem koniecznym jest, aby układ pozostał bezpieczny.

Rozwiązanie 3-ciego przykładu

Jasio, pracownik Uniwersytetu Wrocławskiego, otrzymał od przełożonego aktualny oraz docelowy bezpieczny układ radioaktywnych chemikaliów. Jasio nie jest pewny, czy da się przenieść chemikalia w docelowe miejsca. Twoim zadaniem jest mu pomóc. Dla każdego przypadku testowego sprawdź, czy istnieje ciąg bezpiecznych operacji prowadzących z układu aktualnego do układu docelowego.

Wejście

W pierwszym wierszu wejścia znajduje się liczba całkowita T, oznaczająca liczbę przypadków testowych. Dla każdego przypadku testowego:

W pierwszym wierszu znajduje się liczba całkowita N – liczba pomieszczeń.

W kolejnych N − 1 wierszach znajdują się pary liczb całkowitych ui, vi, opisujące pomieszczenia połączone korytarzem.

Następnie podane są dwa binarne ciągi długości N, opisujące odpowiednio aktualne oraz docelowe układy chemikaliów. Jeśli w pokoju i znajdują się radioaktywne chemikalia to w ciągu na pozycji i znajduje się 1, a 0 w przeciwnym przypadku.

Podane dwa układy są bezpieczne oraz zawierają taką samą liczbę radioaktywnych chemikaliów.

Wyjście

Dla każdego z T przypadków testowych w osobnych liniach wypisz TAK jeśli da się przestawić radioaktywne chemikalia w docelowy układ lub wypisz NIE w przeciwnym przypadku.

Ograniczenia

1 ≤ T ≤ 105, ∑N ≤ 106, 1 ≤ ui, vi ≤ N, ui ≠ vi

Podzadania

Podzadanie Warunki Punkty
1 N ≤ 10, ∑N ≤ 10 000 20
2 W pomieszczeniach występują co najwyżej 2 radioaktywne chemikalia. 10
3 W pomieszczeniach występują co najwyżej 3 radioaktywne chemikalia. 10
4 ∑N ≤ 1000 20
5 ∑N ≤ 105 20
6 Brak dodatkowych ograniczeń. 20

Przykład

Wejście Wyjście 
4
4
1 2
2 3
2 4
1001
0011
4
1 2
2 3
2 4
1001
1001
5
1 2
2 3
2 4
4 5
10010
00110
11
1 2
2 3
3 4
4 5
5 6
2 7
4 8
3 9
5 10
8 11
10000111000
10101001000
 
NIE
TAK
TAK
NIE