#include using namespace std; typedef long long ll; typedef vector vi; typedef vector vl; typedef complex P; typedef pair pii; #define REP(i,n) for(ll i=0;idst)swap(src,dst); int sx,sy,tx,ty; sx = src%w; sy = src/w; tx = dst%w; ty = dst/w; if(sx==tx){ FOR(i,sy,ty){ g[sx+i*w] |= dir[1]; g[sx+(i+1)*w] |= dir[3]; } }else{ FOR(i,sx,tx){ g[sy*w+i] |= dir[0]; g[sy*w+i+1] |= dir[2]; } } } int main(){ // w,h<1e3 // |V| = wh < 1e6 // n < 1e3 // m < 1e3 // |E| = nm < 1e6 int n; cin>>w>>h>>n; while(n--){ int m; cin>>m; int bef; cin>>bef; REP(i,m){ int cur; cin>>cur; add_edge(bef,cur); bef = cur; } } queue Q; int s = 0; int t = w*h-1; Q.push(make_pair(0,0)); int res = -1; vector used(w*h,false); while(!Q.empty()){ pii P = Q.front(); Q.pop(); int pos = P.first; if(used[pos])continue; used[pos] = true; int wei = P.second; int x = pos%w; int y = pos/w; REP(i,4){ if(!(g[pos] & dir[i]))continue; int tx = x+dx[i]; int ty = y+dy[i]; if(tx<0 || tx>=w)continue; if(ty<0 || ty>=h)continue; int tpos = ty*w+tx; if(tpos<0 || tpos>=w*h)continue; if(used[tpos])continue; if(tpos == t){ cout<<(wei+1)<