Problem_E

#include<bits/stdc++.h>
#define ll       long long int
#define SIZE 100005
using namespace std;

vector<int>a[800002];
int c,n,m,g,t,s,d,e,vis[800002],dis[800002];

ll gra(ll t,ll g)
{
  memset(vis,0,sizeof(vis));
  for(int i=1; i<=n; i++)
          dis[i]=1000000000;
  queue<int> q;
  q.push(t);
  vis[t]=1;
  dis[t]=0;
  while(!q.empty())
  {
            int u=q.front();
            //cout<<"u= "<<u<<endl;
            q.pop();
            for(int k=0; k<a[u].size(); k++)
            {    int v=a[u][k];
                   if(dis[u]+1<dis[v])
                   {dis[v]=dis[u]+1;
                    //cout<<k<<" "<<dis[v]<<endl;
                    //cout<<v<<endl;
                    vis[v]=1;
                     q.push(v);
                   }
            }
  }
  return dis[g];
}
int main()
{
cin>>c;
ll i=1;
while(i<=c)
{     cin>>n>>m;
      ll cn[m];
      for(int j=1; j<=m; j++)
      {
       cin>>cn[j];
      }
       for(int j=1; j<=n; j++)
      {
       cin>>d>>e;
       a[d].push_back(e);
       a[e].push_back(d);

      }
      cin>>t>>g;
        int mn=gra(t,g);
        if(vis[g])
        {
                  if((cn[g]-mn)>0)
                    cout<<"Case "<<i<<": "<<cn[g]-mn<<"\n";
                  else
                    cout<<"Case "<<i<<": Don't travel\n";
        }
        else
          cout<<"Case "<<i<<": Path not found\n";

          i++;
}


}