#include "garden.h"
#include "gardenlib.h"
#include <bits/stdc++.h>
//#include "grader.cpp"
#define pii pair<int, int>
#define fr first
#define sc second
#define pb push_back
#define mk make_pair
#define szof(s) (int)s.size()
using namespace std;
const int MAXN = 150005;
int n, m, p;
vector <pii> edges;
vector <pii> g[MAXN]; //id, vertex
int mn[MAXN], mx[MAXN];
pii table[2][MAXN][30];
int get(int v, int len) {
int ind = -1;
int cur = v;
pii need;
for (int i = 30; i >= 0; i--) {
if (len & (1 << i)) {
if (cur == v) {
need = table[0][cur][i];
cur = need.second;
ind = need.first;
} else {
if (ind != g[cur][0].first) {
need = table[0][cur][i];
cur = need.second;
ind = need.first;
} else {
need = table[1][cur][i];
cur = need.second;
ind = need.first;
}
}
}
}
return cur;
}
int solve(int k) {
int ans = 0;
for (int v = 0; v < n; v++) {
if (get(v, k) == p) {
ans++;
}
}
return ans;
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
n = N;
m = M;
p = P;
for (int i = 0; i < M; i++) {
int x = R[i][0];
int y = R[i][1];
edges.pb({x, y});
if (szof(g[x]) < 2) {
g[x].push_back({i, y});
}
if (szof(g[y]) < 2) {
g[y].push_back({i, x});
}
}
for (int i = 0; i < n; i++) {
if (szof(g[i]) < 2) {
g[i].pb(g[i][0]);
}
}
for (int v = 0; v < n; v++) {
table[0][v][0] = g[v][0];
table[1][v][0] = g[v][1];
}
for (int pw = 1; pw < 30; pw++) {
for (int v = 0; v < n; v++) {
for (int tp = 0; tp <= 1; tp++) {
int to = table[tp][v][pw - 1].second;
int ind = table[tp][v][pw - 1].first;
if (ind != g[to][0].first) {
table[tp][v][pw] = table[0][to][pw - 1];
} else {
table[tp][v][pw] = table[1][to][pw - 1];
}
}
}
}
for (int i = 0; i < Q; i++) {
answer(solve(G[i]));
}
}
int dfs(int v, int k, int par = -1, int len = 0) {
if (len == k) {
return v;
}
pii best = {(int)1e9, -1};
auto get = [&](pii a, pii b) {
if (a.fr < b.fr) {
return a;
} else {
return b;
}
};
for (pii to : g[v]) {
if (to.sc != par) {
best = get(best, to);
}
}
if (best.fr == 1e9) {
return dfs(par, k, v, len + 1);
} else {
return dfs(best.sc, k, v, len + 1);
}
}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
int get_rand() {
int x = rnd();
if (x < 0) {
x = -x;
}
return x;
}
int gen(int l, int r) {
return l + (get_rand() % (r - l + 1));
}
struct DSU {
vector <int> pr;
vector <int> sz;
DSU () {
pr.resize(10000);
sz.resize(10000);
for (int i = 0; i < 10000; i++) {
pr[i] = i;
sz[i] = 1;
}
}
int findp(int v) {
if (v == pr[v]) {
return v;
}
return pr[v] = findp(pr[v]);
}
void unite(int a, int b) {
a = findp(a);
b = findp(b);
if (a == b) {
return;
}
if (sz[a] > sz[b]) {
swap(a, b);
}
pr[a] = b;
sz[b] += sz[a];
}
};
