#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
#define ll long long
#define ull unsigned long long
#define lll __int128_t
#define ulll __uint128_t
#define ld long double
#define lld __float128
#define fi first
#define se second
#define mp make_pair
#define fast ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
template<typename T>
using V = vector<T>;
template<typename T>
using VV = V<V<T>>;
template<typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T>
using ordered_multiset = tree<T, null_type, less_equal<T>, rb_tree_tag, tree_order_statistics_node_update>;
template<typename T, typename U>
bool chmax(T &x, U v) {return (v > x)? x=v,1 : 0;}
template<typename T, typename U>
bool chmin(T &x, U v) {return (v < x)? x=v,1 : 0;}
mt19937 rnd(chrono::steady_clock::now().time_since_epoch().count());
mt19937_64 rnd64(chrono::steady_clock::now().time_since_epoch().count());
// #pragma GCC optimize("Ofast")
// #pragma GCC target("avx,avx2,fma")
// #define DEBUG
#ifdef DEBUG
#define _main "\e[36m"
#define _reset "\e[39m\n"
template<typename T>
inline void __print(T x) {cerr << x;}
template<typename T, typename U>
inline void __print(pair<T,U> x)
{
cerr << "("; __print(x.fi); cerr << ", "; __print(x.se); cerr << ")";
}
inline void _print() {}
template<typename T, typename... U>
inline void _print(T x, U... y)
{
__print(x);
if(sizeof...(y)) cerr << ", ";
_print(y...);
}
template<typename T>
inline void _print_arr(T x) {__print(x);}
template<typename T, typename... U>
inline void _print_arr(T x, int size, U... len)
{
cerr << "[";
bool has = sizeof...(len);
for(int i = 0; i < size; i++)
{
if(i) cerr << "," << (has? "\n" : " ");
_print_arr(x[i], len...);
}
cerr << "]";
}
#define _source source_location::current()
#define debug_pref(a) cerr << _main << _source.file_name() << ":" << _source.line() << ":" << _source.column() << " [" << a << "]";
#define debug(a...) {debug_pref(#a); cerr << " = ["; _print(a); cerr << "]" << _reset;}
#define debug_arr(a, sz...) {debug_pref(#a); cerr << " = "; _print_arr(a, sz); cerr << _reset;}
#endif
#ifndef DEBUG
#define debug(a...)
#define debug_arr(a, sz...)
#endif
/*
every route is a cycle that doesnt repeat nodes
so if we build block-cut tree, every route will be inside of some node
now we go from some node in block-cut to another
the only difficult question, is how do we navigate inside of nodes
we know there exists a cycle containing any pairs of nodes, say we found cycle containing 0 and n-1
ditch that idea, ive found better
the only issue on a direct path from 0 and n-1 are watchment
so how about, before you enter a node on a path of a watchman, you wait max 1 minute to make sure you dont intersect with him, and then you just continue
it works when we go in the same direction as watchman, otherwise its more complicated
its seems there are three cases when you have to go "against the flow":
1. you can just walk straight and watchman will catch you
2. you wait until he passes you and then you walk straight
3. you walk with the flow until you reach desired node
can we simplify entire watchman cycle into one single node? because remember, we need MINIMUM path, meaning we have to be veeery greedy
say watcham path has k nodes
each node has some offset on a cycle, call its index
you cannot enter cycle when idx[v] % k == (t+1) % k (thats when watchman is here)
then when you enter, there are few possibilities
you either walk with the flow, or against
can i just forget all that bs and code regular dijkstra?
i cant because time matters for certain cases
we will ofcourse maybe wait one cycle when jumping on a cycle
but there are two other cases where it matters:
- waiting for a guard to go agaist the flow
- waiting before jumping on a cycle because cycle won't match when jumping on another cycle
lets forget about second case, and solve subtask where there will always be a node between two cycles
there are two cases of jumping on a cycle:
- immediate (maybe wait 1 min to pass)
- wait for pass
say we jumping on c[i] with t
immediate: t' = t + (i % k == (t+1) % k) (greediness holds)
pass: t' = t + (i-t) % k (greediness also holds)
in dp, hold extra variable x do differentiate between two states to make dijkstra consider both of them separately
on a cycle, three moves:
1. escape - regular move, might jump onto another cycle. then you have to check, whether you can wait that amount of time
2. i+1 - go with the flow, simply i++
3. i-1 - go against the flow, lets check if its possible
guard pos = t % k, our pos = i < k
this move is possible if distance to us is more than two, so (t - i) % k >= 3
is that it? if we know, that when jumping on a cycle, there are only two possibilities
we differentiate between them with some x
its really here just for that
why would you EVER wait any other amount of time? go with flow - lazy
go against the flow - first greedy move is the best
implementation
we want to know for evert node, its cycle number and its cycle offset (index)
thats kinda it
just do regular dijkstra
*/
const int MAXN = 250005;
const int MAXS = MAXN + 2250000 + 1562500;
vector<int> g[MAXN];
int cyc[MAXN];
int cyc_idx[MAXN];
int sz[MAXN];
pair<int, int> state[MAXS];
int dp[MAXS];
set<pair<int, int> > st;
int pos[MAXN];
inline void prop(int s, int d)
{
if(d >= dp[s])
return;
st.erase(mp(dp[s], s));
dp[s] = d;
st.insert(mp(dp[s], s));
}
int main()
{
fast;
int n, m; cin >> n >> m;
pair<int, int> edg[m];
for(int i = 0; i < m; i++)
{
int a, b; cin >> a >> b; a--; b--;
g[a].push_back(b);
g[b].push_back(a);
edg[i] = mp(a, b);
}
int k; cin >> k;
for(int i = 0; i < k; i++)
{
int l; cin >> l;
for(int j = 0; j < l; j++)
{
int v; cin >> v; v--;
cyc[v] = i+1;
cyc_idx[v] = j;
}
sz[i+1] = l;
}
int fin = n-1;
// make sure there's no edge inside of a component
// can be proven that its correct (i.e. waiting inside of the fictional node is not a proper answer)
// for(int i = 0; i < m; i++)
// {
// int a = edg[i].fi, b = edg[i].se;
// if(cyc[a] != cyc[b] || !cyc[a])
// continue;
// int ia = cyc_idx[a], ib = cyc_idx[b], k = sz[cyc[a]];
// if((ia+1) % k == ib)
// continue;
// if((ib+1) % k == ia)
// continue;
// g[n].push_back(a);
// g[a].push_back(n);
// g[n].push_back(b);
// g[b].push_back(n);
// debug("adding new", a, b);
// n++;
// }
int S, T;
int cur = 0;
for(int i = 0; i < n; i++)
{
if(i == 0)
S = cur;
if(i == fin)
T = cur;
pos[i] = cur;
int k = cyc[i] ? sz[cyc[i]] : 1;
for(int j = 0; j < k; j++)
{
state[cur++] = mp(i, j);
}
}
for(int i = 0; i < MAXS; i++)
{
dp[i] = 1e9;
}
dp[S] = 0;
st.insert(mp(0, S));
while(!st.empty())
{
int s = st.begin()->se;
int v = state[s].fi;
int ofs = state[s].se;
st.erase(st.begin());
int t = dp[s];
int gv = cyc[v];
int iv = cyc_idx[v];
debug(v, ofs, t);
if(gv && ofs > 1)
{
prop(pos[v] + ofs-1, t+1);
}
for(int c : g[v])
{
int gc = cyc[c];
int ic = cyc_idx[c];
if(gc == 0)
{
prop(pos[c], t+1);
continue;
}
// moving inside of the same loop
if(gc == gv)
{
int k = sz[gv];
if((iv+1) % k == ic) // going with the flow
{
prop(pos[c] + ofs, t+1);
}
else if((ic+1) % k == iv) // going aginst the flow
{
if(ofs >= 3)
{
prop(pos[c] + ofs-2, t+1);
}
}
else // jump
{
int nofs = (ic-t-1+k) % k;
int wt = 1;
if(nofs == 0)
{
nofs = k-1;
wt = 2;
}
prop(pos[c] + nofs, t+wt);
}
continue;
}
// jumping onto a loop
int kv = gv ? sz[gv] : 1, k = sz[gc];
// immediate jump
{
int wp = (t+1) % k; // warden pos when we reach c
if(wp != ic) // all good
{
prop(pos[c] + (ic - wp + k) % k, t + 1);
}
else if((wp+kv) % k != ic) // loop around once more
{
wp = (wp + kv) % k;
prop(pos[c] + (ic - wp + k) % k, t + 1 + kv);
}
}
// passing jump (i.e. waiting for guard to pass to get max ofset)
// make sense only if your loop is shorter:
// - we either jump as soon as we can (immediate jump as before)
// - we loop (our loop longer so it doesn't make sense?)
if(kv < k)
{
int wp = (t+1)%k; // pos of guard in c after we go there
int wt = (ic - t%k + k) % k; // how much time we need to wait for guard to pass c
int loops = (wt+kv-1) / kv; // how many loops we'll do
int nt = t + 1 + loops*kv; // time when we'll reach c
int nofs = (ic - nt%k + k) % k; // pos - guard pos
prop(pos[c] + nofs, nt);
}
}
}
int ans = dp[T];
if(ans == 1e9)
{
cout << "impossible";
return 0;
}
cout << ans;
}
/*
6 6
1 2
2 3
3 4
4 5
5 2
5 6
1
4 5 2 3 4
15 16
1 2
2 3
3 4
4 2
3 5
5 6
6 7
7 8
8 9
9 10
10 11
11 12
12 13
13 14
14 5
14 15
2
3 2 4 3
10 10 11 12 13 14 5 6 7 8 9
6 8
1 2
2 3
2 4
2 5
3 4
3 5
4 5
5 6
1
4 2 3 4 5
*/
