/// - 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> adj[N];
int sz[N], par[N];
void dfs(int u, int p) {
par[u] = p;
sz[u] = 1;
for (int &v : adj[u]) if (v != p) {
dfs(v, u);
sz[u] += sz[v];
}
}
int find_centroid(int u, int par, int target) {
for (int &v : adj[u]) if (v != par) {
if (sz[v] >= target) {
return find_centroid(v, u, target);
}
}
return u;
}
vector<int> mark(vector<pair<int, int>> F, int safe) {
int n = F.size() + 1;
for (auto [u, v] : F) {
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
dfs(1, 0);
int c = find_centroid(1, 0, (sz[1] + 1) / 2);
dfs(c, 0);
vector<int> ans(n);
ans[safe - 1] = 1;
while (safe != c) {
safe = par[safe];
ans[safe - 1] = 1;
}
int c2 = -1;
for (int &v : adj[c]) {
if (sz[v] == (n + 1) / 2) {
c2 = v;
}
}
if (c2 != -1 && ans[c2] == 1) {
ans[c] = 0;
}
return ans;
}
void locate(vector<pair<int, int>> F, int curr, int t) {
int n = F.size() + 1;
FOR (i, 1, n) {
adj[i].clear();
}
for (auto [u, v] : F) {
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
dfs(1, 0);
int c = find_centroid(1, 0, (sz[1] + 1) / 2);
dfs(c, 0);
int c2 = -1;
for (int &v : adj[c]) {
if (sz[v] == (n + 1) / 2) {
c2 = v;
}
}
if (c2 == -1) {
adj[c].emplace_back(c);
}
FOR (i, 1, n) {
sort(adj[i].begin(), adj[i].end(), [&] (int a, int b) {
return sz[a] > sz[b];
});
}
while (t == 0) {
t = visit(adj[curr][0]);
curr = adj[curr][0];
}
while (true) {
bool ok = 0;
FOR (i, 1, (int)adj[curr].size() - 1) {
int x = visit(adj[curr][i]);
if (x == 0) {
visit(curr);
}
else {
ok = 1;
curr = adj[curr][i];
t = x;
break;
}
}
if (!ok) {
break;
}
}
}
#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 - 1; v = i;
edges.emplace_back(u, v);
}
vector<int> perm(n);
iota(ALL(perm), 1);
shuffle(ALL(perm), rng);
REP (i, perm.size()) {
idPerm[perm[i]] = i + 1;
}
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
