#define REP(i,n) for(int i=0; i<(int)(n); i++) #include #include inline int getInt(){ int s; scanf("%d", &s); return s; } #include using namespace std; const int inf = 1000000000; set s[1000][1000]; int dp[1000][1000]; const int _dx[] = {0,1,0,-1}; const int _dy[] = {-1,0,1,0}; #define IN(x,s,g) ((x) >= (s) && (x) < (g)) #define ISIN(x,y,w,h) (IN((x),0,(w)) && IN((y),0,(h))) int main(){ const int w = getInt(); const int h = getInt(); const int n = getInt(); REP(i,n){ const int m = getInt(); int pb = getInt(); REP(j,m){ const int px = pb % w; const int py = pb / w; const int b = getInt(); const int x = b % w; const int y = b / w; if(px == x){ const int mny = min(y, py); const int mxy = max(y, py); for(int y = mny; y < mxy; y++){ s[y][x].insert((y + 1) * w + x); s[y + 1][x].insert(y * w + x); } }else{ const int mnx = min(x, px); const int mxx = max(x, px); for(int x = mnx; x < mxx; x++){ s[y][x].insert(y * w + x + 1); s[y][x + 1].insert(y * w + x); } } pb = b; } } queue q; q.push(0); REP(i,h) REP(j,w) dp[i][j] = -1; dp[0][0] = 0; while(q.size()){ const int pos = q.front(); q.pop(); const int x = pos % w; const int y = pos / w; const int cost = dp[y][x]; //printf("%d %d: %d\n", x, y, cost); dp[y][x] = cost; REP(i,4){ const int xx = x + _dx[i]; const int yy = y + _dy[i]; if(!ISIN(xx, yy, w, h)) continue; if(dp[yy][xx] != -1) continue; if(!s[yy][xx].count(y * w + x)) continue; dp[yy][xx] = cost + 1; q.push(yy * w + xx); } } // REP(i,h){ REP(j,w) printf("%d ", dp[i][j]); puts(""); } const int ans = dp[h - 1][w - 1]; if(ans == -1){ puts("Odekakedekinai.."); }else{ printf("%d\n", ans); } return 0; }