#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.begin(),res.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] = {}; int cur = P; used[cur] = 1; int cnt = 1; while (!used[to[cur]]) { cur = to[cur]; cnt++; } if (to[cur] == P) clen = cnt; vector <vector<int>> v(2*N); for (int i = 0; i < 2*N; i++) { v[i].emplace_back(to[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] = 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); } } } bool ok[2*N]; for (int q = 0; q < Q; q++) { int k = G[q]; for (int i = 0; i < 2*N; i++) { ok[i] = ((d[i]-k)%clen == 0); } int ans = 0; for (int i = 0; i < N; i++) { ans += (ok[i] || ok[i+N]); } answer(ans); } }