#include <bits/stdc++.h>
#pragma GCC optimize("O3")
#define fr(i, a, b) for (int i = (a); i <= (b); ++i)
#define rf(i, a, b) for (int i = (a); i >= (b); --i)
#define fe(x, y) for (auto& x : y)
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define mt make_tuple
#define all(x) (x).begin(), (x).end()
#define pw(x) (1LL << (x))
#define sz(x) (int)(x).size()
using namespace std;
mt19937_64 rng(228);
#include <ext/pb_ds/assoc_container.hpp>
using namespace __gnu_pbds;
template <typename T>
using oset = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;
#define fbo find_by_order
#define ook order_of_key
template <typename T>
bool umn(T& a, T b) { return (a > b ? (a = b, 1) : 0); }
template <typename T>
bool umx(T& a, T b) { return (a < b ? (a = b, 1) : 0); }
using ll = long long;
using ld = long double;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
template <typename T>
using ve = vector<T>;
const int N = 3e5 + 5;
int n, m, k;
ve<int> g[N];
ve<int> v[N];
bool mark[N];
ve<int> dp[N];
int bad[N];
int nxt[N];
queue<array<int, 3>> q;
int main() {
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#else
ios::sync_with_stdio(0);
cin.tie(0);
#endif
cin >> n >> m;
fr (i, 1, m) {
int a, b;
cin >> a >> b;
g[a].pb(b);
g[b].pb(a);
}
cin >> k;
fr (i, 1, k) {
int sz;
cin >> sz;
v[i].resize(sz);
int idx = 0;
int prv = -1;
fe (x, v[i]) {
cin >> x;
if (prv != -1) nxt[prv] = x;
prv = x;
assert(!mark[x]);
mark[x] = 1;
dp[x].resize(sz, 1e9);
bad[x] = idx;
idx++;
}
nxt[v[i].back()] = v[i][0];
}
fr (i, 1, n) {
if (!mark[i]) {
dp[i].resize(2, 1e9);
bad[i] = -1;
nxt[i] = -1;
}
}
assert(!mark[1]);
assert(!mark[n]);
// assert(k == 1);
dp[1][0] = 0;
q.push({0, 1, 0});
// fr (i, 1, n) {
// cout << i << " " << bad[i] << "\n";
// }
while (sz(q)) {
int v = (q.front())[1];
int rem = (q.front())[2];
int t = (q.front())[0];
q.pop();
assert(dp[v][rem] == t);
assert(rem == t % sz(dp[v]));
int nt = (t + 1) % sz(dp[v]);
bool good = 0;
fe (to, g[v]) {
if (!mark[to] && min(dp[to][0], dp[to][1]) < t) {
good = 1;
break;
}
}
if (bad[v] != nt || good) {
if (dp[v][nt] > t + 1) {
dp[v][nt] = t + 1;
q.push({dp[v][nt], v, nt});
}
}
if (rem == bad[v]) continue;
fe (to, g[v]) {
int nt = (t + 1) % sz(dp[to]);
if (bad[to] == nt) continue;
if ((t + 1) % sz(dp[v]) == bad[v] && nxt[to] == v) continue;
if (to == n) {
cout << t + 1 << "\n";
return 0;
}
if (dp[to][nt] > t + 1) {
dp[to][nt] = t + 1;
q.push({dp[to][nt], to, nt});
}
}
}
int mn = *min_element(all(dp[n]));
if (mn == int(1e9)) {
cout << "impossible\n";
return 0;
}
cout << mn << "\n";
return 0;
Compilation message
watchmen.cpp: In function 'int main()':
watchmen.cpp:167:13: error: expected '}' at end of input
167 | return 0;
| ^
watchmen.cpp:54:12: note: to match this '{'
54 | int main() {
| ^
