/// - 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) {
n = max(n, u + 1);
n = max(n, v + 1);
}
if (n == 0) return {};
vector<vector<int>> adj(n);
for (auto &[u, v] : edges) {
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
vector<int> par(n, -2);
queue<int> Q;
par[safe] = -1;
Q.emplace(safe);
while (!Q.empty()) {
int u = Q.front(); Q.pop();
for (int v : adj[u]) {
if (par[v] == -2) {
par[v] = u;
Q.emplace(v);
}
}
}
vector<int> label(n, 0);
REP (u, n) {
if (u == safe) {
label[u] = 2;
continue;
}
int p = par[u];
assert(p >= 0);
int idx = -1;
REP (i, adj[u].size()) {
if (adj[u][i] == p) {
idx = i;
break;
}
}
assert(idx != -1);
label[u] = idx;
}
return label;
}
void locate(vector<pair<int, int>> edges, int curr, int t_start) {
if (t_start == 2) {
return;
}
int n = 0;
for (auto &[u, v] : edges) {
n = max(n, u + 1);
n = max(n, v + 1);
}
vector<vector<int>> adj(n);
for (auto &[u, v] : edges) {
adj[u].emplace_back(v);
adj[v].emplace_back(u);
}
int cur = curr;
int cur_label = t_start;
while (cur_label != 2) {
int pos = cur_label;
if (pos < 0 || pos >= (int)adj[cur].size()) {
if (!adj[cur].empty()) {
int nxt = adj[cur][0];
cur_label = visit(nxt);
cur = nxt;
continue;
}
return;
}
int nxt = adj[cur][pos];
cur_label = visit(nxt);
cur = nxt;
}
}
#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
