#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; static const double EPS = 1e-10; typedef long long ll; #define rep(i,n) for(int (i)=0;(i)<(n);(i)++) #define rev(i,n) for(int i=(n)-1;(i)>=0;(i)--) #define all(a) (a).begin(),(a).end() #define pb(a) push_back(a) #define bitcount(b) __builtin_popcount(b) template vector& operator<<(vector& a, S b) { a.push_back(b); return a; } template void operator>>(vector& a, int b) {while(b--)if(!a.empty())a.pop_back();} bool isprime(int n){ if(n<2)return false; for(int i=2;i*i<=n;i++)if(n%i==0)return false; return true;} ll b_pow(ll x,ll n){return n ? b_pow(x*x,n/2)*(n%2?x:1) : 1ll;} string itos(int n){stringstream ss;ss << n;return ss.str();} template ostream& operator<<(ostream& os, const pair& p) { os << "(" << p.first << "," << p.second << ")"; return os; } template ostream& operator<<(ostream& os, const vector& arr) { os << "{"; for(int i = 0 ; i < arr.size() ; i++) os << (i==0?"":",") << arr[i]; os << "}"; return os; } int dx[] = {-1,0,1,0}; int dy[] = {0,1,0,-1}; int dir(int x,int y,int x2,int y2){ if( x == x2 ){ if( y < y2 ) return 1; else return 3; }else{ if( x < x2 ) return 2; else return 0; } } int color[1010][1010][4]; struct NODE{ int x,y,c; }; int dn[1010][1010]; unordered_set skip; int main(){ int W,H,N; cin >> W >> H >> N; if( W * H == 1 ){ cout << 0 << endl; return 0; } for(int i = 0 ; i < N ; i++){ int M; cin >> M; int px,py,pw; for(int j = 0 ; j <= M ; j++){ int w; scanf("%d",&w); pw = w; int x = w % W; int y = w / W; // cout << x << " " << y << endl; if(j){ if( !skip.count(w * 1000 + pw) ){ int dd = dir(px,py,x,y); int c = abs(x-px) + abs(y-py); int cx = px; int cy = py; while(c--){ color[cy][cx][dd] = true; cx += dx[dd]; cy += dy[dd]; color[cy][cx][(dd+2)%4] = true; } skip.insert(w * 1000 + pw); skip.insert(pw * 1000 + w); } } px = x; py = y; } } queue Q; Q.push({0,0,0}); dn[0][0] = 1; while( Q.size() ){ auto q = Q.front(); Q.pop(); if( q.y < 0 || q.x >= W || q.y >= H || q.y < 0 ) continue; if( q.y == H-1 && q.x == W - 1 ){ cout << q.c << endl; return 0; } for(int i = 0 ; i < 4 ; i++){ if( color[q.y][q.x][i] ){ NODE t = {q.x+dx[i],q.y+dy[i],q.c+1}; if( t.y < 0 || t.x >= W || t.y >= H || t.y < 0 || dn[t.y][t.x]++ ) continue; Q.push(t); } } } cout << "Odekakedekinai.." << endl; }