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