#include <bits/stdc++.h>
#define fi first
#define se second
#define mp make_pair
#define TASK ""
#define ALL(x) (x).begin(), (x).end()
using namespace std;
template <typename T1, typename T2> bool mini(T1 &a, T2 b) {
if (a > b) {a = b; return true;} return false;
}
template <typename T1, typename T2> bool maxi(T1 &a, T2 b) {
if (a < b) {a = b; return true;} return false;
}
const int Nmax = 3e5 + 5;
const int oo = 1e9;
const long long ooo = 1e18;
const int mod = 1e9 + 7; // 998244353;
const long double pi = acos(-1);
#include "garden.h"
#include "gardenlib.h"
#include "grader.cpp"
vector <int> adj[Nmax];
vector <int> val[Nmax];
pair <int, int> ed[Nmax];
pair <int, int> pir[Nmax];
int ptr[Nmax];
int ans[Nmax];
int qr[Nmax];
int n,m,p,q;
bool cyc[Nmax];
void addEdge(int u, int v) {
// cerr << u << " " << v << "\n";
ptr[u] = v;
adj[v].push_back(u);
}
void build() {
for (int i = 0; i < n; i++)
pir[i] = mp(-1, -1);
for (int i = 0; i < m; i++) {
int u = ed[i].fi;
int v = ed[i].se;
if (pir[u].fi == -1)
pir[u].fi = v;
else if (pir[u].se == -1)
pir[u].se = v;
if (pir[v].fi == -1)
pir[v].fi = u;
else if (pir[v].se == -1)
pir[v].se = u;
}
for (int i = 0; i < n; i++) {
int j;
j = pir[i].fi;
if (pir[j].fi == i)
addEdge(i, j + n);
else
addEdge(i, j);
j = pir[i].se;
if (j == -1) {
addEdge(i + n, ptr[i]);
} else {
if (pir[j].fi == i)
addEdge(i + n, j + n);
else
addEdge(i + n, j);
}
}
}
void dfs(int u, int d, vector <int> &cnt) {
if (u < n)
cnt[d]++;
for (int v : adj[u])
dfs(v, d + 1, cnt);
}
void dfs1(int u, int d, int sz) {
if (u < n)
val[d % sz].push_back(d);
for (int v : adj[u])
if (!cyc[v])
dfs1(v, d + 1, sz);
}
void solve(int s) {
memset(cyc, 0, sizeof(cyc));
int v = s;
int sz = 0;
while (!cyc[ptr[v]]) {
v = ptr[v];
cyc[v] = true;
sz++;
}
for (int i = 0; i < sz; i++)
val[i].clear();
if (v != s) {
vector <int> cnt(2 * n, 0);
dfs(s, 0, cnt);
for (int i = 0; i < q; i++)
ans[i] += cnt[qr[i]];
} else {
for (int v = s, rep = 1, cur = 0; rep <= sz; v = ptr[v], rep++) {
dfs1(v, cur, sz);
cur--;
if (cur < 0)
cur = sz - 1;
}
for (int i = 0; i < sz; i++)
sort(ALL(val[i]));
for (int i = 0; i < q; i++) {
int k = qr[i];
int v = k % sz;
ans[i] += upper_bound(ALL(val[v]), k) - val[v].begin();
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n = N;
m = M;
p = P;
q = Q;
for (int i = 0; i < m; i++)
ed[i] = mp(R[i][0], R[i][1]);
for (int i = 0; i < q; i++)
qr[i] = G[i];
build();
solve(p);
solve(p + n);
for (int i = 0; i < q; i++)
answer(ans[i]);
}
Compilation message
/usr/bin/ld: /tmp/cck8Nor2.o: in function `read_input()':
grader.cpp:(.text+0x0): multiple definition of `read_input()'; /tmp/ccw621h5.o:garden.cpp:(.text+0x420): first defined here
/usr/bin/ld: /tmp/cck8Nor2.o: in function `answer(int)':
grader.cpp:(.text+0x130): multiple definition of `answer(int)'; /tmp/ccw621h5.o:garden.cpp:(.text+0x550): first defined here
/usr/bin/ld: /tmp/cck8Nor2.o: in function `main':
grader.cpp:(.text.startup+0x0): multiple definition of `main'; /tmp/ccw621h5.o:garden.cpp:(.text.startup+0x0): first defined here
collect2: error: ld returned 1 exit status
