#include <bits/stdc++.h>
using namespace std;
const int LOG = 30;
#define ll long long
#define pb push_back
#define ff first
#define ss second
#define MAXM 150005
#define sz size()
#include "garden.h"
#include "gardenlib.h"
pair <int, int> dp1[MAXM][LOG], dp2[MAXM][LOG];
vector <int> adj[MAXM];
//void answer(int x) {
// cout << x << " ";
//}
void count_routes(int N, int M, int P, int R[][2], int Q, int G[]) {
for (int i = 0; i < M; ++i) {
int u = R[i][0], v = R[i][1];
adj[u].pb (v);
adj[v].pb (u);
}
for (int i = 0; i < N; ++i) {
if ((int)adj[i].sz) {
dp1[i][0].ff = adj[i][0];
dp1[i][0].ss = i;
if ((int)adj[i].sz > 1) {
dp2[i][0].ff = adj[i][1];
dp2[i][0].ss = i;
}
else dp2[i][0] = dp1[i][0];
}
}
for (int j = 1; j < LOG; ++j) {
for (int i = 0; i < N; ++i) {
int x = dp1[i][j - 1].ff;
int y = dp1[i][j - 1].ss;
if (adj[x][0] == y) {
dp1[i][j] = dp2[x][j - 1];
}
else {
dp1[i][j] = dp1[x][j - 1];
}
x = dp2[i][j - 1].ff;
y = dp2[i][j - 1].ss;
if (adj[x][0] == y) {
dp2[i][j] = dp2[x][j - 1];
}
else {
dp2[i][j] = dp1[x][j - 1];
}
}
}
for (int ii = 0; ii < Q; ++ii) {
int val = G[ii];
int jogap = 0;
for (int i = 0; i < N; ++i) {
int hp = i;
int pr = -1;
for (int j = LOG - 1; j >= 0; j--) {
if (val>>j&1) {
if (adj[hp][0] == pr) {
auto tr = dp2[hp][j];
hp = tr.ff;
pr = tr.ss;
}
else {
auto tr = dp1[hp][j];
hp = tr.ff;
pr = tr.ss;
}
}
}
if (hp == P) {
jogap++;
}
}
answer (jogap);
}
}
//
//#include <stdio.h>
//#include <stdlib.h>
//
//#define MAX_M 1000000
//#define MAX_Q 2000
//
//static int N, M, P, Q;
//static int R[MAX_M][2];
//static int G[MAX_Q];
//
//void read_input()
//{
// int i;
// scanf("%d %d %d",&N,&M,&P);
// for(i=0; i<M; i++)
// scanf("%d %d",&R[i][0],&R[i][1]);
// scanf("%d",&Q);
// for(i=0; i<Q; i++)
// scanf("%d",&G[i]);
//}
//
//
//
//int main() {
// freopen("input.txt", "r", stdin);
// read_input();
// count_routes(N,M,P,R,Q,G);
// return 0;
//}
