#include <bits/stdc++.h>
using namespace std;
typedef pair<int, int> pii;
class edge {
public:
int x, w;
bool dir; // 1 if guards go in this direction
edge(int x, int w, bool d = 0) : x(x), w(w), dir(d) {}
};
pair<pii, bool> get_pair(const edge e) {
return pair<pii, bool>(pii(e.x, e.w), e.dir);
}
bool operator<(const edge &a, const edge &b) {
return get_pair(a) < get_pair(b);
}
const int MAXN = 25e4;
const int inf = 1e9;
set<edge> edges[MAXN];
// int prv[MAXN];
// int nxt[MAXN];
int sz[MAXN];
int mod[MAXN];
int dist[MAXN];
int n, m, k;
void prune(int i) {
if (i == n-1 || i == 0 || edges[i].size() != 2) return;
edge l = *edges[i].begin();
edge r = *edges[i].rbegin();
if (sz[i] > 0) {
if (l.dir) swap(l, r);
// nxt[l.x] = r.x;
// prv[r.x] = l.x;
}
edges[i].clear();
edges[l.x].erase(edge(i, l.w, (sz[i] > 0)));
edges[r.x].erase(edge(i, r.w));
if (l.x != r.x) {
edges[l.x].insert(edge(r.x, l.w+r.w, (sz[i] > 0)));
edges[r.x].insert(edge(l.x, l.w+r.w));
}
prune(l.x);
prune(r.x);
}
bool cont(int l, int r, int p, int M) {
if (l > r) return (l <= p) || (p <= r)
return (l <= p && p <= r);
}
int main() {
ios_base::sync_with_stdio(false); cin.tie(NULL);
cin >> n >> m;
for (int i = 0; i < m; i++) {
int x, y; cin >> x >> y;
x--; y--;
edges[x].insert(edge(y, 1));
edges[y].insert(edge(x, 1));
}
cin >> k;
for (int i = 0; i < k; i++) {
int t; cin >> t;
vector<int> v;
for (int j = 0; j < t; j++) {
int x; cin >> x; x--;
v.push_back(x);
}
for (int j = 0; j < t; j++) {
// nxt[v[j]] = v[(j+1)%t];
// prv[v[j]] = v[(j+n-1)%t];
edges[v[j]].erase(edge(v[(j+1)%t], 1));
edges[v[j]].insert(edge(v[(j+1)%t], 1, 1));
sz[v[j]] = v.size();
mod[v[j]] = j;
}
}
for (int i = 0; i < n; i++) {
if (edges[i].size() == 2) prune(i);
}
fill(dist, dist+n, inf);
dist[0] = 0;
priority_queue<pii, vector<pii>, greater<pii>> pq;
pq.push(pii(0, 0));
while (!pq.empty()) {
pii t = pq.top();
pq.pop();
int cur = t.second;
if (dist[cur] < t.first) continue;
for (edge p: edges[cur]) {
int nxtval = p.x;
int ndist;
if (sz[cur] == 0) ndist = dist[cur]+p.w;
else if (sz[nxtval] == 0 || p.dir) {
ndist = dist[cur]+p.w+((dist[cur]%sz[cur])==mod[cur]);
}
else {
if (2*p.w+1 >= sz[cur]) continue;
int mx_pos = ((mod[cur]+sz[cur]-2*p.w-1) % sz[cur]);
int cur_pos = (dist[cur] % sz[cur]);
if (cont((mod[cur]+1)%sz[cur], mx_pos, cur_pos, sz[cur])) ndist = dist[cur]+p.w;
else ndist = dist[cur]+p.w + ((mod[cur]+1+sz[cur]-cur_pos)%sz[cur]);
}
if (ndist < dist[nxtval]) {
dist[nxtval] = ndist;
pq.push(pii(ndist, nxtval));
}
/*
Case 1: This isn't on a cycle. ez
Case 2: this is on a cycle. add 1 if we arrived right as the watchmen arrived
Case 3: both of these are on the same cycle and the watchmen goes from nxt to cur.
*/
}
}
if (dist[n-1] == inf) cout << "impossible\n";
else cout << dist[n-1] << "\n";
}
Compilation message
watchmen.cpp: In function 'bool cont(int, int, int, int)':
watchmen.cpp:53:40: error: expected ';' before 'return'
53 | if (l > r) return (l <= p) || (p <= r)
| ^
| ;
54 | return (l <= p && p <= r);
| ~~~~~~
