#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]; if(c > 0) { ok[i][j] = true; } } } REP(j, w+1) { int c = 0; REP(i, h+1) { c+=ys[i][j]; if(c > 0) { ok[i][j] = true; } } } REP(i, w)REP(j, h) { //cout << ok[i][j] << endl; } p shifts[4] = {p(0,-1), p(0,1), p(1,0),p(-1,0)}; if(!ok[0][0] || ok[w-1][h-1]) { cout << "Odekakedekinai.." << endl; return 0; } queue nexts; nexts.push(xyz(0,0,0)); visit[0][0] = true; while(!nexts.empty()) { xyz c = nexts.front(); nexts.pop(); REP(i, 4) { auto nx = c.x + shifts[i].first; auto ny = c.y + shifts[i].second; if(nx >= 0 && nx < w) { if(ny >= 0 && ny < h) { if(nx == w-1) { if(ny == h - 1) { cout << (c.z+1) << endl; return 0; } } if(ok[nx][ny] && !visit[nx][ny]) { nexts.push(xyz(nx,ny,c.z+1)); visit[nx][ny] = true; } } } } } cout << "Odekakedekinai.." << endl; return 0; }