#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; typedef long long ll; #define FOR(i,a,b) for(int i=(a);i<(b);++i) #define REP(i,n) for(int i=0;i<(n);++i) #define p pair struct xyz { int x; int y; int z; xyz(int x_, int y_, int z_) : x(x_), y(y_), z(z_){} }; #include using namespace std; int xs[1001][1001]; int ys[1001][1001]; bool ok[1001][1001]; bool visit[1001][1001]; int main(){ int w, h, n; cin>>w >> h >> n; REP(i, 1001)REP(j,1001) { xs[i][j] = 0; ys[i][j] = 0; ok[i][j] = false; visit[i][j] = false; } for(int i = 0;i < n;i++) { int m; cin >> m; vector ms(m); for(int j = 0;j < m;j++) { cin >> ms[j]; } for(int j = 0;j < m;j++) { int a = ms[j]; int b = ms[j+1]; int sx = a % w; int sy = a / w; int ex = b % w; int ey = b / w; if(sx == ex) { xs[sx][min(sy, ey)] += 1; xs[sx][max(sy, ey) + 1] -= 1; } else { ys[min(sx, ex)][sy] += 1; ys[max(sx, ex)+1][sy] -= 1; } } } REP(i, w+1) { int c = 0; REP(j, h+1) { c+=xs[i][j]; xs[i][j] = c; } } REP(j, w+1) { int c = 0; REP(i, h+1) { c+=ys[i][j]; ys[i][j] = c; } } REP(i, w)REP(j, h) { //cout << ok[i][j] << endl; } if(!(xs[0][0] || ys[0][0]) || !(xs[w-1][h-2] || ys[w-2][h-1])) { cout << "Odekakedekinai.." << endl; return 0; } queue nexts; nexts.push(xyz(0,0,0)); visit[0][0] = true; while(!nexts.empty()) { const xyz c = nexts.front(); nexts.pop(); if(c.x == w-1 && c.y == h-1) { cout << c.z << endl; return 0; } if(c.x > 0 && ys[c.x-1][c.y] && !visit[c.x-1][c.y]) { nexts.push(xyz(c.x-1,c.y,c.z+1)); visit[c.x-1][c.y]=true; } if(c.x < w-1 && ys[c.x][c.y] && !visit[c.x+1][c.y]) { nexts.push(xyz(c.x+1,c.y,c.z+1)); visit[c.x+1][c.y]=true; } if(c.y > 0 && xs[c.x][c.y-1] && !visit[c.x][c.y-1]) { nexts.push(xyz(c.x,c.y-1,c.z+1)); visit[c.x][c.y-1]=true; } if(c.y < h-1 && xs[c.x][c.y] && !visit[c.x][c.y+1]) { nexts.push(xyz(c.x,c.y+1,c.z+1)); visit[c.x][c.y+1]=true; } } cout << "Odekakedekinai.." << endl; return 0; }