#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]; 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-1;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, 1001) { int c = 0; REP(j, 1001) { c+=xs[i][j]; if(c > 0) { ok[i][j] = true; } } } REP(j, 1001) { int c = 0; REP(i, 1001) { c+=ys[i][j]; if(c > 0) { ok[i][j] = true; } } } p shifts[4] = {p(0,-1), p(0,1), p(1,0),p(-1,0)}; if(!ok[0][0]) { cout << "Odekakedekinai.." << endl; return 0; } queue

nexts; nexts.push(p(0,0)); int current = 0; while(!nexts.empty()) { queue

t; while(!nexts.empty()) { p c = nexts.front(); nexts.pop(); if(visit[c.first][c.second]) { continue; } visit[c.first][c.second] = true; REP(i, 4) { auto nx = c.first + shifts[i].first; auto ny = c.second + shifts[i].second; if(nx >= 0 && nx < w) { if(ny >= 0 && ny < h) { if(nx == w-1) { if(ny == h - 1) { cout << (current+1) << endl; return 0; } } if(ok[nx][ny] && !visit[nx][ny]) { t.push(p(nx,ny)); } } } } } current++; nexts = t; } cout << "Odekakedekinai.." << endl; return 0; }