#include <bits/stdc++.h>
using namespace std;
int visit(int 𝑣);
vector<int> mark(vector<pair<int, int>> F, int safe) {
int N = F.size()+2;
vector<vector<int>> adj(N);
for (auto x : F) {
adj[x.first].push_back(x.second);
adj[x.second].push_back(x.first);
}
vector<int> ret(N);
ret[safe] = 2;
function<void(int, int)> dfs = [&](int a, int p) -> void {
for (int x : adj[a]) {
if (x == p) continue;
ret[x] = (ret[a]+2)%3;
dfs(x, a);
}
};
dfs(safe, 0);
ret.erase(ret.begin());
return ret;
}
void locate(vector<pair<int, int>> F, int curr, int t) {
int N = F.size()+2;
vector<vector<int>> adj(N);
for (auto x : F) {
adj[x.first].push_back(x.second);
adj[x.second].push_back(x.first);
}
vector<int> depth(N, 0);
/*
vector<int> seen(N, -1);
seen[curr] = t;
auto visitme = [&](int a) -> int {
if (seen[a] == -1) seen[a] = visit(a);
return seen[a];
};*/
function<void(int, int)> dfs = [&](int a, int p) {
for (int x : adj[a]) {
if (x == p) continue;
dfs(x, a);
depth[a] = max(depth[x]+1, depth[a]);
}
};
dfs(curr, 0);
int prev = 0;
while (1) {
int best = adj[curr][0], other = -1;
if (best == prev) {
if (adj[curr].size() == 1) return; // ok?
best = adj[curr][1];
}
for (int x : adj[curr]) {
if (x == prev || x == best) continue;
if (depth[best] < depth[x]) {
other = best;
best = x;
} else other = x;
}
prev = curr;
int aus = visit(best);
if (aus == (t+1)%3) curr = best, t = aus;
else {
visit(curr);
if (other == -1) return;
aus = visit(other);
if (aus == (t+1)%3) curr = other, t = aus;
else {
visit(curr);
return;
}
}
}
cout << "nogood";
return;
}
