#include using namespace std; typedef long long int ll; typedef pair P; typedef pair Pll; typedef vector Vi; //typedef tuple T; #define FOR(i,s,x) for(int i=s;i<(int)(x);i++) #define REP(i,x) FOR(i,0,x) #define ALL(c) c.begin(), c.end() #define DUMP( x ) cerr << #x << " = " << ( x ) << endl const int dr[4] = {-1, 0, 1, 0}; const int dc[4] = {0, 1, 0, -1}; #define INF 1<<30 #define MAX_V 1000010 // graph by adjacency list struct Edge { int dst, weight; Edge(int dst, int weight) : dst(dst), weight(weight) { } bool operator < (const Edge &e) const { return weight > e.weight; } }; struct Graph { int V; vector> E; Graph(int V) : V(V) { E.resize(V); } void add_edge(int src, int dst, int weight) { E[src].push_back(Edge(dst, weight)); } }; struct Node { int v, dist; Node(int v, int dist) : v(v), dist(dist) { }; bool operator < (const Node &n) const { return dist > n.dist; // reverse } }; struct ShortestPath { const Graph g; int start; vector dist; ShortestPath(const Graph g, int start) : g(g), start(start) { } void dijkstra() { std::priority_queue que; dist.resize(g.V, INF); dist[start] = 0; que.push(Node(start, 0)); while (!que.empty()) { Node n = que.top(); que.pop(); int v = n.v, cost = n.dist; if (dist[v] < cost) continue; for (Edge e : g.E[v]) { if (dist[v] + e.weight < dist[e.dst]) { dist[e.dst] = dist[v] + e.weight; que.push(Node(e.dst, dist[e.dst])); } } } } }; int main() { // use scanf in CodeForces! cin.tie(0); ios_base::sync_with_stdio(false); int W, H, N, V; cin >> W >> H >> N; V = W*H; vector curve(V, false); vector imos_w(V, 0), imos_h(V, 0); REP(i, N) { int M, prev; cin >> M >> prev; curve[prev] = true; REP(j, M) { int b; cin >> b; curve[b] = true; int p1 = prev, p2 = b; if (p1 > p2) swap(p1, p2); int r1 = p1 / W, c1 = p1 % W, r2 = p2 / W, c2 = p2 % W; //cout << '(' << r1 << ',' << c1 << ')' << ' ' << '(' << r2 << ',' << c2 << ')' << endl; if (r1 == r2) { imos_w[p1]++, imos_w[p2]--; } else if (c1 == c2) { imos_h[c1 * H + r1]++, imos_h[c2 * H + r2]--; } prev = b; } } REP(i, V-1) imos_h[i+1] += imos_h[i], imos_w[i+1] += imos_w[i]; FOR(i, 1, V-1) { int p = (i%W)*H+i/W; if ((imos_w[i-1] or imos_w[i]) and (imos_h[p-1] or imos_h[p])) curve[i] = true; } //REP(i, V) cout << curve[i] << (i == V-1 ? '\n' : ' '); Graph g(V); REP(i, V-1) { if (imos_w[i]) { int n = i; while (imos_w[n] == imos_w[n+1] and not curve[n+1]) n++; g.add_edge(i, n+1, n+1-i), g.add_edge(n+1, i, n+1-i); i = n; } } REP(i, V-1) { if (imos_h[i]) { int n = i; while (imos_h[n] == imos_h[n+1] and not curve[n+1]) n++; int p1 = (i%H)*W+i/H, p2 = (n%H)*W+n/H; g.add_edge(p1, p2+W, n+1-i), g.add_edge(p2+W, p1, n+1-i); i = n; } } /* REP(i, V) { cout << i << ':'; for (auto v : g.E[i]) cout << v.dst << ' '; cout << endl; } // */ ShortestPath sp(g, 0); sp.dijkstra(); if (sp.dist[V-1] == INF) { cout << "Odekakedekinai.." << endl; } else { cout << sp.dist[V-1] << endl; } //REP(i, g.V) cout << sp.dist[i] << (i == g.V-1 ? '\n' : ' '); return 0; }