#include<bits/stdc++.h>
using namespace std;
#include "garden.h"
#include "gardenlib.h"
//#define int long long
#define fi first
#define se second
#define all(x) x.begin(),x.end()
#define pb push_back
typedef vector<int> vi;
typedef pair<int,int> pii;
typedef vector<pii> vii;
typedef vector<bool> vb;
#define sp <<' '<<
#define FOR(i,a) for(int i=0;i<(a);i++)
#define FORE(i,a,b) for(int i=(a);i<(b);i++)
#define cont(x) {for(auto el:x) cout<<el<<' ';cout<<endl;}
#define contp(x) {for(auto el:x) cout<<el.fi<<'-'<<el.se<<' ';cout<<endl;}
#define DEBUG(X) { cout << #X << " = " << (X) << endl; }
#define carp(x,y) (((x)%mod)*((y)%mod))%mod
#define topla(x,y) (((x)%mod)+((y)%mod))%mod
const int MAXN=150005;
const int MAXK=30;
#define mid (l+r)/2
#define endl '\n'
int n,m,p;
vii adj[MAXN];
int suc[MAXN][MAXK][3];
int cik[MAXN][MAXK][3];
int cur[MAXN];
int rt[MAXN];
void calc(){
FORE(k,1,MAXK){
FORE(nd,1,n+1){
if(suc[nd][k-1][1]!=-1){ //1.routeu izleyerek k-1 adım gidiliyorsa
int bir=suc[nd][k-1][1];
suc[nd][k][1]=suc[bir][k-1][cik[nd][k-1][1]];//min edge i kullan da gel
cik[nd][k][1]=cik[bir][k-1][cik[nd][k-1][1]];
}
if(suc[nd][k-1][2]!=-1){
int bir=suc[nd][k-1][2];
suc[nd][k][2]=suc[bir][k-1][cik[nd][k-1][2]];//min edge i kullan da gel
cik[nd][k][2]=cik[bir][k-1][cik[nd][k-1][2]];
}
}
}
}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[])
{
n=N;
m=M;
p=P;
p++;
memset(suc, -1, sizeof suc);
FORE(i,1,m+1){
int from=R[i-1][0];
int to=R[i-1][1];
from++;to++;
adj[from].pb({i-1,to});
adj[to].pb({i-1,from});
}
FORE(i,1,n+1){
sort(all(adj[i]));
while(adj[i].size()>2) adj[i].pop_back();
if(adj[i].size()>=1){
int kom=adj[i][0].se;
//1.routu izle
suc[i][0][1]=kom;
if(adj[kom][0].se==i and adj[kom].size()>1){
cik[i][0][1]=2;
//successor i'nin hangi nodeundan devam edicem
}
else{
cik[i][0][1]=1;
}
}
if(adj[i].size()>=2){ //2.bir route varsa
//2.routu izle
int kom=adj[i][1].se;
suc[i][0][2]=kom;
if(adj[kom][0].se==i and adj[kom].size()>1){
cik[i][0][2]=2;
}
else{
cik[i][0][2]=1;
}
}
}
//calculate successor of each node
calc();
int q=Q;
vi qq, cc;
FOR(i,q){
int deg=G[i];
qq.pb(deg);
cc.pb(deg);
}
sort(all(qq));
map<int,int> cev;
FORE(i,1,n+1) cur[i]=i;
int once=0;
FORE(i,1,n+1) rt[i]=1;
for(auto ell:qq){
int el=ell;
el-=once;
FOR(i,MAXK){
if((1<<i)>el) break;
if(el&(1<<i)){
FORE(nd,1,n+1){
if(cur[nd]==-1) continue;
int node=cur[nd];
cur[nd]=suc[node][i][rt[nd]];
rt[nd]=cik[node][i][rt[nd]];
}
}
}
if(el!=0){
FORE(nd,1,n+1){
if(cur[nd]==p) cev[ell]++;
}
}
once+=el;
}
for(auto el:cc){
answer(cev[el]);
}
}
