#include #include #include #include #include #include #define repeat(i,n) for (int i = 0; (i) < (n); ++(i)) #define repeat_from(i,m,n) for (int i = (m); (i) < (n); ++(i)) using namespace std; const int UP = 0; const int DOWN = 1; const int RIGHT = 2; const int LEFT = 3; const int dy[4] = { -1, 1, 0, 0 }; const int dx[4] = { 0, 0, 1, -1 }; struct state_t { int dist; int16_t y, x; }; int main() { int w, h, n; scanf("%d%d%d", &w, &h, &n); vector > g(h, vector(w)); repeat (i,n) { int m; scanf("%d", &m); vector b(m+1); repeat (i,m+1) scanf("%d", &b[i]); repeat (i,m) { int y0 = b[i] / w; int y1 = b[i+1] / w; int x0 = b[i] % w; int x1 = b[i+1] % w; if (y0 == y1) { int y = y0; repeat_from (z,min(x0,x1),max(x0,x1)) { g[y][z ] |= (1 << RIGHT); g[y][z+1] |= (1 << LEFT); } } else if (x0 == x1) { int x = x0; repeat_from (z,min(y0,y1),max(y0,y1)) { g[z ][x] |= (1 << DOWN); g[z+1][x] |= (1 << UP); } } else { assert (false); } } } vector > dist(h, vector(w)); queue que; dist[0][0] = 1; que.push((state_t) { 1, 0, 0 }); while (not que.empty()) { state_t s = que.front(); que.pop(); repeat (i,4) { if (not (g[s.y][s.x] & (1 << i))) continue; // the edge doesn't exist state_t t; t.dist = s.dist + 1; t.y = s.y + dy[i]; t.x = s.x + dx[i]; if (t.y < 0 or h <= t.y or t.x < 0 or w <= t.x) continue; if (dist[t.y][t.x]) continue; dist[t.y][t.x] = t.dist; que.push(t); } } if (dist[h-1][w-1]) { printf("%d\n", dist[h-1][w-1] - 1); } else { puts("Odekakedekinai.."); } return 0; }