#include <bits/stdc++.h>
using namespace std;
vector<vector<int>> adj;
int visit(int 𝑣);
void dfs(int a, int p, vector<int> &ret) {
for (int x : adj[a]) {
if (x == p) continue;
ret[x] = (ret[a]+2)%3;
dfs(x, a, ret);
}
}
void dd(int a, int p, vector<int> &d) {
d[a] = 0;
for (int x : adj[a]) {
if (x == p) continue;
dd(x, a, d);
d[a] = max(d[x]+1, d[a]);
}
}
vector<int> mark(vector<pair<int, int>> F, int safe) {
int N = F.size()+2;
adj.resize(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;
dfs(safe, -1, ret);
ret.erase(ret.begin());
return ret;
}
void locate(vector<pair<int, int>> F, int curr, int t) {
int N = F.size()+2;
adj.clear();
adj.resize(N);
for (auto x : F) {
adj[x.first].push_back(x.second);
adj[x.second].push_back(x.first);
}
vector<int> depth(N);
vector<int> seen(N, -1);
seen[curr] = t;
auto visitme = [&](int a) -> int {
if (seen[a] == -1) seen[a] = visit(a);
return seen[a];
};
dd(curr, -1, depth);
int prev = -1;
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;
}
}
}
return;
}
