#include using namespace std; #undef _P #define _P(...) (void)printf(__VA_ARGS__) #define FOR(i,a,b) for (int i = (a); i < (b); i++) #define RFOR(i,a,b) for (int i = (b)-1; i >= (a); i--) #define REP(i,n) for (int i = 0; i < (n); i++) #define RREP(i,n) for (int i = (n)-1; i >= 0; i--) #define ALL(x) (x).begin(), (x).end() #define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++) #define RITR(x,c) for(__typeof(c.rbegin()) x=c.rbegin();x!=c.rend();x++) #define MIN(a,b) (a < b ? a : b) #define MAX(a,b) (a > b ? a : b) #define BIT(n) (1LL<<(n)) #define SZ(x) ((int)(x).size()) #define ZERO(a) memset(a,0,sizeof(a)) #define MINUS(a) memset(a,0xff,sizeof(a)) #define FILL(a,v) memset(a,v,sizeof(a)) #define bitcount(b) __builtin_popcount(b) #define GCD(a,b) (__gcd(a,b)) #define GCD3(a,b,c) (GCD(GCD(a,b), c)) #define LCM(a,b) (a/GCD(a,b)*b) #define LCM3(a,b,c) LCM(LCM(a,b),c) #define MOD 1000000007 template inline bool amax(T &a, const T &b) { if (a < b) { a = b; return 1; } return 0; } template inline bool amin(T &a, const T &b) { if (b < a) { a = b; return 1; } return 0; } typedef long long ll; // ------------------------------------- typedef pair II; int W, H, N; int C[1001010]; int VI[1010][1010]; int HI[1010][1010]; vector E[1001010]; int main() { cin.tie(0); ios::sync_with_stdio(false); scanf("%d %d %d", &W, &H, &N); ZERO(VI); ZERO(HI); REP(i, N) { int M; scanf("%d", &M); int B[1010]; REP(j, M+1) { scanf("%d", B+j); } REP(j, M) { int f = B[j]; int t = B[j+1]; int mi = MIN(f, t); int ma = MAX(f, t); if (f / W == t / W) { // yoko int l = mi % W; int r = ma % W; int y = mi / W; HI[y][l]++; HI[y][r]--; } else { // tate int b = mi / W; int t = ma / W; int x = mi % W; VI[b][x]++; VI[t][x]--; } } } REP(y, H) { REP(x, W) { if (x) HI[y][x] += HI[y][x-1]; if (y) VI[y][x] += VI[y-1][x]; if (HI[y][x]) { E[y*W+x].push_back(y*W+x+1); E[y*W+x+1].push_back(y*W+x); } if (VI[y][x]) { E[y*W+x].push_back(y*W+x+W); E[y*W+x+W].push_back(y*W+x); } } } // ver dijkstra priority_queue, greater > q; FILL(C, 0x3f); q.push({0, 0}); while (!q.empty()) { int c = q.top().first; int p = q.top().second; q.pop(); if (c >= C[p]) continue; //_P("%d,%d\n", p, c); if (p == W * H - 1) { cout << c << '\n'; return 0; } C[p] = c; auto& ep = E[p]; int sz = SZ(ep); REP(i, sz) { int n = ep[i]; if (c + 1 < C[n]) { q.push({c+1, n}); } } } cout << "Odekakedekinai.." << '\n'; return 0; }