#include <bits/stdc++.h>
using namespace std;
#define eb emplace_back
const int N=1e6+5;
int n,m,c,p,dg[N],dg1[N],vs[N],l[N],r[N],rt[N],w[N],f[N];bool tg[N];
vector<int> e[N],e1[N],e2[N];queue<int> q;
bool chk(int u,int v)
{
	auto it=lower_bound(e1[u].begin(),e1[u].end(),v);
	return it!=e[u].end() && (*it)==v;
}
void dfs(int u)
{
	if(vs[u]) return;vs[u]=vs[0];w[vs[0]]+=dg[u]>0;
	tg[vs[0]]|=e1[u].size()>1;for(auto v:e[u]) dfs(v);
}
void dfs1(int u,int x) {l[u]=++l[0];rt[u]=x;for(auto v:e2[u]) dfs1(v,x);r[u]=l[0];}
int main()
{
	scanf("%d %d %d %d",&n,&m,&c,&p);f[0]=1;
	for(int i=1;i<=n;++i) f[i]=(1ll*f[i-1]*i+1)%p;
	for(int i=1,u,v;i<=m;++i)
		scanf("%d %d",&u,&v),++u,++v,++dg[v],e[u].eb(v),e[v].eb(u),e1[u].eb(v);
	for(int i=1;i<=n;++i) sort(e1[i].begin(),e1[i].end());
	for(int i=1;i<=n;++i) if(!dg[i]) q.push(i);
	while(!q.empty())
	{
		int u=q.front();q.pop();if(e1[u].size()>1) continue;
		for(auto v:e1[u]) {++dg1[u];e2[v].eb(u);--dg[v];if(!dg[v]) q.push(v);}
	}
	for(int i=1;i<=n;++i) if(!vs[i]) ++vs[0],dfs(i);
	for(int i=1;i<=n;++i) if(!dg1[i]) dfs1(i,i);
	for(int i=1,u,v;i<=c;++i)
	{
		scanf("%d %d",&u,&v);++u;++v;
		if(u==v) puts("1");
		else if(vs[u]!=vs[v]) puts("0");
		else if(!dg[v]) printf("%d\n",l[u]>=l[v] && r[u]<=r[v]);
		else
		{
			u=rt[u];
			if(u==v || !tg[vs[u]]) puts("1");
			else if(dg[u]) printf("%d\n",f[w[vs[u]]-2]);
			else if(chk(u,v)) printf("%lld\n",(1ll*(e1[u].size()-1)*f[w[vs[u]]-2]+1)%p);
			else printf("%lld\n",1ll*e1[u].size()*f[w[vs[u]]-2]%p);
		}
	}
	return 0;
}