#include #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 #include using namespace std; int xs[1001][1001]; int ys[1001][1001]; int dist[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; dist[i][j] = 1000000000; } 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, h+1) { int c = 0; REP(i, w+1) { c+=ys[i][j]; ys[i][j] = c; } } if(!(xs[0][0] || ys[0][0])) { cout << "Odekakedekinai.." << endl; return 0; } priority_queue,vector>,greater>> nexts; nexts.push(make_tuple(-0,0,0)); while(!nexts.empty()) { const auto c = nexts.top(); nexts.pop(); const int x = get<1>(c); const int y = get<2>(c); int z = get<0>(c); if(z>dist[x][y]) { continue; } if(x == w-1 && y == h-1) { cout << z << endl; return 0; } z++; if(x > 0 && ys[x-1][y] && dist[x-1][y]>z) { dist[x-1][y] = z; nexts.push(make_tuple(z, x-1,y)); } if(x < w-1 && ys[x][y] && dist[x+1][y]>z) { dist[x+1][y] = z; nexts.push(make_tuple(z,x+1,y)); } if(y > 0 && xs[x][y-1] && dist[x][y-1] > z) { dist[x][y-1] = z; nexts.push(make_tuple(z, x,y-1)); } if(y < h-1 && xs[x][y] && dist[x][y+1] > z) { dist[x][y+1] = z; nexts.push(make_tuple(z, x,y+1)); } } cout << "Odekakedekinai.." << endl; return 0; }