//#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector")
#include <bits/stdc++.h>
#include<set>
#include <array>
using namespace std;
#define ll long long
#define endl '\n'
#define mod 1000000007
#define pb push_back
#define ff first
#define ss second
#define con continue
#define ub upper_bound
#define lb lower_bound

#define si(x) int(x.size())
#define sum_all(a)     ( accumulate ((a).begin(), (a).end(), 0ll))
#define mine(a)    (*min_element((a).begin(), (a).end()))
#define maxe(a)    (*max_element((a).begin(), (a).end()))
#define mini(a)    ( min_element((a).begin(), (a).end()) - (a).begin())
#define maxi(a)    ( max_element((a).begin(), (a).end()) - (a).begin())
#define lowb(a, x) ( lower_bound((a).begin(), (a).end(), (x)) - (a).begin())
#define uppb(a, x) ( upper_bound((a).begin(), (a).end(), (x)) - (a).begin())
const double pi = 2 * acos(0.0);
const int dx[] = { -1, 0, 1, 0 };
const int dy[] = { 0, -1, 0, 1 };

const int dx8[] = { -1, 0, 1, 0,1,1,-1,-1 };
const int dy8[] = { 0, -1, 0, 1,1,-1,1,-1 };

ll min(ll a,ll b)
{
    if(a<b)return a;
    return b; 
}
ll max(ll a,ll b)
{
    if(a>b)return a;
    return b; 
}
ll ceil1(ll a,ll b)
{
    return(a+b-1)/b;
}
void read(vector<ll> & arr)
{
  for(ll i=0;i<si(arr);i++)
    cin >> arr[i];

}

void read_graph(vector<vector<ll>>& g, ll m)
{
  while(m--)
  {
    ll x,y; cin >> x>> y ;
    x--,y--; 
    g[x].pb(y);
    g[y].pb(x);
  }
}
void solve()
{
 
  int n,m;
  cin >> n >> m;

  vector<vector<pair<char,int>>> g(n);
  for(int i=0;i<m;i++)
  {
     int x,y;
     char ch;
     cin >> x >> y >> ch ;
     x--,y--;
     g[x].push_back({ch,y});
     g[y].push_back({ch,x});

  }
   using node= pair<int,pair<int,int>>;
   vector<vector<bool>> vis(n,vector<bool>(n));


   queue<node> q ;
   q.push({0,{0,n-1}});
   int ans=INT_MAX;
   while(!q.empty())
   {
     auto a1=q.front();
     q.pop(); 

     auto a=a1.ss.ff,b=a1.ss.ss;
     auto dis= a1.ff; 
     if(a==b) 
     {
        ans=min(ans,dis*2);
        continue;
     }
     if(vis[a][b]) continue;
      vis[a][b]=true; 
      vis[b][a]=true;
      bool f=false;
     for(auto info :g[a])
     {
         auto v=info.ss;
         if(v==b)
         {
           f=true;
           break;
         }
     }
  if(f)
  {
     ans=min(ans,dis*2+1);
     continue;
  }
     for(auto info :g[a])
        for(auto info2 : g[b])
        {
            if(info.ff!=info2.ff) continue;
            if(vis[info.ss][info2.ss]) continue; 
            q.push({dis+1,{info.ss,info2.ss}});
        }

   }
  if(ans==INT_MAX) ans=-1;
  cout << ans << endl;
  return ; 
}


int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
#ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    freopen("output.txt", "w", stdout);
#endif
    //int t; cin >> t; while (t--)
    solve();

}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> P;
const ll MOD = 1e9+7;
const ll INF = 1e18;
#define rep(i,m,n) for(ll i = (m); i <= (n); i++)
#define zep(i,m,n) for(ll i = (m); i < (n); i++)
#define rrep(i,m,n) for(ll i = (m); i >= (n); i--)
#define print(x) cout << (x) << endl;
#define printa(x,m,n) for(int i = (m); i <= n; i++){cout << (x[i]) << " ";} cout<<endl;

ll n, p[2 * 101 * 1001], db[20][2 * 101 * 1001], iv[2 * 101 * 1001], dep[2 * 101 * 1001], Q;
vector<ll> v, ans;

int main(){
    cin.tie(0); ios::sync_with_stdio(false);
    
    cin >> n;
    zep(i, 1, n){cin >> p[i]; p[i]--;}

    vector<vector<ll>> g(n);
    zep(i, 1, n)g[p[i]].push_back(i);
    //zep(i, 0, n){zep(j, 0, g[i].size())cout << g[i][j] << " "; cout << endl;}
    queue<ll> q;
    iv[0] = v.size();
    q.push(0);
    v.push_back(0);

    while(!q.empty()){
        ll at = q.front(); q.pop();
        
        db[0][iv[at]] = v.size();
        zep(i, 0, g[at].size()){
            iv[g[at][i]] = v.size();
            v.push_back(g[at][i]);
            q.push(g[at][i]);
            dep[g[at][i]] = dep[at] + 1;
        }
    }
    db[0][n] = v.size();

    zep(j, 1, 20){
        rep(i, 0, n){
            db[j][i] = db[j - 1][db[j - 1][i]];
        }
    }
    
    cin >> Q;
    while(Q--){
        ll u, d; cin >> u >> d; u--;
        d -= dep[u];
        
        if(d < 0){
            ans.push_back(0); continue;
        }

        ll l = iv[u], r = iv[u] + 1;
        rrep(j, 19, 0){
            if(d & (1LL << j)){
                l = db[j][l];
                r = db[j][r];
            }
        }
        ans.push_back(r - l);
    }

    zep(i, 0, ans.size())print(ans[i])
    
    return 0;
}