1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include<algorithm>
#include<array>
#include<iomanip>
#include<ios>
#include<iostream>
#include<map>
#include<numeric>
#include<string>
#include<set>
#include<vector>
#include<queue>

typedef std::vector<std::vector<int>> Sasiedzi;

static bool zawiera(std::string &napis, char znak) {
	return std::find(napis.begin(), napis.end(), znak) != napis.end();
}

static void ciag(Sasiedzi &sasiedzi, std::string &kolorowanie, std::vector<int> &stopien, std::string &ciag_wyj) {
	int wierzcholek = std::find(stopien.begin(), stopien.end(), 1) - stopien.begin();
	int poprzedni = -1;
	ciag_wyj[0] = kolorowanie[wierzcholek];
	for (size_t i = 1; i < kolorowanie.size(); ++i) {
		std::cerr << wierzcholek << ' ' << poprzedni << ' ' << sasiedzi[wierzcholek].front() << ' ' << sasiedzi[wierzcholek].back() << std::endl;
		int tymcz = wierzcholek;
		wierzcholek = (sasiedzi[wierzcholek][0] != poprzedni)? sasiedzi[wierzcholek][0]: sasiedzi[wierzcholek][1];
		poprzedni = tymcz;
		if (kolorowanie[wierzcholek] != ciag_wyj.back()) {
			ciag_wyj += kolorowanie[wierzcholek];
		}
	}
}

int main()
{
	std::string kolorowanie_poczatkowe;
	std::string kolorowanie_koncowe;
	int wierzcholkow;
	int testow;
	int z;
	int ku;
	bool rozgaleziony;

	std::cin >> testow;

	for (int t = 0; t < testow; ++t) {
		rozgaleziony = false;
		std::cin >> wierzcholkow;
		std::cin >> kolorowanie_poczatkowe;
		std::cin >> kolorowanie_koncowe;
		std::vector<int> stopien(wierzcholkow, 0);
		Sasiedzi sasiedzi(wierzcholkow, Sasiedzi::value_type{});
		for (int i = 1; i < wierzcholkow; ++i) {
			std::cin >> z >> ku;
			--z;
			--ku;
			stopien[z]++;
			stopien[ku]++;
			std::cerr << (z+1) << ' ' << stopien[z] << std::endl;
			std::cerr << (ku+1) << ' ' << stopien[ku] << std::endl;
			if (3 <= stopien[z] || 3 <= stopien[ku]) {
				rozgaleziony = true;
				continue;
			}
			sasiedzi[z].push_back(ku);
			sasiedzi[ku].push_back(z);
		}
		if (rozgaleziony) {
			if ( (zawiera(kolorowanie_poczatkowe, '0') || ! zawiera(kolorowanie_koncowe, '0')) && (zawiera(kolorowanie_poczatkowe, '1') || ! zawiera(kolorowanie_koncowe, '1')) ) {
				std::cout << "TAK" << std::endl;
			} else  {
				std::cout << "NIE" << std::endl;
			}
			std::cerr << "1" << std::endl;
			continue;
		}

		std::string ciag_poczatkowy;
		std::string ciag_koncowy;
		ciag(sasiedzi, kolorowanie_poczatkowe, stopien, ciag_poczatkowy);
		ciag(sasiedzi, kolorowanie_koncowe, stopien, ciag_koncowy);
		if (ciag_poczatkowy == ciag_koncowy || ciag_koncowy.size() < ciag_poczatkowy.size()) {
			std::cout << "TAK" << std::endl;
			std::cerr << ' ' << ciag_poczatkowy << ' ' << ciag_koncowy << std::endl;
		} else  {
			std::cout << "NIE" << std::endl;
		}
			std::cerr << "2" << std::endl;
	}

	return 0;
}