#include <bits/stdc++.h> #include "garden.h" #include "gardenlib.h" using namespace std; void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) { vector <vector<pair<int,int>>> res(N); for (int i = 0; i < M; i++) { int u = R[i][0]; int v = R[i][1]; res[v].emplace_back(i,u); res[u].emplace_back(i,v); } for (int i = 0; i < N; i++) { sort(res[i].begin(),res[i].end()); } int to[2*N]; for (int i = 0; i < N; i++) { int best = res[i][0].second; int scbest = (res[i].size() > 1) ? res[i][1].second : best; if (res[best][0].second == i) { to[i] = best + N; } else { to[i] = best; } if (res[scbest][0].second == i) { to[i+N] = scbest + N; } else { to[i+N] = scbest; } } int clen = 0; int used[2*N]; for (int i = 0; i < 2*N; i++) used[i] = 0; int cur = P; used[cur] = 1; int cnt = 1; while (!used[to[cur]]) { cur = to[cur]; cnt++; } if (to[cur] == P) clen = cnt; int clen1 = 0; for (int i = 0; i < 2*N; i++) used[i] = 0; cur = P+N; used[cur] = 1; cnt = 1; while (!used[to[cur]]) { cur = to[cur]; cnt++; } if (to[cur] == P+N) clen1 = cnt; vector <vector<int>> v(2*N); for (int i = 0; i < 2*N; i++) { v[to[i]].emplace_back(i); } queue <int> q; q.push(P); int d[2*N]; for (int i = 0; i < 2*N; i++) d[i] = INT_MAX; d[P] = 0; while (!q.empty()) { int f = q.front(); q.pop(); for (auto to:v[f]) { if (d[to] > d[f] + 1) { d[to] = d[f] + 1; q.push(to); } } } q.push(P+N); int d1[2*N]; for (int i = 0; i < 2*N; i++) d1[i] = INT_MAX; d1[P+N] = 0; while (!q.empty()) { int f = q.front(); q.pop(); for (auto to:v[f]) { if (d1[to] > d1[f]+1) { d1[to] = d1[f] + 1; q.push(to); } } } bool ok[2*N]; bool ok1[2*N]; for (int q = 0; q < Q; q++) { int k = G[q]; for (int i = 0; i < 2*N; i++) { if (clen == 0) { ok[i] = (k == d[i]); continue; } ok[i] = (k >= d[i] && (k-d[i])%clen == 0); } for (int i = 0; i < 2*N; i++) { if (clen1 == 0) { ok1[i] = (k == d1[i]); continue; } ok1[i] = (k >= d1[i] && (k-d1[i])%clen1 == 0); } int ans = 0; for (int i = 0; i < N; i++) { ans += (ok[i] || ok[i+N] || ok1[i] || ok1[i+N]); } answer(ans); } }