/// - art -
#ifndef _WIN64
#include "incursion.h"
#endif // _WIN64
#include <bits/stdc++.h>
#define el cout << '\n'
#define ALL(x) (x).begin(), (x).end()
#define FOR(i, a, b) for (int i = (a), _b = (b); i <= _b; ++i)
#define REV(i, b, a) for (int i = (b), _a = (a); i >= _a; --i)
#define REP(i, c) for (int i = 0, _c = (c); i < _c; ++i)
const int N = 1e5 + 7;
using namespace std;
#ifdef _WIN64
mt19937_64 rng(chrono::high_resolution_clock::now().time_since_epoch().count());
vector<int> mark(vector<pair<int, int>> F, int safe);
void locate(vector<pair<int, int>> F, int curr, int t);
int idPerm[N];
map<pair<int, int>, bool> mp;
vector<int> t;
int last;
int visit(int v) {
assert(mp.find(make_pair(last, v)) != mp.end());
last = v;
return t[idPerm[v]];
}
#endif // _WIN64
vector<int> mark(vector<pair<int, int>> edges, int safe) {
int n = 0;
for (auto &[u, v] : edges) {
--u; --v;
n = max(n, v + 1);
n = max(n, u + 1);
}
vector<vector<int>> adj(n);
for (auto &[u, v] : edges) {
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
queue<int> Q;
Q.emplace(safe);
vector<int> dist(n, -1);
dist[safe] = 0;
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int &v : adj[u]) {
if (dist[v] == -1) {
dist[v] = dist[u] + 1;
Q.emplace(v);
}
}
}
return dist;
}
void locate(vector<pair<int, int>> edges, int curr, int t) {
if (t == 0) {
return;
}
int n = 0;
for (auto &[u, v] : edges) {
--u; --v;
n = max(n, v + 1);
n = max(n, u + 1);
}
vector<vector<int>> adj(n);
for (auto &[u, v] : edges) {
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
auto dfs = [&](int u, int par) -> void {
stack<pair<int, int>> st;
st.emplace(u, par);
while (!st.empty()) {
auto [u, par] = st.top(); st.pop();
for (int &v : adj[u]) if (v != par) {
int x = visit(v);
if (x == 0) {
return;
}
st.emplace(v, u);
}
}
};
int x = visit(adj[curr][0]);
if (x < t) {
dfs(adj[curr][0], curr);
}
else {
visit(curr);
visit(adj[curr][1]);
dfs(adj[curr][1], curr);
}
}
#ifdef _WIN64
int main() {
ios_base::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
int n, safe;
// cin >> n >> safe;
n = rng() % 10 + 1;
safe = rng() % n;
vector<pair<int, int>> edges;
FOR (i, 2, n) {
int u, v;
// cin >> u >> v;
u = i - 2; v = i - 1;
edges.emplace_back(u, v);
}
vector<int> perm(n);
iota(ALL(perm), 0);
shuffle(ALL(perm), rng);
REP (i, perm.size()) {
idPerm[perm[i]] = i;
}
t = mark(edges, safe);
for (auto &[u, v] : edges) {
u = perm[u]; v = perm[v];
mp[{u, v}] = 1;
mp[{v, u}] = 1;
}
int sta;
// cin >> sta;
sta = rng() % n;
cerr << n << ' ' << safe << ' ' << sta << '\n';
last = sta;
locate(edges, sta, t[idPerm[sta]]);
assert(last == perm[safe]);
return 0;
}
#endif // _WIN64
