def solve(): W, H, hsWH, hsHW = read_data() build_edges(hsWH, hsHW) return wfs(W, H, hsWH, hsHW) def read_data(): W, H, N = map(int, input().split()) hsWH = [[0] * H for w in range(W)] # vertical lines hsHW = [[0] * W for h in range(H)] # horizontal lines for n in range(N): process_move(hsWH, hsHW, W, H) return W, H, hsWH, hsHW def process_move(hsWH, hsHW, W, H): Mnotused = input() Bs = list(map(int, input().split())) h0, w0 = divmod(Bs[0], W) for b in Bs: h1, w1 = divmod(b, W) if h0 == h1: # horizontal move if w0 > w1: hsHW[h0][w1] += 1 hsHW[h0][w0] -= 1 else: hsHW[h0][w0] += 1 hsHW[h0][w1] -= 1 w0 = w1 else: # vertical move if h0 > h1: hsWH[w0][h1] += 1 hsWH[w0][h0] -= 1 else: hsWH[w0][h0] += 1 hsWH[w0][h1] -= 1 h0 = h1 def build_edges(hsWH, hsHW): cum_sum(hsWH) cum_sum(hsHW) def cum_sum(mat): for row in mat: cum = 0 for i, val in enumerate(row): cum += val row[i] = cum def wfs(W, H, hsWH, hsHW): ''' (0, 0) から (W-1, H-1) までの最短距離を求める。 hsWH[w][h]: cell(w, h) と cell(w, h+1) に辺があるか否か hsHW[h][w]: cell(w, h) と cell(w+1, h) に辺があるか否か ''' start = 0 goal = H * W - 1 unvisited = [True] * (H * W) frontiers = [start] cost = 0 while frontiers: cost += 1 new_frontiers = [] for f in frontiers: if f == goal: return cost - 1 h, w = divmod(f, W) if hsWH[w][h] and unvisited[f + W]: unvisited[f + W] = False new_frontiers.append(f + W) if hsWH[w][h-1] and unvisited[f - W]: unvisited[f - W] = False new_frontiers.append(f - W) if hsHW[h][w] and unvisited[f + 1]: unvisited[f + 1] = False new_frontiers.append(f + 1) if hsHW[h][w-1] and unvisited[f - 1]: unvisited[f - 1] = False new_frontiers.append(f - 1) frontiers = new_frontiers return -1 ans = solve() if ans == -1: print("Odekakedekinai..") else: print(ans)