#include<iostream>#include<cstring>#include<cstdio>#include<vector>#include<queue>using namespace std;struct node{ int i,pathnum; vector<int> insnum;};int n,m,k,path[5010],ins[5010];queue<node> q;bool visited[5010];vector<int> adr[5010];node pos[5010];int main(){ int i,j,a,b; node tmp; while(scanf("%d%d%d",&m,&n,&k)!=EOF){ memset(visited,0,sizeof(visited)); memset(path,0,sizeof(path)); while(!q.empty())q.pop(); for(i=1;i<=n;i++)adr[i].clear(); for(i=1;i<=n;i++){ scanf("%d%d",&a,&b); ins[a]=b; } for(i=1;i<=m;i++){ scanf("%d%d",&a,&b); adr[a].push_back(b); adr[b].push_back(a); } for(i=1;i<=n;i++){pos[i].i=i;pos[i].insnum.clear();pos[i].pathnum=0;} pos[1].insnum.push_back(ins[1]);pos[1].pathnum=1; q.push(pos[1]); path[1]=0; while(!q.empty()){ tmp=q.front();q.pop(); if(tmp.i==n)break; for(j=0;j<adr[tmp.i].size();j++){ i=adr[tmp.i][j]; if(!visited[i]){ path[i]=path[tmp.i]+1; for(int j0=0;j0<tmp.insnum.size();j0++){ if(tmp.insnum[j0]+ins[i]<=k){ pos[i].pathnum++; pos[i].insnum.push_back(tmp.insnum[j0]+ins[i]); } } if(pos[i].pathnum>0){ visited[i]=1; q.push(pos[i]); } } else if(path[tmp.i]+1==path[i]){ for(int j0=0;j0<tmp.insnum.size();j0++){ if(tmp.insnum[j0]+ins[i]<=k){ pos[i].pathnum++; pos[i].insnum.push_back(tmp.insnum[j0]+ins[i]); } } } } } if(pos[n].pathnum!=0)printf("%dn",pos[n].pathnum); else printf("Impossible!n"); }}
