#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include "garden.h"
#include "gardenlib.h"
using namespace std;
// <|°_°|>
const int INFINI = (1000 * 1000 * 1000 + 1);
const int MAX_NOEUDS = (150 * 1000);
const int MAX_ARETES = (300 * 1000 + 1);
const int MAX_REQUETES = (2000);
vector <int> Voisins[MAX_NOEUDS];
bool Depart[MAX_ARETES];
bool Vu[MAX_ARETES];
int Fils[MAX_ARETES];
int Dist[MAX_ARETES];
pair <int, int> Ans[MAX_REQUETES];
int Occ[MAX_ARETES];
pair <int, int> AretesSorties;
void Set(int noeud, bool start) {
int dest2, dest;
dest2 = dest = Voisins[noeud][0];
if (Voisins[noeud].size() > 1)
dest2 = Voisins[noeud][1];
for (int id : Voisins[noeud])
{
if (id != dest)
Fils[id ^ 1] = dest;
else
Fils[id ^ 1] = dest2;
}
if (dest2 == dest)
dest2 = -1;
if (start)
AretesSorties = {dest, dest2};
Depart[dest] = true;
return;
}
int FindDist(int noeud, int out) {
if (noeud == out)
return 0;
if (Vu[noeud])
return Dist[noeud];
Vu[noeud] = true;
return Dist[noeud] = FindDist(Fils[noeud], out) + 1;
}
void SetDist(int dep, int nbAretes) {
for (int i = 0; i < nbAretes; i ++)
{
Dist[i] = INFINI;
Vu[i] = false;
}
for (int i = 0; i < nbAretes; i ++)
{
if (!Vu[i])
FindDist(i, dep);
}
return;
}
void count_routes(int nbNoeuds, int nbAretes, int sortie, int Aretes[][2], int nbRequetes, int Requetes[]) {
for (int i = 0; i < nbAretes; i ++)
{
Voisins[Aretes[i][0]].push_back(2 * i);
Voisins[Aretes[i][1]].push_back(2 * i + 1);
}
nbAretes *= 2;
for (int i = 0; i < nbNoeuds; i ++)
{
Set(i, i == sortie);
}
for (int i = 0; i < nbRequetes; i ++)
{
Ans[i] = {Requetes[i], i};
}
sort(Ans, Ans + nbRequetes);
for (int i = 0; i < nbRequetes; i ++)
{
Ans[i].first = 0;
}
SetDist(AretesSorties.first, nbAretes);
int tailleCycle = Dist[Fils[AretesSorties.first]] + 1;
Dist[AretesSorties.first] = tailleCycle;
int maxi = 0;
for (int i = 0; i < nbAretes; i ++)
{
if (Depart[i] && Dist[i] < INFINI)
{
maxi = max(maxi, Dist[i]);
Occ[Dist[i]] ++;
}
}
int cur = 0;
int newCur = 0;
for (int i = 0; i < nbRequetes; i ++)
{
while (cur <= min(maxi, Requetes[Ans[i].second]))
{
if (cur >= tailleCycle)
Occ[newCur] += Occ[cur];
cur ++;
if (++ newCur == tailleCycle)
newCur = 0;
}
if (Requetes[Ans[i].second] % tailleCycle < MAX_ARETES)
Ans[i].first += Occ[Requetes[Ans[i].second] % tailleCycle];
}
if (AretesSorties.second >= 0)
{
SetDist(AretesSorties.second, nbAretes);
tailleCycle = Dist[Fils[AretesSorties.second]] + 1;
Dist[AretesSorties.second] = tailleCycle;
for (int i = 0; i <= maxi; i ++)
{
Occ[i] = 0;
}
maxi = 0;
for (int i = 0; i < nbAretes; i ++)
{
if (Depart[i] && Dist[i] < INFINI)
{
maxi = max(maxi, Dist[i]);
Occ[Dist[i]] ++;
}
}
cur = 0;
newCur = 0;
for (int i = 0; i < nbRequetes; i ++)
{
while (cur <= min(maxi, Requetes[Ans[i].second]))
{
if (cur >= tailleCycle)
Occ[newCur] += Occ[cur];
cur ++;
if (++ newCur == tailleCycle)
newCur = 0;
}
if (Requetes[Ans[i].second] % tailleCycle < MAX_ARETES)
Ans[i].first += Occ[Requetes[Ans[i].second] % tailleCycle];
}
}
for (int i = 0; i < nbRequetes; i ++)
{
swap(Ans[i].first, Ans[i].second);
}
sort(Ans, Ans + nbRequetes);
for (int i = 0; i < nbRequetes; i ++)
{
answer(Ans[i].second);
}
return;
}
