import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Scanner; import java.util.Set; public class Main { private int w; private int h; /* [0]そこから上へ移動できるか。[1]そこから右へ移動できるか。[2]すでに踏破チェック済みか */ private boolean[][] blocks; private static final String ODEKAKEDEKINAI = "Odekakedekinai.."; private void initField(int w, int h) { this.w = w; this.h = h; blocks = new boolean[w * h][3]; } private void execute() { if (w * h - 1 == 0) { System.out.println(0); System.exit(0); } /* block[0]を起点として、移動開始 */ Set next = new HashSet(); next.add(0); int stepCount = 0; while (true) { next = step(next); stepCount++; if (next.isEmpty()) { System.out.println(ODEKAKEDEKINAI); break; } if (next.contains(w * h - 1)) { System.out.println(stepCount); break; } } } private Set step(Set beforeBlocks) { Set nextBlocks = new HashSet(); for (int number : beforeBlocks) { /* 現在numberに踏破済みのフラグ(blocks[number][2]=true)を立てる */ blocks[number][2] = true; /* 上移動チェック */ if (blocks[number][0] && !blocks[number + w][2]) { nextBlocks.add(number + w); } /* 下移動チェック */ if (number > w && blocks[number - w][0] && !blocks[number - w][2]) { nextBlocks.add(number - w); } /* 左移動チェック */ if (number % w != 0 && blocks[number - 1][1] && !blocks[number - 1][2]) { nextBlocks.add(number - 1); } /* 右移動チェック */ if (blocks[number][1] && !blocks[number + 1][2]) { nextBlocks.add(number + 1); } } return nextBlocks; } private void footprint(int min, int max) { if (min / w == max / w) { /* 横の移動 = minとmaxをwで割ったときの値が等しい */ for (int i = min; i < max; i++) { /* 左側(数が小さいほうのblock)から右へと移動できるので、blocks[i][1]をtrue */ blocks[i][1] = true; } } else { /* 縦の移動 */ for (int i = min; i < max; i += w) { /* 下側(数が小さいほうのblock)から上へと移動できるので、blocks[i][0]をtrue */ blocks[i][0] = true; } } } public static void main(String[] args) { Scanner cin = new Scanner(System.in); Main snow = new Main(); int w = Integer.parseInt(cin.next()); int h = Integer.parseInt(cin.next()); snow.initField(w, h); Map checkedMap = new HashMap(); int limit = Integer.parseInt(cin.next()); for (int i = 0; i < limit; i++) { int index = Integer.parseInt(cin.next()); int[] currentArray = new int[2]; currentArray[1] = Integer.parseInt(cin.next()); for (int j = 0; j < index; j++) { currentArray[j % 2] = Integer.parseInt(cin.next()); int min = Math.min(currentArray[0], currentArray[1]); int max = Math.max(currentArray[0], currentArray[1]); if (!checkedMap.containsKey(min)) { checkedMap.put(min, max); } else { int value = checkedMap.get(min); if (value >= max) { continue; } checkedMap.put(min, max); } snow.footprint(min, max); } } cin.close(); snow.execute(); } }