#include #include #include #include #include #include using namespace std; ifstream fin("fantasy.in"); ofstream fout("fantasy.out"); const int MAXN = 1010; int t, n, d, c, v, last[MAXN], dist[MAXN], visited[MAXN], urm[MAXN], mark[MAXN], gtc[MAXN], gtcb[MAXN]; vector graph[MAXN]; int get_dist(int start, int finish) { queue coada; coada.push(start); dist[start] = 0; for (int i = 1; i <= n; ++i) visited[i] = 0; while (!coada.empty()) { int nod = coada.front(); coada.pop(); visited[nod] = 1; //cout << nod << endl; for (auto it : graph[nod]) { if (!visited[it]) { last[it] = nod; dist[it] = dist[nod] + 1; visited[it] = 1; if (it == finish) return dist[it]; coada.push(it); } } } //cout << "CEVA PLM" << endl; return -1; } int main() { fin >> t; for (; t; --t) { fin >> n >> d >> c >> v; for (int i = 1; i <= n; ++i) mark[i] = 0; for (int i = 1; i <= n; ++i) graph[i].clear(); for (int i = 1; i < n; ++i) { int x, y; fin >> x >> y; graph[x].push_back(y); graph[y].push_back(x); } //cout << "MERGE" << endl; //cout << "MERGE" << endl; int dist2 = get_dist(c, v); int dist1 = get_dist(d, v); for (int i = 1; i <= n; ++i) gtc[i] = last[i]; for (int nod = v; nod != d; nod = gtc[nod]) { gtcb[gtc[nod]] = nod; } get_dist(d, c); //cout << "MERG DISTANTELE" << endl; for (int nod = c; nod != d; nod = last[nod]) { urm[last[nod]] = nod; mark[nod] = 1; } mark[d] = 1; int moare = 0; cout << dist1 << " " << dist2 << " " << mark[v] << endl; //break; if (!mark[v]) { if (dist1 >= dist2) { fout << "DA\n"; continue; } while (!mark[v] && !moare) { if (gtc[v] == d || gtc[v] == c) { moare = 1; } if (gtcb[d] != urm[d]) { moare = 1; } v = gtc[v]; d = urm[d]; c = last[c]; if (v == c || v == d) { moare = 1; } } if (moare) { fout << "NU\n"; continue; } } //cout << v << d << c << endl; int canEvasion = 0; int bestEvasion = 0; if (graph[v].size() > 2) { canEvasion = 1; } int curEvasion = 0; //cout << "NU AICI!\n" << endl; int cv = v, cd = d, cc = c; while (last[v] != urm[d] && last[v] != d) { // cat timp nu ne lovim de dragon scapam de el v = last[v]; c = last[c]; d = urm[d]; --curEvasion; if (graph[v].size() > 2) { canEvasion = 1; bestEvasion = curEvasion; break; } } v = cv; d = cd; c = cc; curEvasion = 0; while (urm[v] != last[c] && urm[v] != c) { // cat timp nu ne lovim de cavaler scapam de el v = urm[v]; c = last[c]; d = urm[d]; ++curEvasion; if (graph[v].size() > 2) { canEvasion = 1; bestEvasion = curEvasion; } } if (!canEvasion) { fout << "NU\n"; continue; } if (dist1 >= dist2 - bestEvasion * 2) { fout << "DA\n"; } else { fout << "NU\n"; } } return 0; }