刚从 modinte 那里学到的广义 dijkstra。注意到一定不会有路径形如 \(x \to y \to x\)，这样等价于 \(x\) 在原地等上两个时刻，我们记 \(d_i\) 表示到达 \(i\) 节点需要的最少时间。建图，边权为当前这一条边在哪一个历史时刻。然后用一个 set 来存下每个历史时刻在第几次时间旅行后是这个时刻，那么直接跑最短路，转移是对于一条边 \((u,v,w)\)，当前 \(d_u = x\)，那要找到最小的 \(i > x\) 且第 \(i\) 次时间旅行到达的是历史时刻 \(w\)，然后就有 \(d_{v} = \min \{ d_v,i + 1 \}\)，这个过程可以直接在 set 里做一个 lower_bound。根据 dijkstra 的特性，每次从堆中取出的一定是当前最优的节点，因此正确性显然，复杂度 \(\mathcal O(m (\log n + \log t))\)。
#include<bits/stdc++.h>
#define int long long
#define ull unsigned long long
#define ui unsigned int
#define ld long double
#define power(x) ((x)*(x))
#define eb emplace_back
#define pb pop_back
#define mp make_pair
#define fi first
#define se second
#define TT template<typename T>
#define TA template<typename T,typename ...Args>
#define dbg(x) cerr<<"In Line "<<__LINE__<<" the "<<#x<<" = "<<x<<'\n';
using namespace std;
using pii=pair<int,int>;
using pdi=pair<double,int>;
using piii=pair<pair<int,int>,int>;
bool Mbe;
namespace IO
{
inline int read()
{
int s=0,w=0; char c=getchar();
while(!isdigit(c)) w|=c=='-',c=getchar();
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
return s*(w?-1:1);
}
TT inline void read(T &s)
{
s=0; int w=0; char c=getchar();
while(!isdigit(c)) w|=c=='-',c=getchar();
while(isdigit(c)) s=(s*10)+(c^48),c=getchar();
s*=w?-1:1;
}
TA inline void read(T &x,Args &...args) {read(x),read(args...);}
TT inline void write(T x,char ch=' ')
{
if(x<0) x=-x,putchar('-');
static char stk[30]; int top=0;
do stk[top++]=x%10+'0',x/=10; while(x);
while(top) putchar(stk[--top]);
if(ch!='~') putchar(ch);
}
}
using namespace IO;
namespace MTool
{
static const int Mod=998244353;
TT inline void Swp(T &a,T &b) {static T t=a;a=b;b=t;}
TT inline void cmax(T &a,T b) {a=max(a,b);}
TA inline void cmax(T &a,T b,Args ...args) {a=max({a,b,args...});}
TT inline void cmin(T &a,T b) {a=min(a,b);}
TA inline void cmin(T &a,T b,Args ...args) {a=min({a,b,args...});}
TT inline T Cadd(T a,T b) {return a+b>=Mod?a+b-Mod:a+b;}
TT inline T Cdel(T a,T b) {return a-b<0?a-b+Mod:a-b;}
TT inline T Cmul(T a,T b) {return a*b%Mod;}
TT inline T Cmod(T a) {return (a%Mod+Mod)%Mod;}
TT inline void Madd(T &a,T b) {a=a+b>=Mod?a+b-Mod:a+b;}
TT inline void Mdel(T &a,T b) {a=a-b<0?a-b+Mod:a-b;}
TT inline void Mmul(T &a,T b) {a=a*b%Mod;}
TT inline void Mmod(T &a) {a=(a%Mod+Mod)%Mod;}
TA inline T Cadd(T a,T b,Args ...args) {return Cadd(Cadd(a,b),args...);}
TA inline T Cdel(T a,T b,Args ...args) {return Cdel(Cdel(a,b),args...);}
TA inline T Cmul(T a,T b,Args ...args) {return Cmul(Cmul(a,b),args...);}
TA inline void Madd(T &a,T b,Args ...args) {Madd(a,Cadd(b,args...));}
TA inline void Mdel(T &a,T b,Args ...args) {Mdel(a,Cadd(b,args...));}
TA inline void Mmul(T &a,T b,Args ...args) {Mmul(a,Cmul(b,args...));}
TT inline T qpow(T a,T b) {int res=1; while(b) {if(b&1) Mmul(res,a); Mmul(a,a); b>>=1;} return res;}
TT inline T qmul(T a,T b) {int res=0; while(b) {if(b&1) Madd(res,a); Madd(a,a); b>>=1;} return res;}
TT inline T spow(T a,T b) {int res=1; while(b) {if(b&1) res=qmul(res,a); a=qmul(a,a); b>>=1;} return res;}
TT inline void exgcd(T A,T B,T &X,T &Y) {if(!B) return X=1,Y=0,void(); exgcd(B,A%B,Y,X),Y-=X*(A/B);}
TT inline T Ginv(T x) {T A=0,B=0; exgcd(x,Mod,A,B); return Cmod(A);}
}
using namespace MTool;
inline void file()
{
freopen(".in","r",stdin);
freopen(".out","w",stdout);
}
namespace LgxTpre
{
constexpr int MAX=200010;
constexpr int inf=2147483647;
constexpr int INF=4557430888798830399;
int n,t,m,x,y;
vector<pii> G[MAX];
set<int> s[MAX];
priority_queue<pii> q;
int dis[MAX],vis[MAX];
inline void lmy_forever()
{
read(n,t);
for(int i=1;i<=t;++i) {read(m); for(int j=1;j<=m;++j) read(x,y),G[x].eb(mp(y,i)),G[y].eb(mp(x,i));}
read(m),memset(dis,0x3f,sizeof dis),q.emplace(mp(0,1)),dis[1]=0;
for(int i=1;i<=m;++i) read(x),s[x].insert(i-1);
while(!q.empty())
{
auto [_,now]=q.top(); q.pop();
if(vis[now]) continue;
vis[now]=1;
for(auto [to,tim]:G[now])
{
auto D=s[tim].lower_bound(dis[now]);
if(D==s[tim].end()) continue;
if(dis[to]>*D+1) dis[to]=*D+1,q.emplace(mp(-dis[to],to));
}
}
write(dis[n]==INF?-1:dis[n],'\n');
}
}
bool Med;
signed main()
{
// file();
int Tbe=clock();
LgxTpre::lmy_forever();
int Ted=clock();
fprintf(stderr,"\nMemory: %.3lf MB",abs(&Mbe-&Med)/1024.0/1024.0);
fprintf(stderr,"\nTime: %.3lf ms",1e3*(Ted-Tbe)/CLOCKS_PER_SEC);
return (0-0);
}