#include <bits/stdc++.h>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
const int K = 31;
const int N = 2 * 150000 + 7;
int n, m, city, from[N], to[N], y;
vector<int> g[N];
void add_edge(int a, int b) {
from[y] = a;
to[y] = b;
g[a].push_back(y);
y++;
}
int nxt[K][N];
bool contain[K][N];
int len_cycle[2], type_cycle[2];
int ff[N], tt[N];
bool ok;
int node, lq;
bool func0(int len) {
if (len < 0) return 0;
if (len == 0) return 1;
if (len_cycle[0] == -1) return 0;
if (type_cycle[0] == 0) return (len % len_cycle[0] == 0);
if (len_cycle[1] == -1) assert(0);
if (len < len_cycle[0]) return 0;
if (type_cycle[1] == 1) return (len - len_cycle[0]) % len_cycle[1] == 0;
if (type_cycle[1] == 0) {
int r = len % (len_cycle[0] + len_cycle[1]);
if (r == 0 || r == len_cycle[0]) {
return 1;
} else {
return 0;
}
}
assert(0);
}
bool func1(int len) {
return ok;
if (len < 0) return 0;
if (len == 0) return 1;
if (len_cycle[1] == -1) return 0;
return ok;
if (type_cycle[1] == 0) return (len % len_cycle[1] == 0);
if (len_cycle[0] == -1) assert(0);
/// return ok;
if (len < len_cycle[1]) return 0;
if (type_cycle[0] == 0) return (len - len_cycle[1]) % len_cycle[0] == 0;
if (type_cycle[0] == 1) {
int r = len % (len_cycle[0] + len_cycle[1]);
if ((r == 0 || r == len_cycle[1]) != ok) {
cout << "# " << lq << ", " << node << "\n";
cout << "my bad\n";
cout << "ok = " << ok << "\n";
exit(0);
cout << ok << " and " << (r == 0 || r == len_cycle[1]) << "\n";
cout << " = " << len << " : " << len_cycle[0] << " and " << len_cycle[1] << "\n";
cout << " len_query = " << lq << "\n";
{
int i = g[node][0];
cout << "kek: " << i << "\n";
for (int s = 0; s <= 10; s++) {
cout << s << " si " << i << " si " << city << "\n";
if (from[i] == city) {
cout << "what the frick " << s << "\n";
}
i = nxt[0][i];
continue;
if (from[i] == city) {
cout << " = " << s << "\n";
}
///cout << s << " : " << i << " " << (from[i] == city) << "\n";
i = nxt[0][i];
}
}
exit(0);
}
if (r == 0 || r == len_cycle[1]) {
return 1;
} else {
return 0;
}
}
return ok;
assert(0);
}
void count_routes(int nn, int mm, int pp, int rr[][2], int qq, int gg[]) {
n = nn;
m = mm;
city = pp;
y = 0;
for (int i = 0; i < n; i++) {
g[i].clear();
}
for (int i = 0; i < m; i++) {
add_edge(rr[i][0], rr[i][1]);
add_edge(rr[i][1], rr[i][0]);
}
for (int i = 0; i < y; i++) {
int b = to[i];
if ((int) g[b].size() == 1) {
nxt[0][i] = i ^ 1;
} else {
if ((i ^ 1) == g[b][0]) {
nxt[0][i] = g[b][1];
} else {
nxt[0][i] = g[b][0];
}
}
contain[0][i] = (b == city);
}
for (int bit = 1; bit < K; bit++) {
for (int i = 0; i < y; i++) {
nxt[bit][i] = nxt[bit - 1][nxt[bit - 1][i]];
contain[bit][i] = contain[bit - 1][i] | contain[bit - 1][nxt[bit - 1][i]];
}
}
len_cycle[0] = len_cycle[1] = -1;
for (int ies = 0; ies < min(2, (int) g[city].size()); ies++) {
int i = g[city][ies];
if (!contain[K - 1][i]) {
continue;
}
int sz = 0;
for (int j = K - 1; j >= 0; j--) {
if (!contain[j][i]) {
sz += (1 << j);
i = nxt[j][i];
}
}
len_cycle[ies] = sz;
{
bool este = 0;
int i = g[city][ies];
for (int bit = 0; bit < K; bit++) {
if (len_cycle[ies] & (1 << bit)) {
este |= contain[bit][i];
i = nxt[bit][i];
}
}
if ((int) g[city].size() == 1) {
type_cycle[ies] = 0;
} else {
if ((i ^ 1) == g[city][0]) {
type_cycle[ies] = 1;
} else {
type_cycle[ies] = 0;
}
}
}
len_cycle[ies]++;
}
vector<int> nodes;
for (int a = 0; a < n; a++) {
int i = g[a][0];
if (!contain[K - 1][i] || a == city) {
ff[a] = -1;
continue;
}
nodes.push_back(a);
int sz = 0;
for (int j = K - 1; j >= 0; j--) {
if (!contain[j][i]) {
sz += (1 << j);
i = nxt[j][i];
}
}
ff[a] = sz;
{
bool este = 0;
int i = g[a][0];
for (int bit = 0; bit < K; bit++) {
if (ff[a] & (1 << bit)) {
este |= contain[bit][i];
i = nxt[bit][i];
}
}
if ((int) g[city].size() == 1) {
tt[a] = 0;
} else {
if ((i ^ 1) == g[city][0]) {
tt[a] = 1;
} else {
tt[a] = 0;
}
}
}
ff[a]++;
}
tt[city] = 0;
ff[city] = 0;
nodes.push_back(city);
for (int qind = 0; qind < qq; qind++) {
int len_query = gg[qind], sol = 0;
lq = len_query;
for (auto &a : nodes) {
int cur = g[a][0];
for (int bit = 0; (1 << bit) <= len_query; bit++) {
if (len_query & (1 << bit)) {
cur = nxt[bit][cur];
}
}
ok = (from[cur] == city);
if (a == 6) {
// cout << "here : " << (from[cur] == city) << "\n";
cur = g[a][0];
// cout << ": " << cur << "\n";
for (int j = 0; j <= 10; j++) {
// cout << j << " si " << cur << " si " << city << " si " << "\n";
if (from[cur] == city) {
/// cout << "ooooooooooo : " << j << "\n";
}
cur = nxt[0][cur];
}
// cout << " the fol : " << ok << "\n";
// exit(0);
// cout << "\n";
// cout << "done\n\n\n";
/// exit(0);
}
int len = len_query;
if (tt[a] == 0) {
len -= ff[a];
// ok = (from[cur] == city);
bool me = func0(len);
assert(me == ok);
} else {
node = a;
len -= ff[a];
// ok = (from[cur] == city);
bool me = func1(len);
assert(me == ok);
}
if (from[cur] == city) {
sol++;
if (cur == city) {
}
}
}
answer(sol);
}
}
