#include <iostream>
#include <fstream>
#include <vector>
#include <limits.h>

using namespace std;

int n,m,t;
vector <int> a[32001];
struct oferta { int p,s; } v[100000];

void citire()
{
    int i,x,y,j;

    ifstream f("obiective.in");
    f>>n>>m;

    for(i=0;i<=n;i++)
     for(j=0;j<=n;j++)
       a[i].push_back(1000);
    for(i=1;i<=m;i++)
    {
        f>>x>>y;
        a[x][y]=0; a[y][x]=1;
    }
    f>>t; cout<<endl;
    for(i=1;i<=t;i++)
    {
        f>>x>>y;
        v[i].p=x; v[i].s=y;
    }
    f.close();

    for(i=1;i<=n;i++)
    {
        for(j=1;j<=n;j++)
        cout<<a[i][j]<<" "; cout<<endl;
    }cout<<endl;
  //  for(i=1;i<=t;i++) cout<<v[i].p<<" "<<v[i].s<<endl; cout<<endl;
}

void dijkstra(int start,int stop)
{
   int d[32000],ok,i,j,k;
   bool viz[32000];

   for(i=1;i<=n;i++)
   {
       d[i]=a[start][i]; viz[i]=0;
   }

   for(i=1;i<=n;i++) cout<<d[i]<<" "; cout<<endl;

   d[start]=0;
   viz[start]=1;

   for(i=1;i<=n-1;i++)
   {
       int min1=1000,poz;
       for(j=1;j<=n;j++)
       {
           if(min1>d[j]&&viz[j]==0)
           {
               min1=d[j]; poz=j;
           }
       }
      // cout<<poz<<endl;
       viz[poz]=1;
       for(j=1;j<=n;j++)
       {  if(viz[j]==0)
          {
           if(d[j]>(d[poz]+a[poz][j]))
           {
               d[j]=d[poz]+a[poz][j];// cout<<"la";
           }
          }
       }
   }
  // for(i=1;i<=n;i++) cout<<d[i]<<" ";
  ofstream g("obiective.out");
  g<<d[stop]<<endl;
  g.close();
}

void rezolva()
{
    int z;

    for(z=1;z<=t;z++)
    {
      dijkstra(v[z].p,v[z].s);
    }
}

int main()
{
    citire();
    rezolva();

    return 0;
}