#include using namespace std; #define rep(i,n) REP(i,0,n) #define REP(i,s,e) for(int i=(s); i<(int)(e); i++) #define repr(i, n) REPR(i, n, 0) #define REPR(i, s, e) for(int i=(int)(s-1); i>=(int)(e); i--) #define all(r) r.begin(),r.end() #define rall(r) r.rbegin(),r.rend() typedef long long ll; typedef vector vi; typedef vector vl; const ll INF = 1e18; const ll MOD = 1e9 + 7; template T chmax(T& a, const T& b){return a = (a > b ? a : b);} template T chmin(T& a, const T& b){return a = (a < b ? a : b);} #define DEBUG_MODE #ifdef DEBUG_MODE #define dump(x) cout << #x << " : " << x << " " #define dumpL(x) cout << #x << " : " << x << '\n' #define LINE cout << "line : " << __LINE__ << " " #define LINEL cout << "line : " << __LINE__ << '\n' #define dumpV(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << " " #define dumpVL(v) cout << #v << " : ["; for(auto& t : v) cout << t << ", "; cout<<"]" << endl #define STOP assert(false) #else #define dump(x) #define dumpL(x) #define LINE #define LINEL #define dumpV(v) #define dumpVL(v) #define STOP assert(false) #endif #define mp make_pair namespace std { template ostream &operator <<(ostream& out, const pair& a) { out << '(' << a.fi << ", " << a.se << ')'; return out; } } //有向、無向グラフ共通クラス(隣接リスト) struct Graph { int n; using WEIGHT_TYPE = long long; const WEIGHT_TYPE INF = 1e18; struct Edge { int to; WEIGHT_TYPE weight; }; struct Edge2 { int from; int to; WEIGHT_TYPE weight; }; vector> es; Graph(int n) : n(n), es(n) {} // dijkstra O(E log V) vector dijkstra(int s) { vector d(n, INF); d[s] = 0; using P = pair; priority_queue, greater

> q; q.push({0LL, s}); while(!q.empty()) { auto p = q.top(); q.pop(); int cur = p.second; auto cost = p.first; if(d[cur] < p.first) continue; for(auto &e : es[cur]) { int to = e.to; auto dist = e.weight + cost; if(dist < d[to]) { d[to] = dist; q.push({dist, to}); } } } return d; } // dijkstra O(V^2) vector dijkstra2(int s) { vector d(n, INF); d[s] = 0; vector used(n); auto mat = getEdgeMat(); while(1) { int cur = -1; rep(i, n) { if(used[i]) continue; if(cur == -1 || d[i] < d[cur]) cur = i; } if(cur == -1) break; used[cur] = 1; rep(i, n) { chmin(d[i], d[cur] + mat[cur][i]); } } return d; } // warshall_floyd O(n^3) vector> warshall_floyd() { // vector> d(n, vector(n, INF)); // rep(i, n) d[i][i] = 0LL; // rep(i, n) for (auto && e : es[i]) { // int j = e.to; // chmin(d[i][j], e.weight); // } auto d = getEdgeMat(); rep(k, n) rep(i, n) rep(j, n) { chmin(d[i][j], d[i][k] + d[k][j]); } return d; } // 頂点sから到達できるか vector getVisitable(int s) { vector ret(n); queue q; q.push(s); ret[s] = true; while(!q.empty()) { auto cur = q.front(); q.pop(); for(auto &&e : es[cur]) { if(!ret[e.to]) { ret[e.to] = true; q.push(e.to); } } } return ret; } // 2部グラフ判定 bool isBipartile() { vector memo(n, -1); rep(i, n) { if(memo[i] != -1) continue; queue q; q.push(i); memo[i] = 0; while(!q.empty()) { auto v = q.front(); q.pop(); for(auto &&e : es[v]) { auto u = e.to; if(memo[u] == -1) { memo[u] = !memo[v]; q.push(u); } else if(memo[u] == memo[v]) { return false; } } } } return true; } vector> getEdgeMat() { vector> mat(n, vector(n, INF)); rep(i, n) mat[i][i] = 0; rep(i, n) { for(auto &&e : es[i]) chmin(mat[i][e.to], e.weight); } return mat; } }; // 無向グラフ struct GraphUD : public Graph { GraphUD(int n) : Graph(n) {} void add_edge(int from, int to, WEIGHT_TYPE weight) { es[from].push_back({to, weight}); es[to].push_back({from, weight}); } vector getEdge2() { vector ret; rep(i, n) for(auto &&e : es[i]) { if(i < e.to) ret.push_back({i, e.to, e.weight}); } return ret; } // 橋の検出 // http://nupioca.hatenadiary.jp/entry/2013/11/03/200006 // Calculate bridges in a undirected graph. // Assume graph is connected and has no parallel edges or self-loops. vector getBridges() { int V = n; // res: bridges vector res; // assume at least the first vertex exists vector low(V, -1); // lowest reacheable index vector pre(V, -1); // pre-order index int count = 0; // pre-order index counter // v: current node // from: parent node function dfs = [&](int v, int from) { pre[v] = count++; low[v] = pre[v]; for(auto &&e : es[v]) { int to = e.to; if(pre[to] == -1) { // destination has not been visited // visit destination and update low[v] low[v] = min(low[v], dfs(to, v)); if(low[to] == pre[to]) { // edge is not contained in a closed path -> bridge res.push_back({v, to, e.weight}); } } else { if(from == to) { // ignore a path to parent continue; } low[v] = min(low[v], low[to]); } } return low[v]; }; dfs(0, -1); // start dfs from vertex 0 return res; } }; // 有向グラフ struct GraphD : public Graph { GraphD(int n) : Graph(n) {} void add_edge(int from, int to, WEIGHT_TYPE weight) { es[from].push_back({to, weight}); } vector getEdge2() { vector ret; rep(i, n) for(auto &&e : es[i]) { ret.push_back({i, e.to, e.weight}); } return ret; } GraphD getReverseGraph() { GraphD g(n); rep(i, n) for(auto &&e : es[i]) { g.add_edge(e.to, i, e.weight); } return g; } vector> scc() { vector> res; vector cmp(n); vector vs; vector> r_es(n); rep(i, n) for(auto &&e : es[i]) { int j = e.to; r_es[j].push_back(i); } vector used(n); function dfs = [&](int v) { used[v] = true; for(auto &&e : es[v]) { int to = e.to; if(!used[to]) dfs(to); } vs.push_back(v); }; function rdfs = [&](int v, int k) { used[v] = true; cmp[v] = k; for(auto &&to : r_es[v]) { if(!used[to]) rdfs(to, k); } }; fill(all(used), 0); vs.clear(); for(int v = 0; v < n; v++) { if(!used[v]) dfs(v); } fill(all(used), 0); int k = 0; for(int i = vs.size() - 1; i >= 0; i--) { if(!used[vs[i]]) rdfs(vs[i], k++); } res.clear(); res.resize(k); for(int i = 0; i < n; i++) { res[cmp[i]].push_back(i); } return res; } // bellmanFord 負閉路があるなら, dist[s] = INF | O(VE) vector bellmanFord(int s) { vector dist(n, INF); dist[s] = 0; auto es = getEdge2(); rep(i, n) { for(auto &&e : es) { if(dist[e.to] > dist[e.from] + e.weight) { dist[e.to] = dist[e.from] + e.weight; if(i == n - 1) { dist[s] = INF; return dist; } } } } return dist; } // bellmanFord s->tの経路上に負閉路があるなら, dist[s] = INF | O(VE) vector bellmanFord2(int s, int t) { vector dist(n, INF); auto f1 = getVisitable(s); auto f2 = getReverseGraph().getVisitable(t); dist[s] = 0; auto es = getEdge2(); rep(i, n) { for(auto &&e : es) { if(!(f1[e.from] && f2[e.to])) continue; if(dist[e.to] > dist[e.from] + e.weight) { dist[e.to] = dist[e.from] + e.weight; if(i == n - 1) { dist[s] = INF; return dist; } } } } return dist; } }; int main(){ cin.tie(0); ios::sync_with_stdio(false); int w, h, n; cin >> w >> h >> n; vector r(w, vi(h)); vector c(h, vi(w)); rep(_, n) { int m; cin >> m; ++m; vi b(m); rep(i, m) cin >> b[i]; rep(i, m-1) { int sx = b[i] % w, sy = b[i] / w; int tx = b[i+1] % w, ty = b[i+1] / w; // cout << " " << b[i] << " " << sy << " " << sx << '\n'; // cout << " " << b[i+1] << " " << ty << " " << tx << '\n'; if(sx == tx) { if(sy > ty) swap(sy, ty); r[sx][sy] += 1; r[sx][ty] -= 1; // cout << "r " << sx << " " << sy << " " << ty << '\n'; } else { if(sx > tx) swap(sx, tx); c[sy][sx] += 1; c[sy][tx] -= 1; // cout << "c " << sy << " " << sx << " " << tx << '\n'; } } } rep(i, r.size()) rep(j, r[i].size()-1) r[i][j+1] += r[i][j]; rep(i, c.size()) rep(j, c[i].size()-1) c[i][j+1] += c[i][j]; GraphUD g(h * w); rep(x, w) rep(y, h-1) if(r[x][y]) { int cur = y * w + x; int nxt = cur + w; g.add_edge(cur, nxt, +1); } rep(y, h) rep(x, w-1) if(c[y][x]) { int cur = y * w + x; int nxt = cur + 1; g.add_edge(cur, nxt, +1); } auto d = g.dijkstra(0)[h * w - 1]; if(d == g.INF) cout << "Odekakedekinai.." << '\n'; else cout << d << '\n'; return 0; }