import sys from collections import deque def main(): input = sys.stdin.read().split() ptr = 0 W = int(input[ptr]); ptr +=1 H = int(input[ptr]); ptr +=1 N = int(input[ptr]); ptr +=1 # Initialize direction flags: east, west, north, south east = [[False]*H for _ in range(W)] west = [[False]*H for _ in range(W)] north = [[False]*H for _ in range(W)] south = [[False]*H for _ in range(W)] for _ in range(N): M = int(input[ptr]); ptr +=1 B = list(map(int, input[ptr:ptr+M+1])) ptr += M+1 for i in range(M): current = B[i] next_node = B[i+1] w1 = current % W h1 = current // W w2 = next_node % W h2 = next_node // W if h1 == h2: # East or West movement if w1 < w2: # East for w in range(w1, w2): east[w][h1] = True west[w+1][h1] = True else: # West for w in range(w1, w2, -1): west[w][h1] = True east[w-1][h1] = True else: # North or South movement if h1 < h2: # North for h in range(h1, h2): north[h][w1] = True south[h+1][w1] = True else: # South for h in range(h1, h2, -1): south[h][w1] = True north[h-1][w1] = True # BFS setup size = W * H start = 0 goal = W * H - 1 if start == goal: print(0) return visited = [-1] * size q = deque([start]) visited[start] = 0 found = False while q and not found: current = q.popleft() current_dist = visited[current] current_w = current % W current_h = current // W # Check East if current_w < W - 1: next_w = current_w + 1 next_h = current_h next_node = next_w + next_h * W if east[current_w][current_h] and visited[next_node] == -1: if next_node == goal: print(current_dist + 1) found = True break visited[next_node] = current_dist + 1 q.append(next_node) # Check West if not found and current_w > 0: next_w = current_w - 1 next_h = current_h next_node = next_w + next_h * W if west[current_w][current_h] and visited[next_node] == -1: if next_node == goal: print(current_dist + 1) found = True break visited[next_node] = current_dist + 1 q.append(next_node) # Check North if not found and current_h < H - 1: next_h = current_h + 1 next_w = current_w next_node = next_w + next_h * W if north[current_h][current_w] and visited[next_node] == -1: if next_node == goal: print(current_dist + 1) found = True break visited[next_node] = current_dist + 1 q.append(next_node) # Check South if not found and current_h > 0: next_h = current_h - 1 next_w = current_w next_node = next_w + next_h * W if south[current_h][current_w] and visited[next_node] == -1: if next_node == goal: print(current_dist + 1) found = True break visited[next_node] = current_dist + 1 q.append(next_node) if not found: print("Odekakedekinai..") if __name__ == "__main__": main()