solutions: ["import sys\nn = int(input().strip())\nA = []\nfor a in range(1, n):\n\tB = []\n\tfor b in range(1, n):\n\t\tP = {(0, 0)}\n\t\tc = 0\n\t\tf = True\n\t\tV = set()\n\t\twhile f:\n\t\t\tc += 1\n\t\t\tQ = set()\n\t\t\tV = V | P\n\t\t\tfor p in P:\n\t\t\t\tif (p[0] == n - 1) & (p[1] == n - 1):\n\t\t\t\t\tf = False\n\t\t\t\t\tbreak\n\t\t\t\tif (0 <= p[0] + a < n) & (0 <= p[1] + b < n):\n\t\t\t\t\tQ.add((p[0] + a, p[1] + b))\n\t\t\t\tif (0 <= p[0] - a < n) & (0 <= p[1] - b < n):\n\t\t\t\t\tQ.add((p[0] - a, p[1] - b))\n\t\t\t\tif (0 <= p[0] - a < n) & (0 <= p[1] + b < n):\n\t\t\t\t\tQ.add((p[0] - a, p[1] + b))\n\t\t\t\tif (0 <= p[0] + a < n) & (0 <= p[1] - b < n):\n\t\t\t\t\tQ.add((p[0] + a, p[1] - b))\n\t\t\t\tif (0 <= p[0] + b < n) & (0 <= p[1] + a < n):\n\t\t\t\t\tQ.add((p[0] + b, p[1] + a))\n\t\t\t\tif (0 <= p[0] - b < n) & (0 <= p[1] - a < n):\n\t\t\t\t\tQ.add((p[0] - b, p[1] - a))\n\t\t\t\tif (0 <= p[0] - b < n) & (0 <= p[1] + a < n):\n\t\t\t\t\tQ.add((p[0] - b, p[1] + a))\n\t\t\t\tif (0 <= p[0] + b < n) & (0 <= p[1] - a < n):\n\t\t\t\t\tQ.add((p[0] + b, p[1] - a))\n\t\t\tP = set()\n\t\t\tP = P | Q\n\t\t\tP = P - V\n\t\t\tif len(P) == 0:\n\t\t\t\tbreak\n\t\tif not f:\n\t\t\tB.append(c - 1)\n\t\telse:\n\t\t\tB.append(-1)\n\tA.append(B)\nfor a in A:\n\tfor b in a:\n\t\tprint(b, end=' ')\n\tprint('')\n", "import sys\nmoves = []\n\ndef bfs(n, a, b):\n\tdist = {}\n\tstart = (0, 0)\n\tgoal = (n - 1, n - 1)\n\tqueue = [start]\n\tdist[start] = 0\n\twhile len(queue):\n\t\tcur = queue[0]\n\t\tqueue.pop(0)\n\t\tif cur == goal:\n\t\t\tmoves.append(dist[cur])\n\t\t\treturn\n\t\tfor move in [(a, b), (b, a), (-a, -b), (-b, -a), (a, -b), (-a, b), (-b, a), (b, -a)]:\n\t\t\tnext_pos = (cur[0] + move[0], cur[1] + move[1])\n\t\t\tif next_pos[0] > goal[0] or next_pos[1] > goal[1] or next_pos[0] < 0 or (next_pos[1] < 0) or (next_pos[0] == 0 and next_pos[1] == 0):\n\t\t\t\tcontinue\n\t\t\tif next_pos not in dist:\n\t\t\t\tdist[next_pos] = dist[cur] + 1\n\t\t\t\tqueue.append(next_pos)\n\tmoves.append(-1)\n\tqueue.clear()\n\tdist.clear()\n\treturn\nn = int(input().strip())\nfor j in range(1, n):\n\tfor k in range(1, n):\n\t\tbfs(n, j, k)\n\tprint(*moves)\n\tmoves.clear()\n", "import sys\nn = int(input().strip())\nN5 = '4 4 2 8\\n4 2 4 4\\n2 4 -1 -1\\n8 4 -1 1'\nN6 = '5 4 3 2 5\\n4 -1 2 -1 -1\\n3 2 -1 -1 -1\\n2 -1 -1 -1 -1\\n5 -1 -1 -1 1 '\nN7 = '6 4 4 8 2 12\\n4 3 4 2 16 3\\n4 4 2 4 4 4\\n8 2 4 -1 -1 -1\\n2 16 4 -1 -1 -1\\n12 3 4 -1 -1 1 '\nN8 = '7 6 5 6 5 2 7\\n6 -1 6 -1 2 -1 -1\\n5 6 -1 2 -1 -1 -1\\n6 -1 2 -1 -1 -1 -1\\n5 2 -1 -1 -1 -1 -1\\n2 -1 -1 -1 -1 -1 -1\\n7 -1 -1 -1 -1 -1 1 '\nN9 = '8 6 4 4 6 12 2 16\\n6 4 6 4 8 2 8 8\\n4 6 -1 4 2 -1 -1 -1\\n4 4 4 2 4 4 4 4\\n6 8 2 4 -1 -1 -1 -1\\n12 2 -1 4 -1 -1 -1 -1\\n2 8 -1 4 -1 -1 -1 -1\\n16 8 -1 4 -1 -1 -1 1 '\nN10 = '9 6 5 8 5 6 7 2 9\\n6 -1 6 -1 10 -1 2 -1 -1\\n5 6 3 6 7 2 13 -1 3\\n8 -1 6 -1 2 -1 -1 -1 -1\\n5 10 7 2 -1 -1 -1 -1 -1\\n6 -1 2 -1 -1 -1 -1 -1 -1\\n7 2 13 -1 -1 -1 -1 -1 -1\\n2 -1 -1 -1 -1 -1 -1 -1 -1\\n9 -1 3 -1 -1 -1 -1 -1 1 '\nN11 = '10 8 6 4 4 8 6 16 2 20\\n8 5 4 4 4 3 8 2 28 5\\n6 4 -1 8 4 -1 2 16 -1 -1\\n4 4 8 -1 4 2 -1 -1 -1 -1\\n4 4 4 4 2 4 4 4 4 4\\n8 3 -1 2 4 -1 -1 -1 -1 -1\\n6 8 2 -1 4 -1 -1 -1 -1 -1\\n16 2 16 -1 4 -1 -1 -1 -1 -1\\n2 28 -1 -1 4 -1 -1 -1 -1 -1\\n20 5 -1 -1 4 -1 -1 -1 -1 1 '\nN12 = '11 8 7 6 7 10 7 6 9 2 11\\n8 -1 6 -1 6 -1 14 -1 2 -1 -1\\n7 6 -1 8 7 -1 7 2 -1 -1 -1\\n6 -1 8 -1 6 -1 2 -1 -1 -1 -1\\n7 6 7 6 -1 2 -1 -1 -1 -1 -1\\n10 -1 -1 -1 2 -1 -1 -1 -1 -1 -1\\n7 14 7 2 -1 -1 -1 -1 -1 -1 -1\\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\\n9 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n11 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '\nN13 = '12 8 6 8 4 4 8 12 6 20 2 24\\n8 6 6 4 10 4 12 8 12 2 12 12\\n6 6 4 8 6 4 8 8 2 8 8 8\\n8 4 8 3 8 4 12 2 36 16 -1 3\\n4 10 6 8 -1 4 2 -1 -1 -1 -1 -1\\n4 4 4 4 4 2 4 4 4 4 4 4\\n8 12 8 12 2 4 -1 -1 -1 -1 -1 -1\\n12 8 8 2 -1 4 -1 -1 -1 -1 -1 -1\\n6 12 2 36 -1 4 -1 -1 -1 -1 -1 -1\\n20 2 8 16 -1 4 -1 -1 -1 -1 -1 -1\\n2 12 8 -1 -1 4 -1 -1 -1 -1 -1 -1\\n24 12 8 3 -1 4 -1 -1 -1 -1 -1 1 '\nN14 = '13 10 7 6 5 12 7 10 9 6 11 2 13\\n10 -1 6 -1 6 -1 6 -1 18 -1 2 -1 -1\\n7 6 -1 6 7 -1 9 14 -1 2 -1 -1 -1\\n6 -1 6 -1 10 -1 10 -1 2 -1 -1 -1 -1\\n5 6 7 10 -1 6 11 2 -1 -1 -1 -1 -1\\n12 -1 -1 -1 6 -1 2 -1 -1 -1 -1 -1 -1\\n7 6 9 10 11 2 -1 -1 -1 -1 -1 -1 -1\\n10 -1 14 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\\n9 18 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n11 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n13 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1\\n'\nN15 = '14 10 8 8 6 4 4 8 10 16 6 24 2 28\\n10 7 8 6 4 5 4 6 8 5 12 2 40 7\\n8 8 -1 4 6 -1 4 16 -1 8 2 -1 -1 -1\\n8 6 4 -1 10 6 4 -1 20 2 16 -1 -1 -1\\n6 4 6 10 -1 8 4 12 2 -1 -1 -1 -1 -1\\n4 5 -1 6 8 -1 4 2 -1 -1 -1 -1 -1 -1\\n4 4 4 4 4 4 2 4 4 4 4 4 4 4\\n8 6 16 -1 12 2 4 -1 -1 -1 -1 -1 -1 -1\\n10 8 -1 20 2 -1 4 -1 -1 -1 -1 -1 -1 -1\\n16 5 8 2 -1 -1 4 -1 -1 -1 -1 -1 -1 -1\\n6 12 2 16 -1 -1 4 -1 -1 -1 -1 -1 -1 -1\\n24 2 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1\\n2 40 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1\\n28 7 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 1 '\nN16 = '15 10 9 6 7 10 9 14 9 10 11 6 13 2 15\\n10 -1 6 -1 10 -1 10 -1 6 -1 22 -1 2 -1 -1\\n9 6 5 6 5 4 7 10 3 14 13 2 23 -1 5\\n6 -1 6 -1 10 -1 14 -1 10 -1 2 -1 -1 -1 -1\\n7 10 5 10 3 10 9 14 13 2 23 -1 -1 -1 3\\n10 -1 4 -1 10 -1 6 -1 2 -1 -1 -1 -1 -1 -1\\n9 10 7 14 9 6 -1 2 -1 -1 -1 -1 -1 -1 -1\\n14 -1 10 -1 14 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\\n9 6 3 10 13 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n10 -1 14 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n11 22 13 2 23 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n13 2 23 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n15 -1 5 -1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '\nN17 = '16 12 8 8 6 8 4 4 8 12 10 20 6 28 2 32\\n12 8 8 6 8 4 14 4 16 6 16 12 16 2 16 16\\n8 8 -1 8 4 -1 6 4 -1 20 8 -1 2 28 -1 -1\\n8 6 8 4 8 6 8 4 8 8 8 2 8 8 8 8\\n6 8 4 8 -1 12 6 4 10 -1 2 68 16 -1 -1 -1\\n8 4 -1 6 12 -1 8 4 -1 2 -1 -1 -1 -1 -1 -1\\n4 14 6 8 6 8 -1 4 2 -1 -1 -1 -1 -1 -1 -1\\n4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4\\n8 16 -1 8 10 -1 2 4 -1 -1 -1 -1 -1 -1 -1 -1\\n12 6 20 8 -1 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1\\n10 16 8 8 2 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1\\n20 12 -1 2 68 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1\\n6 16 2 8 16 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1\\n28 2 28 8 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1\\n2 16 -1 8 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1\\n32 16 -1 8 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 1 '\nN18 = '17 12 9 8 7 6 7 16 9 14 11 10 13 6 15 2 17\\n12 -1 8 -1 6 -1 10 -1 14 -1 6 -1 26 -1 2 -1 -1\\n9 8 -1 8 5 -1 9 6 -1 18 13 -1 13 2 -1 -1 -1\\n8 -1 8 -1 6 -1 6 -1 18 -1 14 -1 2 -1 -1 -1 -1\\n7 6 5 6 -1 12 11 10 9 -1 13 2 -1 -1 -1 -1 -1\\n6 -1 -1 -1 12 -1 10 -1 -1 -1 2 -1 -1 -1 -1 -1 -1\\n7 10 9 6 11 10 -1 6 15 2 -1 -1 -1 -1 -1 -1 -1\\n16 -1 6 -1 10 -1 6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\\n9 14 -1 18 9 -1 15 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n14 -1 18 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n11 6 13 14 13 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n10 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n13 26 13 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n15 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n17 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '\nN19 = '18 12 10 8 6 12 8 4 4 8 12 16 10 24 6 32 2 36\\n12 9 8 6 8 5 4 8 4 5 8 6 12 7 16 2 52 9\\n10 8 6 8 6 4 6 12 4 12 12 8 12 12 2 12 12 12\\n8 6 8 -1 4 6 14 -1 4 10 20 -1 8 2 -1 -1 -1 -1\\n6 8 6 4 -1 12 8 16 4 -1 10 20 2 16 -1 -1 -1 -1\\n12 5 4 6 12 3 12 6 4 7 24 2 56 13 16 -1 -1 3\\n8 4 6 14 8 12 -1 8 4 20 2 -1 -1 -1 -1 -1 -1 -1\\n4 8 12 -1 16 6 8 -1 4 2 -1 -1 -1 -1 -1 -1 -1 -1\\n4 4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4 4\\n8 5 12 10 -1 7 20 2 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n12 8 12 20 10 24 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n16 6 8 -1 20 2 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n10 12 12 8 2 56 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n24 7 12 2 16 13 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n6 16 2 -1 -1 16 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n32 2 12 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n2 52 12 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n36 9 12 -1 -1 3 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 1 '\nN20 = '19 14 11 10 7 6 7 14 11 18 11 14 13 10 15 6 17 2 19\\n14 -1 10 -1 10 -1 6 -1 10 -1 18 -1 6 -1 30 -1 2 -1 -1\\n11 10 -1 10 7 -1 7 16 -1 6 11 -1 15 22 -1 2 -1 -1 -1\\n10 -1 10 -1 6 -1 6 -1 14 -1 22 -1 14 -1 2 -1 -1 -1 -1\\n7 10 7 6 -1 10 11 6 13 -1 13 26 17 2 -1 -1 -1 -1 -1\\n6 -1 -1 -1 10 -1 14 -1 -1 -1 10 -1 2 -1 -1 -1 -1 -1 -1\\n7 6 7 6 11 14 -1 10 13 14 17 2 -1 -1 -1 -1 -1 -1 -1\\n14 -1 16 -1 6 -1 10 -1 6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\\n11 10 -1 14 13 -1 13 6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n18 -1 6 -1 -1 -1 14 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n11 18 11 22 13 10 17 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n14 -1 -1 -1 26 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n13 6 15 14 17 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n10 -1 22 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n15 30 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n17 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n19 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '\nN21 = '20 14 10 8 8 12 6 8 4 4 8 12 14 20 10 28 6 36 2 40\\n14 10 8 8 8 6 12 4 18 4 20 8 20 6 20 16 20 2 20 20\\n10 8 -1 8 8 -1 4 12 -1 4 6 -1 8 28 -1 12 2 -1 -1 -1\\n8 8 8 5 8 4 8 4 12 4 16 3 20 8 24 2 64 28 -1 5\\n8 8 8 8 4 8 8 8 8 4 8 8 8 8 2 8 8 8 8 8\\n12 6 -1 4 8 -1 14 8 -1 4 12 -1 32 2 -1 16 -1 -1 -1 -1\\n6 12 4 8 8 14 -1 12 6 4 12 12 2 -1 -1 -1 -1 -1 -1 -1\\n8 4 12 4 8 8 12 -1 8 4 20 2 -1 -1 -1 -1 -1 -1 -1 -1\\n4 18 -1 12 8 -1 6 8 -1 4 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n4 4 4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4 4 4\\n8 20 6 16 8 12 12 20 2 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n12 8 -1 3 8 -1 12 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n14 20 8 20 8 32 2 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n20 6 28 8 8 2 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n10 20 -1 24 2 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n28 16 12 2 8 16 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n6 20 2 64 8 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n36 2 -1 28 8 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n2 20 -1 -1 8 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n40 20 -1 5 8 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '\nN22 = '21 14 11 10 9 6 9 10 9 20 11 18 13 14 15 10 17 6 19 2 21\\n14 -1 10 -1 6 -1 14 -1 10 -1 10 -1 22 -1 6 -1 34 -1 2 -1 -1\\n11 10 7 6 9 6 7 6 5 10 11 6 13 18 5 22 19 2 33 -1 7\\n10 -1 6 -1 10 -1 14 -1 6 -1 10 -1 26 -1 18 -1 2 -1 -1 -1 -1\\n9 6 9 10 -1 6 9 16 9 -1 15 10 15 14 -1 2 -1 -1 -1 -1 -1\\n6 -1 6 -1 6 -1 14 -1 6 -1 18 -1 10 -1 2 -1 -1 -1 -1 -1 -1\\n9 14 7 14 9 14 3 14 13 18 15 22 19 2 33 -1 -1 -1 -1 -1 3\\n10 -1 6 -1 16 -1 14 -1 10 -1 22 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\\n9 10 5 6 9 6 13 10 -1 6 19 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n20 -1 10 -1 -1 -1 18 -1 6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n11 10 11 10 15 18 15 22 19 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n18 -1 6 -1 10 -1 22 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n13 22 13 26 15 10 19 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n14 -1 18 -1 14 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n15 6 5 18 -1 2 33 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n10 -1 22 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n17 34 19 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n19 2 33 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n21 -1 7 -1 -1 -1 3 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '\nN23 = '22 16 12 10 8 8 6 12 8 4 4 8 12 16 14 24 10 32 6 40 2 44\\n16 11 10 8 10 7 8 6 4 7 4 10 8 7 12 6 16 9 20 2 64 11\\n12 10 -1 8 8 -1 8 4 -1 16 4 -1 6 8 -1 32 12 -1 2 40 -1 -1\\n10 8 8 -1 10 6 4 -1 18 6 4 -1 24 14 8 -1 32 2 28 -1 -1 -1\\n8 10 8 10 -1 4 6 8 6 -1 4 24 14 20 -1 8 2 -1 -1 -1 -1 -1\\n8 7 -1 6 4 -1 12 8 -1 7 4 -1 20 7 -1 2 16 -1 -1 -1 -1 -1\\n6 8 8 4 6 12 -1 16 8 12 4 20 10 -1 2 36 -1 16 -1 -1 -1 -1\\n12 6 4 -1 8 8 16 -1 12 6 4 -1 12 2 -1 -1 -1 -1 -1 -1 -1 -1\\n8 4 -1 18 6 -1 8 12 -1 8 4 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n4 7 16 6 -1 7 12 6 8 -1 4 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n4 4 4 4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4 4 4 4\\n8 10 -1 -1 24 -1 20 -1 -1 2 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n12 8 6 24 14 20 10 12 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n16 7 8 14 20 7 -1 2 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n14 12 -1 8 -1 -1 2 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n24 6 32 -1 8 2 36 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n10 16 12 32 2 16 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n32 9 -1 2 -1 -1 16 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n6 20 2 28 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n40 2 40 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n2 64 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n44 11 -1 -1 -1 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 '\nN24 = '23 16 13 10 9 10 9 6 9 18 13 22 13 18 15 14 17 10 19 6 21 2 23\\n16 -1 10 -1 10 -1 6 -1 14 -1 14 -1 10 -1 26 -1 6 -1 38 -1 2 -1 -1\\n13 10 -1 10 7 -1 9 10 -1 20 11 -1 13 6 -1 26 19 -1 19 2 -1 -1 -1\\n10 -1 10 -1 10 -1 10 -1 6 -1 6 -1 18 -1 30 -1 18 -1 2 -1 -1 -1 -1\\n9 10 7 10 -1 6 7 6 13 -1 11 14 17 26 -1 14 21 2 -1 -1 -1 -1 -1\\n10 -1 -1 -1 6 -1 10 -1 -1 -1 22 -1 18 -1 -1 -1 2 -1 -1 -1 -1 -1 -1\\n9 6 9 10 7 10 -1 16 15 6 11 10 15 -1 19 2 55 -1 -1 -1 -1 -1 -1\\n6 -1 10 -1 6 -1 16 -1 14 -1 14 -1 22 -1 2 -1 -1 -1 -1 -1 -1 -1 -1\\n9 14 -1 6 13 -1 15 14 -1 10 17 -1 17 2 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n18 -1 20 -1 -1 -1 6 -1 10 -1 6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n13 14 11 6 11 22 11 14 17 6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n22 -1 -1 -1 14 -1 10 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n13 10 13 18 17 18 15 22 17 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n18 -1 6 -1 26 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n15 26 -1 30 -1 -1 19 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n14 -1 26 -1 14 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n17 6 19 18 21 2 55 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n10 -1 -1 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n19 38 19 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n6 -1 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n21 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1\\n23 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1'\nN25 = '24 16 12 12 8 8 6 16 10 8 4 4 8 12 16 20 14 28 10 36 6 44 2 48 \\n16 12 12 8 8 6 8 8 16 4 22 4 24 8 24 12 24 6 24 20 24 2 24 24 \\n12 12 8 8 6 6 6 16 4 16 10 4 14 16 6 16 16 12 16 16 2 16 16 16 \\n12 8 8 6 12 6 12 4 12 10 12 4 12 12 12 8 12 12 12 2 12 12 12 12 \\n8 8 6 12 -1 8 4 16 6 -1 12 4 10 28 -1 20 8 24 2 -1 -1 -1 -1 -1 \\n8 6 6 6 8 4 8 8 6 6 8 4 8 8 8 8 8 2 8 8 8 8 8 8 \\n6 8 6 12 4 8 -1 16 10 20 10 4 12 -1 10 20 2 -1 16 -1 -1 -1 -1 -1 \\n16 8 16 4 16 8 16 3 16 8 20 4 24 12 36 2 76 36 -1 16 -1 -1 -1 3 \\n10 16 4 12 6 6 10 16 -1 12 6 4 14 32 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n8 4 16 10 -1 6 20 8 12 -1 8 4 24 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n4 22 10 12 12 8 10 20 6 8 -1 4 2 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n4 4 4 4 4 4 4 4 4 4 4 2 4 4 4 4 4 4 4 4 4 4 4 4 \\n8 24 14 12 10 8 12 24 14 24 2 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n12 8 16 12 28 8 -1 12 32 2 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n16 24 6 12 -1 8 10 36 2 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n20 12 16 8 20 8 20 2 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n14 24 16 12 8 8 2 76 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n28 6 12 12 24 2 -1 36 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n10 24 16 12 2 8 16 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n36 20 16 2 -1 8 -1 16 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n6 24 2 12 -1 8 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n44 2 16 12 -1 8 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n2 24 16 12 -1 8 -1 -1 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 \\n48 24 16 12 -1 8 -1 3 -1 -1 -1 4 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 1 \\n'\nif n == 5:\n\tprint(N5)\nif n == 6:\n\tprint(N6)\nif n == 7:\n\tprint(N7)\nif n == 8:\n\tprint(N8)\nif n == 9:\n\tprint(N9)\nif n == 10:\n\tprint(N10)\nif n == 11:\n\tprint(N11)\nif n == 12:\n\tprint(N12)\nif n == 13:\n\tprint(N13)\nif n == 14:\n\tprint(N14)\nif n == 15:\n\tprint(N15)\nif n == 16:\n\tprint(N16)\nif n == 17:\n\tprint(N17)\nif n == 18:\n\tprint(N18)\nif n == 19:\n\tprint(N19)\nif n == 20:\n\tprint(N20)\nif n == 21:\n\tprint(N21)\nif n == 22:\n\tprint(N22)\nif n == 23:\n\tprint(N23)\nif n == 24:\n\tprint(N24)\nif n == 25:\n\tprint(N25)\n", "def pos_moves(x, y, a, b, n):\n\tresult = []\n\tfor (xd, yd) in ((a, b), (a, -b), (-a, b), (-a, -b), (b, a), (b, -a), (-b, a), (-b, -a)):\n\t\tif not 0 <= x + xd < n or not 0 <= y + yd < n:\n\t\t\tcontinue\n\t\tresult.append((x + xd, y + yd))\n\treturn result\n\ndef moves(a, b, n):\n\tfound = set()\n\td = {(0, 0): 0}\n\ttodo = [(0, 0)]\n\tgoal = (n - 1, n - 1)\n\twhile todo:\n\t\tp = todo.pop(0)\n\t\td_p = d[p]\n\t\tfor m in pos_moves(p[0], p[1], a, b, n):\n\t\t\tif m in found:\n\t\t\t\tcontinue\n\t\t\telif m == goal:\n\t\t\t\treturn d_p + 1\n\t\t\telse:\n\t\t\t\tfound.add(m)\n\t\t\t\td[m] = d_p + 1\n\t\t\t\ttodo.append(m)\n\treturn -1\nn = int(input().strip())\nfor i in range(1, n):\n\tprint(*[moves(i, j, n) for j in range(1, n)])\n", "import sys\nn = int(input().strip())\nlst = []\nfor i in range(1, n):\n\tlst.append([])\n\tfor j in range(1, i):\n\t\tlst[i - 1].append(lst[j - 1][i - 1])\n\tif (n - 1) % i == 0:\n\t\tlst[i - 1].append((n - 1) // i)\n\telse:\n\t\tlst[i - 1].append(-1)\n\tfor j in range(i + 1, n):\n\t\tarr = [(i, j), (i, -j), (-i, j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)]\n\t\tmaxdist = n * n\n\t\tv = [[0 for _ in range(n)] for _ in range(n)]\n\t\tq = [(n - 1, n - 1, 0)]\n\t\tv[n - 1][n - 1] = 1\n\t\tpossib = 1\n\t\tsteps = 0\n\t\twhile q:\n\t\t\tcurr = q.pop(0)\n\t\t\tsteps = curr[2]\n\t\t\tif curr[0] == 0 and curr[1] == 0:\n\t\t\t\tlst[i - 1].append(steps)\n\t\t\t\tbreak\n\t\t\tfor el in arr:\n\t\t\t\tk = el[0] + curr[0]\n\t\t\t\tl = el[1] + curr[1]\n\t\t\t\tif k >= 0 and k <= n - 1 and (l >= 0) and (l <= n - 1) and (v[k][l] != 1):\n\t\t\t\t\tv[k][l] = 1\n\t\t\t\t\tq.append((k, l, steps + 1))\n\t\tif v[0][0] == 0:\n\t\t\tlst[i - 1].append(-1)\nfor el in lst:\n\tprint(*el)\n", "class Grid:\n\n\tdef __init__(self, n, a, b):\n\t\tself.n = n\n\t\tself.a = a\n\t\tself.b = b\n\t\tself.grid = [[-1 for _ in range(n)] for _ in range(n)]\n\t\tself.iteration = 0\n\t\tself.possible_positions = [(0, 0)]\n\t\tself.grid[0][0] = 0\n\t\tself.result = None\n\n\tdef iterate(self):\n\t\tself.iteration += 1\n\t\tnext_positions = []\n\t\tfor (x, y) in self.possible_positions:\n\t\t\tpossible_next_positions = self.jump(x, y)\n\t\t\tfor (i, j) in possible_next_positions:\n\t\t\t\tif i == self.n - 1 and j == self.n - 1:\n\t\t\t\t\tself.result = self.iteration\n\t\t\t\t\treturn\n\t\t\t\tif self.grid[i][j] == -1:\n\t\t\t\t\tself.grid[i][j] = self.iteration\n\t\t\t\t\tnext_positions.append((i, j))\n\t\tif not next_positions:\n\t\t\tself.result = -1\n\t\t\treturn\n\t\tself.possible_positions = next_positions\n\n\tdef solve(self):\n\t\twhile self.result is None:\n\t\t\tself.iterate()\n\t\treturn self.result\n\n\tdef jump(self, x, y):\n\t\t(a, b) = (self.a, self.b)\n\t\tpotential = [(x - a, y - b), (x - a, y + b), (x + a, y - b), (x + a, y + b), (x - b, y - a), (x - b, y + a), (x + b, y - a), (x + b, y + a)]\n\t\treturn [(i, j) for (i, j) in potential if 0 <= i < self.n and 0 <= j < self.n]\nn = int(input())\nsolution_matrix = [[-1 for _ in range(n - 1)] for _ in range(n - 1)]\nfor a in range(1, n):\n\tfor b in range(a, n):\n\t\tgrid = Grid(n, a, b)\n\t\tsolution = grid.solve()\n\t\tsolution_matrix[a - 1][b - 1] = solution_matrix[b - 1][a - 1] = solution\nprint('\\n'.join((' '.join((str(i) for i in line)) for line in solution_matrix)))\n", "import sys\nn = int(input().strip())\nresults = [[None for _ in range(n - 1)] for _ in range(n - 1)]\nmultiplier = [(1, 1), (1, -1), (-1, 1), (-1, -1)]\nfor i in range(1, n):\n\tfor j in range(i, n):\n\t\tvisited = dict()\n\t\tvisited[0, 0] = 0\n\t\tmove_from = [(0, 0)]\n\t\twhile move_from != []:\n\t\t\told_move = move_from.pop(0)\n\t\t\tpos_moves = [(old_move[0] + i * x, old_move[1] + j * y) for (x, y) in multiplier]\n\t\t\tpos_moves.extend([(old_move[0] + j * x, old_move[1] + i * y) for (x, y) in multiplier])\n\t\t\tfor new_move in pos_moves:\n\t\t\t\tif new_move[0] >= 0 and new_move[1] >= 0 and (new_move[0] < n) and (new_move[1] < n):\n\t\t\t\t\tif visited.get(new_move, None) == None:\n\t\t\t\t\t\tvisited[new_move] = visited.get(old_move) + 1\n\t\t\t\t\t\tmove_from.append(new_move)\n\t\t\t\t\telif visited.get(new_move) > visited.get(old_move) + 1:\n\t\t\t\t\t\tvisited[new_move] = visited.get(old_move) + 1\n\t\t\tif visited.get((n - 1, n - 1), None) != None:\n\t\t\t\tresults[i - 1][j - 1] = visited.get((n - 1, n - 1), -1)\n\t\t\t\tif i != j:\n\t\t\t\t\tresults[j - 1][i - 1] = visited.get((n - 1, n - 1), -1)\n\t\tif visited.get((n - 1, n - 1), None) == None:\n\t\t\tresults[i - 1][j - 1] = -1\n\t\t\tif i != j:\n\t\t\t\tresults[j - 1][i - 1] = -1\nfor row in results:\n\tout = str()\n\tfor col in row:\n\t\tout += str(col) + ' '\n\tprint(out.rstrip())\n", "def bfs(i, j):\n\tdist = {}\n\tstart = (0, 0)\n\tgoal = (n - 1, n - 1)\n\tqueue = [start]\n\tdist[start] = 0\n\twhile len(queue):\n\t\tcur = queue[0]\n\t\tqueue.pop(0)\n\t\tif cur == goal:\n\t\t\treturn dist[cur]\n\t\tfor move in [(i, j), (j, i), (-i, -j), (-j, -i), (i, -j), (-i, j), (-j, i), (j, -i)]:\n\t\t\tnext_pos = (cur[0] + move[0], cur[1] + move[1])\n\t\t\tif next_pos[0] > goal[0] or next_pos[1] > goal[1] or next_pos[0] < 0 or (next_pos[1] < 0):\n\t\t\t\tcontinue\n\t\t\tif next_pos not in dist:\n\t\t\t\tdist[next_pos] = dist[cur] + 1\n\t\t\t\tqueue.append(next_pos)\n\treturn -1\nn = int(input().strip())\nans = []\nfor i in range(1, n):\n\tans.append([])\n\tfor j in range(i, n):\n\t\tans[-1].extend([bfs(i, j)])\nprint(' '.join((str(p) for p in ans[0])))\nfor i in range(1, n - 1):\n\tans[i] = [ans[j][i] for j in range(i)] + ans[i]\n\tprint(' '.join((str(p) for p in ans[i])))\n", "import sys\n\ndef set_element(board, position_x, position_y, move_x, move_y, tmp_y, tmp_x):\n\tif 0 <= tmp_y < len(board) and 0 <= tmp_x < len(board):\n\t\tif board[tmp_y][tmp_x] == -1 or board[tmp_y][tmp_x] > board[position_y][position_x] + 1:\n\t\t\tboard[tmp_y][tmp_x] = board[position_y][position_x] + 1\n\t\t\treturn True\n\treturn False\n\ndef reccur_board(board, position_x, position_y, move_x, move_y):\n\tpositions = [(position_x, position_y)]\n\twhile len(positions) != 0:\n\t\t(tmp_x, tmp_y) = positions.pop(0)\n\t\tif set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y + move_y, tmp_x + move_x):\n\t\t\tpositions.append((tmp_x + move_x, tmp_y + move_y))\n\t\tif set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y - move_y, tmp_x - move_x):\n\t\t\tpositions.append((tmp_x - move_x, tmp_y - move_y))\n\t\tif set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y - move_y, tmp_x + move_x):\n\t\t\tpositions.append((tmp_x + move_x, tmp_y - move_y))\n\t\tif set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y + move_y, tmp_x - move_x):\n\t\t\tpositions.append((tmp_x - move_x, tmp_y + move_y))\n\t\tif move_x != move_y:\n\t\t\tif set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y + move_x, tmp_x + move_y):\n\t\t\t\tpositions.append((tmp_x + move_y, tmp_y + move_x))\n\t\t\tif set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y - move_x, tmp_x - move_y):\n\t\t\t\tpositions.append((tmp_x - move_y, tmp_y - move_x))\n\t\t\tif set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y - move_x, tmp_x + move_y):\n\t\t\t\tpositions.append((tmp_x + move_y, tmp_y - move_x))\n\t\t\tif set_element(board, tmp_x, tmp_y, move_x, move_y, tmp_y + move_x, tmp_x - move_y):\n\t\t\t\tpositions.append((tmp_x - move_y, tmp_y + move_x))\nn = int(input().strip())\nresult = [[-2 for x in range(1, n)] for y in range(1, n)]\nfor move_y in range(1, n):\n\tfor move_x in range(1, n):\n\t\tboard = [[-1 for x in range(0, n)] for y in range(0, n)]\n\t\tboard[0][0] = 0\n\t\tif result[move_y - 1][move_x - 1] == -2 and result[move_x - 1][move_y - 1] == -2:\n\t\t\treccur_board(board, 0, 0, move_x, move_y)\n\t\t\tresult[move_y - 1][move_x - 1] = str(board[n - 1][n - 1])\n\t\t\tresult[move_x - 1][move_y - 1] = str(board[n - 1][n - 1])\nfor line in result:\n\tprint(' '.join([str(e) for e in line]))\n", "import sys\nn = int(input().strip())\n\ndef find_min_num_knight_moves(n, a, b):\n\toffsets = [(+a, +b), (+a, -b), (-a, +b), (-a, -b), (+b, +a), (-b, +a), (+b, -a), (-b, -a)]\n\tstore = [[0 for _ in range(n)] for _ in range(n)]\n\tqueue = [(0, 0)]\n\twhile len(queue) != 0:\n\t\t(i, j) = queue.pop(0)\n\t\tfor o in offsets:\n\t\t\ti_ = i + o[0]\n\t\t\tj_ = j + o[1]\n\t\t\tif i_ in range(n) and j_ in range(n):\n\t\t\t\tnew_value = store[i][j] + 1\n\t\t\t\told_value = store[i_][j_]\n\t\t\t\tif old_value == 0 or (old_value != 0 and new_value < old_value):\n\t\t\t\t\tstore[i_][j_] = new_value\n\t\t\t\t\tqueue.append((i_, j_))\n\tresult = store[-1][-1]\n\tif store[-1][-1] == 0:\n\t\tresult = -1\n\treturn result\nfor a in range(1, n):\n\tmsg = ''\n\tfor b in range(1, n):\n\t\tresult = find_min_num_knight_moves(n, a, b)\n\t\tmsg = msg + str(result) + ' '\n\tprint(msg)\n", "import sys\nfrom collections import deque\n\nclass Board(object):\n\n\tdef __init__(self, i, j, n):\n\t\tassert n > 0 and 0 < i < n and (0 < j < n)\n\t\tself.N = n\n\t\tself.I = i\n\t\tself.J = j\n\n\tdef next_pos(self, x, y):\n\t\tassert 0 <= x < self.N and 0 <= y < self.N\n\t\ti = self.I\n\t\tj = self.J\n\t\tout = set()\n\t\tfor _i in (i, -i):\n\t\t\tfor _j in (j, -j):\n\t\t\t\tnx = x + _i\n\t\t\t\tny = y + _j\n\t\t\t\tif 0 <= nx < self.N and 0 <= ny < self.N:\n\t\t\t\t\tout.add((nx, ny))\n\t\t\t\tnx = x + _j\n\t\t\t\tny = y + _i\n\t\t\t\tif 0 <= nx < self.N and 0 <= ny < self.N:\n\t\t\t\t\tout.add((nx, ny))\n\t\treturn list(out)\n\nclass BFS(object):\n\n\tdef __init__(self, board):\n\t\tself.N = board.N\n\t\tself.board = board\n\t\tself.x_start = 0\n\t\tself.y_start = 0\n\t\tself.x_end = self.N - 1\n\t\tself.y_end = self.N - 1\n\n\tdef search(self):\n\t\tx = self.x_start\n\t\ty = self.y_start\n\t\tvisited = set()\n\t\tqueue = deque([(x, y, 0)])\n\t\twhile len(queue) > 0:\n\t\t\t(x, y, level) = queue.popleft()\n\t\t\tif (x, y) in visited:\n\t\t\t\tcontinue\n\t\t\tif (x, y) == (self.x_end, self.y_end):\n\t\t\t\treturn level\n\t\t\tfor (next_x, next_y) in self.board.next_pos(x, y):\n\t\t\t\tqueue.append((next_x, next_y, level + 1))\n\t\t\tvisited.add((x, y))\n\t\treturn -1\nn = int(input().strip())\nbuffer = {}\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tif j >= i:\n\t\t\tstep = BFS(Board(i, j, n)).search()\n\t\t\tprint(step, end=' ')\n\t\t\tif j > i:\n\t\t\t\tbuffer[j, i] = step\n\t\telse:\n\t\t\tprint(buffer[i, j], end=' ')\n\tprint('')\n", "import collections as col\nimport sys\n\ndef valids(n, a, b, v):\n\tws = []\n\t(x, y) = v\n\tif 0 <= x + a < n and 0 <= y + b < n:\n\t\tws.append((x + a, y + b))\n\tif 0 <= x + a < n and 0 <= y - b < n:\n\t\tws.append((x + a, y - b))\n\tif 0 <= x - a < n and 0 <= y + b < n:\n\t\tws.append((x - a, y + b))\n\tif 0 <= x - a < n and 0 <= y - b < n:\n\t\tws.append((x - a, y - b))\n\tif 0 <= x + b < n and 0 <= y + a < n:\n\t\tws.append((x + b, y + a))\n\tif 0 <= x + b < n and 0 <= y - a < n:\n\t\tws.append((x + b, y - a))\n\tif 0 <= x - b < n and 0 <= y + a < n:\n\t\tws.append((x - b, y + a))\n\tif 0 <= x - b < n and 0 <= y - a < n:\n\t\tws.append((x - b, y - a))\n\treturn ws\n\ndef bfs(n, a, b):\n\tmarked = [False for _ in range(n * n)]\n\tmarked[0] = True\n\tdist = [0 for _ in range(n * n)]\n\tq = col.deque()\n\tq.append((0, 0))\n\twhile len(q) > 0:\n\t\tv = q.popleft()\n\t\tvIndex = v[0] * n + v[1]\n\t\tfor w in valids(n, a, b, v):\n\t\t\twIndex = w[0] * n + w[1]\n\t\t\tif not marked[wIndex]:\n\t\t\t\tmarked[wIndex] = True\n\t\t\t\tdist[wIndex] = dist[vIndex] + 1\n\t\t\t\tif w == (n - 1, n - 1):\n\t\t\t\t\treturn dist[wIndex]\n\t\t\t\tq.append(w)\n\treturn -1\nn = int(input().strip())\nres = [[-1 for _ in range(n)] for _ in range(n)]\nfor i in range(n - 1):\n\tfor j in range(i, n - 1):\n\t\tres[i][j] = res[j][i] = bfs(n, i + 1, j + 1)\nfor i in range(n - 1):\n\tprint(' '.join([str(res[i][j]) for j in range(n - 1)]))\n", "import collections\nimport heapq\nimport sys\nn = int(input().strip())\nGOAL = (n - 1, n - 1)\n\ndef heuristic(square, a, b):\n\treturn (GOAL[0] + GOAL[1] - square[0] - square[1]) / (a + b)\n\ndef is_legal(square):\n\treturn 0 <= square[0] < n and 0 <= square[1] < n\n\ndef get_neighbors(square, a, b):\n\tdiffs = ((a, b), (a, -b), (-a, b), (-a, -b), (b, a), (b, -a), (-b, a), (-b, -a))\n\tneighbors = set([])\n\tfor d in diffs:\n\t\tneighbor = (square[0] + d[0], square[1] + d[1])\n\t\tif is_legal(neighbor):\n\t\t\tneighbors.add(neighbor)\n\treturn neighbors\n\ndef moves_to_goal(a, b):\n\tclosed_squares = set([])\n\tfrontier_squares = [(0, [(0, 0), 0])]\n\twhile len(frontier_squares):\n\t\t(current_square, path_len) = heapq.heappop(frontier_squares)[1]\n\t\tif current_square in closed_squares:\n\t\t\tcontinue\n\t\tclosed_squares.add(current_square)\n\t\tneighbors = get_neighbors(current_square, a, b)\n\t\tfor neighbor in neighbors:\n\t\t\tif neighbor == GOAL:\n\t\t\t\treturn path_len + 1\n\t\t\tif not neighbor in closed_squares:\n\t\t\t\theapq.heappush(frontier_squares, (path_len + 1 + heuristic(neighbor, a, b), [neighbor, path_len + 1]))\n\treturn -1\nfor a in range(1, n):\n\trow = []\n\tfor b in range(1, n):\n\t\trow.append(str(moves_to_goal(a, b)))\n\tprint(' '.join(row))\n", "import sys\n\ndef chess(n, i, j):\n\tmemory = set()\n\tinitial = set()\n\tcount = 0\n\tinitial.add((1, 1))\n\twhile len(initial) > 0:\n\t\tlevel = set()\n\t\tfor item in initial:\n\t\t\tif item == (n, n):\n\t\t\t\treturn count\n\t\t\tif item[0] - i > 0:\n\t\t\t\tif item[1] - j > 0:\n\t\t\t\t\tif (item[0] - i, item[1] - j) not in memory:\n\t\t\t\t\t\tmemory.add((item[0] - i, item[1] - j))\n\t\t\t\t\t\tlevel.add((item[0] - i, item[1] - j))\n\t\t\t\tif item[1] + j <= n:\n\t\t\t\t\tif (item[0] - i, item[1] + j) not in memory:\n\t\t\t\t\t\tmemory.add((item[0] - i, item[1] + j))\n\t\t\t\t\t\tlevel.add((item[0] - i, item[1] + j))\n\t\t\tif item[0] + i <= n:\n\t\t\t\tif item[1] - j > 0:\n\t\t\t\t\tif (item[0] + i, item[1] - j) not in memory:\n\t\t\t\t\t\tmemory.add((item[0] + i, item[1] - j))\n\t\t\t\t\t\tlevel.add((item[0] + i, item[1] - j))\n\t\t\t\tif item[1] + j <= n:\n\t\t\t\t\tif (item[0] + i, item[1] + j) not in memory:\n\t\t\t\t\t\tmemory.add((item[0] + i, item[1] + j))\n\t\t\t\t\t\tlevel.add((item[0] + i, item[1] + j))\n\t\t\taux = i\n\t\t\ti = j\n\t\t\tj = aux\n\t\t\tif item[0] - i > 0:\n\t\t\t\tif item[1] - j > 0:\n\t\t\t\t\tif (item[0] - i, item[1] - j) not in memory:\n\t\t\t\t\t\tmemory.add((item[0] - i, item[1] - j))\n\t\t\t\t\t\tlevel.add((item[0] - i, item[1] - j))\n\t\t\t\tif item[1] + j <= n:\n\t\t\t\t\tif (item[0] - i, item[1] + j) not in memory:\n\t\t\t\t\t\tmemory.add((item[0] - i, item[1] + j))\n\t\t\t\t\t\tlevel.add((item[0] - i, item[1] + j))\n\t\t\tif item[0] + i <= n:\n\t\t\t\tif item[1] - j > 0:\n\t\t\t\t\tif (item[0] + i, item[1] - j) not in memory:\n\t\t\t\t\t\tmemory.add((item[0] + i, item[1] - j))\n\t\t\t\t\t\tlevel.add((item[0] + i, item[1] - j))\n\t\t\t\tif item[1] + j <= n:\n\t\t\t\t\tif (item[0] + i, item[1] + j) not in memory:\n\t\t\t\t\t\tmemory.add((item[0] + i, item[1] + j))\n\t\t\t\t\t\tlevel.add((item[0] + i, item[1] + j))\n\t\t\taux = i\n\t\t\ti = j\n\t\t\tj = aux\n\t\tinitial = level\n\t\tcount += 1\n\treturn -1\nn = int(input().strip())\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tprint(chess(n, i, j), end=' ')\n\tprint()\n", "import sys\nimport math\nn = int(input().strip())\n\ndef valid_moves(n, knight, cur_pos):\n\t(i, j) = knight\n\tmoves = [(i, j), (j, i), (i, -j), (-i, j), (-i, -j), (j, -i), (-j, i), (-j, -i)]\n\tres = []\n\tfor move in moves:\n\t\tloc = (cur_pos[0] + move[0], cur_pos[1] + move[1])\n\t\tif loc[0] >= 0 and loc[0] < n and (loc[1] >= 0) and (loc[1] < n):\n\t\t\tres.append(move)\n\treturn res\n\ndef min_moves(n, knight):\n\tcur_pos = (0, 0)\n\tgoal = (n - 1, n - 1)\n\tmoves_queue = [cur_pos]\n\tdist = {}\n\tdist[cur_pos] = 0\n\twhile len(moves_queue):\n\t\tcur_pos = moves_queue.pop(0)\n\t\tif cur_pos == goal:\n\t\t\treturn dist[goal]\n\t\tfor move in valid_moves(n, knight, cur_pos):\n\t\t\tnew_pos = (cur_pos[0] + move[0], cur_pos[1] + move[1])\n\t\t\tif new_pos not in dist:\n\t\t\t\tdist[new_pos] = dist[cur_pos] + 1\n\t\t\t\tmoves_queue.append(new_pos)\n\treturn -1\n\ndef array2str(arr):\n\tres_str = ''\n\tfor row in arr:\n\t\tfor num in row:\n\t\t\tres_str += str(num) + ' '\n\t\tres_str += '\\n'\n\treturn res_str\n\ndef anwser(n):\n\tresults = [[float('nan') for i in range(0, n - 1)] for row in range(0, n - 1)]\n\tfor i in range(len(results)):\n\t\tfor j in range(len(results[0])):\n\t\t\tif i == j:\n\t\t\t\tmove = i + 1\n\t\t\t\tif (n - 1) % move == 0:\n\t\t\t\t\tresults[i][i] = (n - 1) // move\n\t\t\t\telse:\n\t\t\t\t\tresults[i][i] = -1\n\t\t\tif math.isnan(results[i][j]):\n\t\t\t\tresults[i][j] = min_moves(n, (i + 1, j + 1))\n\treturn results\nanwser_str = array2str(anwser(n))\nprint(anwser_str)\n", "import sys\n\ndef next_step(board, target, a, b, n):\n\tmask = 0\n\tfor i in range(n):\n\t\tfor j in range(n):\n\t\t\tif board[n + i][n + j] == target:\n\t\t\t\tmask = 1\n\t\t\t\tif board[n + i + a][n + j + b] == 0:\n\t\t\t\t\tboard[n + i + a][n + j + b] = target + 1\n\t\t\t\tif board[n + i + a][n + j - b] == 0:\n\t\t\t\t\tboard[n + i + a][n + j - b] = target + 1\n\t\t\t\tif board[n + i + b][n + j + a] == 0:\n\t\t\t\t\tboard[n + i + b][n + j + a] = target + 1\n\t\t\t\tif board[n + i + b][n + j - a] == 0:\n\t\t\t\t\tboard[n + i + b][n + j - a] = target + 1\n\t\t\t\tif board[n + i - a][n + j + b] == 0:\n\t\t\t\t\tboard[n + i - a][n + j + b] = target + 1\n\t\t\t\tif board[n + i - a][n + j - b] == 0:\n\t\t\t\t\tboard[n + i - a][n + j - b] = target + 1\n\t\t\t\tif board[n + i - b][n + j + a] == 0:\n\t\t\t\t\tboard[n + i - b][n + j + a] = target + 1\n\t\t\t\tif board[n + i - b][n + j - a] == 0:\n\t\t\t\t\tboard[n + i - b][n + j - a] = target + 1\n\tif mask == 0:\n\t\treturn board\n\treturn next_step(board, target + 1, a, b, n)\n\ndef check_step(a, b, n):\n\tboard = []\n\tfor i in range(3 * n):\n\t\tboard.append([])\n\t\tfor j in range(3 * n):\n\t\t\tboard[i].append(0)\n\tboard[n][n] = 1\n\tnew_board = next_step(board, 1, a, b, n)\n\treturn int(new_board[2 * n - 1][2 * n - 1] - 1)\nn = int(input().strip())\nfor i in range(1, n):\n\tmylist = []\n\tfor j in range(1, n):\n\t\tmylist.append(str(check_step(i, j, n)))\n\tprint(' '.join(mylist))\n", "import sys\nfrom collections import deque\n\ndef main(n):\n\tfor a in range(1, n):\n\t\trow = []\n\t\tfor b in range(1, n):\n\t\t\trow.append(move_knight([a, b], n))\n\t\tprint(' '.join((str(x) for x in row)))\n\ndef move_knight(movement, n):\n\tvisited = [[0, 0]]\n\tpositions = deque()\n\tpositions.append([[0, 0], 0])\n\tmoves = 0\n\twhile positions:\n\t\tcurrent = positions.popleft()\n\t\tc_position = current[0]\n\t\tc_move = current[1]\n\t\tfuture = future_positions(movement, current[0], n)\n\t\tfor f in future:\n\t\t\tif f == [n - 1, n - 1]:\n\t\t\t\treturn c_move + 1\n\t\t\telif f in visited:\n\t\t\t\tpass\n\t\t\telse:\n\t\t\t\tpositions.append([f, c_move + 1])\n\t\t\t\tvisited.append(f)\n\treturn -1\n\ndef future_positions(movement, current, n):\n\tf_ps = []\n\tx = current[0]\n\ty = current[1]\n\ta = movement[0]\n\tb = movement[1]\n\tfor f_x in [x - a, x + a]:\n\t\tif valid(f_x, n):\n\t\t\tfor f_y in [y - b, y + b]:\n\t\t\t\tif valid(f_y, n):\n\t\t\t\t\tf_ps.append([f_x, f_y])\n\tfor f_x in [x - b, x + b]:\n\t\tif valid(f_x, n):\n\t\t\tfor f_y in [y - a, y + a]:\n\t\t\t\tif valid(f_y, n):\n\t\t\t\t\tf_ps.append([f_x, f_y])\n\treturn f_ps\n\ndef valid(i, n):\n\treturn i >= 0 and i < n\nn = int(input().strip())\nmain(n)\n", "import sys\n\ndef new_positions(new_positions, c, d, length, pre_positions):\n\tx_change = [d, d, -d, -d, c, c, -c, -c]\n\ty_change = [c, -c, c, -c, d, -d, d, -d]\n\tpositions = set([])\n\tfor item in new_positions:\n\t\tpositions = positions | set([(item[0] + x, item[1] + y) for (x, y) in zip(x_change, y_change) if 0 <= item[0] + x and item[0] + x < length and (0 <= item[1] + y) and (item[1] + y < length)])\n\treturn positions - pre_positions\nn = int(input().strip())\nfor i in range(1, n):\n\tstr_row = ''\n\tfor j in range(1, n):\n\t\tpositions_all = set([])\n\t\tnew_set = set([(n - 1, n - 1)])\n\t\tcount = 0\n\t\twhile len(new_set) > 0 and (0, 0) not in new_set:\n\t\t\tpositions_all = positions_all | new_set\n\t\t\tnew_set = new_positions(new_set, i, j, n, positions_all)\n\t\t\tcount += 1\n\t\tstr_row += str(count) + ' ' if (0, 0) in new_set else str(-1) + ' '\n\tprint(str_row.strip())\n", "class Game(object):\n\n\tdef __init__(self, n):\n\t\tself.n = n\n\t\tself.knights = {(a, b) for a in range(1, n) for b in range(1, a + 1)}\n\t\tself.answers = {}\n\t\tself.initial = (0, 0)\n\t\tself.goal = (n - 1, n - 1)\n\n\tdef available_moves(self, pos, k):\n\t\tpossible_moves = [(pos[0] + x * k[i], pos[1] + y * k[int(not i)]) for x in (1, -1) for y in (1, -1) for i in (0, 1)]\n\t\treturn {m for m in possible_moves if min(m) >= 0 and max(m) < self.n}\n\n\tdef play(self, k):\n\t\tif k in self.answers:\n\t\t\treturn self.answers[k]\n\t\tnext_moves = {self.initial}\n\t\tplayed_moves = {}\n\t\tmove_num = 0\n\t\twhile len(next_moves) > 0:\n\t\t\tcurrent_moves = next_moves\n\t\t\tnext_moves = set()\n\t\t\tfor m in current_moves:\n\t\t\t\tif m == self.goal:\n\t\t\t\t\tself.answers[k] = move_num\n\t\t\t\t\tself.answers[k[::-1]] = move_num\n\t\t\t\t\treturn move_num\n\t\t\t\tplayed_moves[m] = move_num\n\t\t\t\tnext_moves.update(self.available_moves(m, k))\n\t\t\tnext_moves = next_moves.difference(played_moves.keys())\n\t\t\tmove_num += 1\n\t\tself.answers[k] = -1\n\t\tself.answers[k[::-1]] = -1\n\t\treturn -1\n\n\tdef evaluate_all(self):\n\t\tfor k in self.knights:\n\t\t\tx = self.play(k)\n\t\toutput = [[0 for __ in range(self.n - 1)] for _ in range(self.n - 1)]\n\t\tfor (k, v) in self.answers.items():\n\t\t\toutput[k[0] - 1][k[1] - 1] = str(v)\n\t\tprint('\\n'.join([' '.join(_) for _ in output]))\nn = int(input().strip())\ngame = Game(n)\ngame.evaluate_all()\n", "import sys\nimport queue\nn = int(input().strip())\n(a, b) = (1, 1)\n\ndef valid_move(i, j):\n\treturn 0 <= i < n and 0 <= j < n\n\ndef find_new_moves(i, j):\n\tmoves = [(i + a, j + b), (i + a, j - b), (i - a, j + b), (i - a, j - b), (i + b, j + a), (i + b, j - a), (i - b, j + a), (i - b, j - a)]\n\tmoves = [move for move in moves if valid_move(move[0], move[1])]\n\treturn moves\n\ndef BFS():\n\tdistance = [[-1] * n for i in range(n)]\n\tcolor = [['white'] * n for i in range(n)]\n\tparent = [[(-1, -1)] * n for i in range(n)]\n\tsource = (0, 0)\n\tcolor[0][0] = 'gray'\n\tdistance[0][0] = 0\n\tparent[0][0] = (-1, -1)\n\tq = queue.Queue(250)\n\tq.put(source)\n\twhile not q.empty() and distance[n - 1][n - 1] is -1:\n\t\tu = q.get()\n\t\tfor v in find_new_moves(u[0], u[1]):\n\t\t\ti = v[0]\n\t\t\tj = v[1]\n\t\t\tif color[i][j] is 'white':\n\t\t\t\tcolor[i][j] = 'gray'\n\t\t\t\tdistance[i][j] = distance[u[0]][u[1]] + 1\n\t\t\t\tparent[i][j] = u\n\t\t\t\tq.put((i, j))\n\t\tcolor[u[0]][u[1]] = 'black'\n\treturn distance[n - 1][n - 1]\nfor i in range(1, n):\n\tpaths = []\n\tfor j in range(1, n):\n\t\t(a, b) = (i, j)\n\t\tanswer = BFS()\n\t\tpaths.append(str(answer))\n\tprint(' '.join(paths))\n", "from copy import deepcopy\nimport sys\nn = int(input().strip())\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\ttable = [[None for x in range(n)] for x in range(n)]\n\t\ttable[0][0] = 0\n\t\tstep_num = 0\n\t\told_table = deepcopy(table)\n\t\tnew_table = deepcopy(table)\n\t\twhile True:\n\t\t\ttry:\n\t\t\t\tfor k in range(n):\n\t\t\t\t\tfor l in range(n):\n\t\t\t\t\t\tif old_table[k][l] != step_num:\n\t\t\t\t\t\t\tcontinue\n\t\t\t\t\t\tnew_x = k + i\n\t\t\t\t\t\tnew_y = l + j\n\t\t\t\t\t\tif not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):\n\t\t\t\t\t\t\tif new_table[new_x][new_y] is None:\n\t\t\t\t\t\t\t\tnew_table[new_x][new_y] = step_num + 1\n\t\t\t\t\t\t\t\tif new_x == n - 1 and new_y == n - 1:\n\t\t\t\t\t\t\t\t\tprint(step_num + 1, end=' ')\n\t\t\t\t\t\t\t\t\traise ValueError\n\t\t\t\t\t\tnew_x = k + j\n\t\t\t\t\t\tnew_y = l + i\n\t\t\t\t\t\tif not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):\n\t\t\t\t\t\t\tif new_table[new_x][new_y] is None:\n\t\t\t\t\t\t\t\tnew_table[new_x][new_y] = step_num + 1\n\t\t\t\t\t\t\t\tif new_x == n - 1 and new_y == n - 1:\n\t\t\t\t\t\t\t\t\tprint(step_num + 1, end=' ')\n\t\t\t\t\t\t\t\t\traise ValueError\n\t\t\t\t\t\tnew_x = k - i\n\t\t\t\t\t\tnew_y = l + j\n\t\t\t\t\t\tif not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):\n\t\t\t\t\t\t\tif new_table[new_x][new_y] is None:\n\t\t\t\t\t\t\t\tnew_table[new_x][new_y] = step_num + 1\n\t\t\t\t\t\tnew_x = k + i\n\t\t\t\t\t\tnew_y = l - j\n\t\t\t\t\t\tif not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):\n\t\t\t\t\t\t\tif new_table[new_x][new_y] is None:\n\t\t\t\t\t\t\t\tnew_table[new_x][new_y] = step_num + 1\n\t\t\t\t\t\tnew_x = k - i\n\t\t\t\t\t\tnew_y = l - j\n\t\t\t\t\t\tif not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):\n\t\t\t\t\t\t\tif new_table[new_x][new_y] is None:\n\t\t\t\t\t\t\t\tnew_table[new_x][new_y] = step_num + 1\n\t\t\t\t\t\tnew_x = k - j\n\t\t\t\t\t\tnew_y = l + i\n\t\t\t\t\t\tif not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):\n\t\t\t\t\t\t\tif new_table[new_x][new_y] is None:\n\t\t\t\t\t\t\t\tnew_table[new_x][new_y] = step_num + 1\n\t\t\t\t\t\tnew_x = k + j\n\t\t\t\t\t\tnew_y = l - i\n\t\t\t\t\t\tif not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):\n\t\t\t\t\t\t\tif new_table[new_x][new_y] is None:\n\t\t\t\t\t\t\t\tnew_table[new_x][new_y] = step_num + 1\n\t\t\t\t\t\tnew_x = k - j\n\t\t\t\t\t\tnew_y = l - i\n\t\t\t\t\t\tif not (new_x < 0 or new_y < 0 or new_x >= n or (new_y >= n)):\n\t\t\t\t\t\t\tif new_table[new_x][new_y] is None:\n\t\t\t\t\t\t\t\tnew_table[new_x][new_y] = step_num + 1\n\t\t\t\tif old_table == new_table:\n\t\t\t\t\tprint(str(-1), end=' ')\n\t\t\t\t\traise ValueError\n\t\t\t\told_table = deepcopy(new_table)\n\t\t\t\tstep_num += 1\n\t\t\texcept ValueError:\n\t\t\t\tbreak\n\tprint()\n", "import sys\nfrom queue import Queue\n\ndef in_range(i, j):\n\treturn 0 <= i < n and 0 <= j < n\nn = int(input().strip())\nans = [[-1 for i in range(n - 1)] for j in range(n - 1)]\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tboard = [[-1 for i in range(n)] for j in range(n)]\n\t\tboard[0][0] = 0\n\t\tq = Queue()\n\t\tvisited = set()\n\t\tq.put((0, 0))\n\t\tvisited.add((0, 0))\n\t\twhile not q.empty():\n\t\t\t(x, y) = q.get()\n\t\t\tstep = board[x][y]\n\t\t\tif (x, y) == (n - 1, n - 1):\n\t\t\t\tans[i - 1][j - 1] = board[n - 1][n - 1]\n\t\t\t\tbreak\n\t\t\tset_of_moves = [(x + c1 * i, y + c2 * j) for c1 in [-1, 1] for c2 in [-1, 1]] + [(x + c1 * j, y + c2 * i) for c1 in [-1, 1] for c2 in [-1, 1]]\n\t\t\tfor pt in set_of_moves:\n\t\t\t\tif in_range(*pt) and pt not in visited:\n\t\t\t\t\tboard[pt[0]][pt[1]] = step + 1\n\t\t\t\t\tvisited.add(pt)\n\t\t\t\t\tq.put(pt)\nfor ar in ans:\n\tprint(*ar)\n", "import sys\nn = int(input().strip())\nfrom queue import deque\n\ndef get_Neighbours(p, i, j):\n\tpotential_neighbours = [(p[0] + i, p[1] + j), (p[0] + j, p[1] + i), (p[0] - i, p[1] + j), (p[0] - j, p[1] + i), (p[0] + i, p[1] - j), (p[0] + j, p[1] - i), (p[0] - i, p[1] - j), (p[0] - j, p[1] - i)]\n\tneighbours = []\n\tfor item in potential_neighbours:\n\t\tif item[0] >= 0 and item[1] >= 0 and (item[0] < n) and (item[1] < n):\n\t\t\tneighbours.append(item)\n\treturn neighbours\ncount = [[None for _ in range(n - 1)] for _ in range(n - 1)]\nfor i in range(1, n):\n\tfor j in range(i, n):\n\t\tvisited = [[False for _ in range(n)] for _ in range(n)]\n\t\tcounter = [[float('inf') for _ in range(n)] for _ in range(n)]\n\t\tcounter[0][0] = 0\n\t\tqueue = deque([(0, 0)])\n\t\twhile len(queue):\n\t\t\tcP = queue.pop()\n\t\t\tif visited[cP[0]][cP[1]]:\n\t\t\t\tcontinue\n\t\t\tvisited[cP[0]][cP[1]] = True\n\t\t\tneighbours = get_Neighbours(cP, i, j)\n\t\t\tfor item in neighbours:\n\t\t\t\tqueue.appendleft(item)\n\t\t\t\tcounter[item[0]][item[1]] = min(counter[item[0]][item[1]], counter[cP[0]][cP[1]] + 1)\n\t\tt = counter[n - 1][n - 1]\n\t\tif t == float('inf'):\n\t\t\tcount[i - 1][j - 1] = count[j - 1][i - 1] = -1\n\t\telse:\n\t\t\tcount[i - 1][j - 1] = count[j - 1][i - 1] = t\nfor i in range(n - 1):\n\tprint(' '.join(list(map(str, count[i]))))\n", "from copy import copy\nimport sys\nn = int(input().strip())\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tcells = set()\n\t\tcells.add(0)\n\t\tmoves = 0\n\t\twhile n ** 2 - 1 not in cells:\n\t\t\told_cells = copy(cells)\n\t\t\tnew_cells = set()\n\t\t\tfor c in cells:\n\t\t\t\tif 0 <= c % n + j < n and 0 <= c // n + i < n:\n\t\t\t\t\tnew_cells.add(c + i * n + j)\n\t\t\t\tif 0 <= c % n - j < n and 0 <= c // n + i < n:\n\t\t\t\t\tnew_cells.add(c + i * n - j)\n\t\t\t\tif 0 <= c % n + j < n and 0 <= c // n - i < n:\n\t\t\t\t\tnew_cells.add(c - i * n + j)\n\t\t\t\tif 0 <= c % n - j < n and 0 <= c // n - i < n:\n\t\t\t\t\tnew_cells.add(c - i * n - j)\n\t\t\t\tif 0 <= c % n + i < n and 0 <= c // n + j < n:\n\t\t\t\t\tnew_cells.add(c + i + j * n)\n\t\t\t\tif 0 <= c % n + i < n and 0 <= c // n - j < n:\n\t\t\t\t\tnew_cells.add(c + i - j * n)\n\t\t\t\tif 0 <= c % n - i < n and 0 <= c // n + j < n:\n\t\t\t\t\tnew_cells.add(c - i + j * n)\n\t\t\t\tif 0 <= c % n - i < n and 0 <= c // n - j < n:\n\t\t\t\t\tnew_cells.add(c - i - j * n)\n\t\t\tcells = cells.union(new_cells)\n\t\t\tif cells == old_cells:\n\t\t\t\tmoves = -1\n\t\t\t\tbreak\n\t\t\tmoves += 1\n\t\tprint(moves, end=' ')\n\tprint()\n", "import sys\nn = int(input().strip())\n\ndef isValid(pos):\n\treturn pos[0] >= 0 and pos[1] >= 0 and (pos[0] < n) and (pos[1] < n)\n\ndef possible_moves(position, i, j):\n\t(x, y) = [int(x) for x in position.split(',')]\n\tposs_moves = [(x + i, y + j), (x - i, y + j), (x + i, y - j), (x - i, y - j), (x + j, y + i), (x - j, y + i), (x + j, y - i), (x - j, y - i)]\n\tout_moves = []\n\tfor move in poss_moves:\n\t\tif isValid(move):\n\t\t\tout_moves.append({'position': '%s,%s' % (move[0], move[1])})\n\treturn out_moves\n\ndef bfs(root, goal, i, j):\n\tnode_set = []\n\tqueue = []\n\troot['parent'] = None\n\tqueue.append(root)\n\twhile len(queue) > 0:\n\t\tcurrent = queue.pop(0)\n\t\tif current['position'] == goal['position']:\n\t\t\treturn current\n\t\tfor node in possible_moves(current['position'], i, j):\n\t\t\tif not any([node['position'] == x['position'] for x in node_set]):\n\t\t\t\tnode_set.append(node)\n\t\t\t\tnode['parent'] = current\n\t\t\t\tqueue.append(node)\n\treturn False\n\ndef knightL(i, j):\n\tif True:\n\t\troot = {}\n\t\troot['position'] = '%s,%s' % (0, 0)\n\t\tgoal = {}\n\t\tgoal['position'] = '%s,%s' % (n - 1, n - 1)\n\t\tsuccess = bfs(root, goal, i, j)\n\t\tif success:\n\t\t\tmoves = 0\n\t\t\twhile success.get('parent', False):\n\t\t\t\tmoves += 1\n\t\t\t\tsuccess = success['parent']\n\t\t\treturn moves\n\t\telse:\n\t\t\treturn -1\n\treturn '-1'\noutput = ''\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\toutput += str(knightL(i, j)) + ' '\n\toutput += '\\n'\nprint(output)\n", "from collections import deque\n\ndef min_moves_bfs(xf, yf, a, b, visited, q):\n\twhile q:\n\t\t(x, y, num_moves) = q.popleft()\n\t\tfound = enqueue_4_neighbors(x, y, a, b, visited, q, num_moves + 1, xf, yf)\n\t\tif found != -1:\n\t\t\treturn found\n\t\tif a != b:\n\t\t\tfound = enqueue_4_neighbors(x, y, b, a, visited, q, num_moves + 1, xf, yf)\n\t\t\tif found != -1:\n\t\t\t\treturn found\n\treturn -1\n\ndef enqueue_4_neighbors(x, y, a, b, visited, q, num_moves, xf, yf):\n\tif x - a >= 0 and y - b >= 0 and (not visited[x - a][y - b]):\n\t\tq.append((x - a, y - b, num_moves))\n\t\tvisited[x - a][y - b] = True\n\t\tif q[-1][0] == xf and q[-1][1] == yf:\n\t\t\treturn q[-1][2]\n\tif x + a < len(visited) and y - b >= 0 and (not visited[x + a][y - b]):\n\t\tq.append((x + a, y - b, num_moves))\n\t\tvisited[x + a][y - b] = True\n\t\tif q[-1][0] == xf and q[-1][1] == yf:\n\t\t\treturn q[-1][2]\n\tif x - a >= 0 and y + b < len(visited) and (not visited[x - a][y + b]):\n\t\tq.append((x - a, y + b, num_moves))\n\t\tvisited[x - a][y + b] = True\n\t\tif q[-1][0] == xf and q[-1][1] == yf:\n\t\t\treturn q[-1][2]\n\tif x + a < len(visited) and y + b < len(visited) and (not visited[x + a][y + b]):\n\t\tq.append((x + a, y + b, num_moves))\n\t\tvisited[x + a][y + b] = True\n\t\tif q[-1][0] == xf and q[-1][1] == yf:\n\t\t\treturn q[-1][2]\n\treturn -1\nn = int(input().strip())\nfor a in range(1, n):\n\tfor b in range(1, n):\n\t\tvisited = [[False] * n for _ in range(n)]\n\t\tvisited[0][0] = True\n\t\tq = deque([(0, 0, 0)])\n\t\tprint(str(min_moves_bfs(n - 1, n - 1, a, b, visited, q)) + ' ', end='')\n\tprint('')\n", "import queue\n\ndef solution(n, b):\n\tif b[0] >= n or b[0] < 0:\n\t\treturn False\n\tif b[1] >= n or b[1] < 0:\n\t\treturn False\n\treturn True\n\ndef result(n, y1, a):\n\tres = []\n\tfor y2 in range(1, n):\n\t\tif (y1, y2) in a:\n\t\t\tres.append(a[y1, y2])\n\t\telif (y2, y1) in a:\n\t\t\tres.append(a[y2, y1])\n\t\telse:\n\t\t\trep = search(y1, y2, n)\n\t\t\ta[y1, y2] = rep\n\t\t\tres.append(rep)\n\treturn res\n\ndef search(y1, y2, n):\n\tx = {}\n\ty = {}\n\tworklist = queue.Queue()\n\tworklist.put((0, 0))\n\twhile worklist.qsize() != 0:\n\t\tb = worklist.get()\n\t\tif b in x:\n\t\t\tcontinue\n\t\tx[b] = True\n\t\tfor k in compute(y1, y2, n, b):\n\t\t\tif solution(n, k) and k not in x:\n\t\t\t\tworklist.put(k)\n\t\t\t\ty[k] = b\n\t\t\telse:\n\t\t\t\tcontinue\n\tif (n - 1, n - 1) in x:\n\t\tres = sol(n, y)\n\t\treturn res\n\telse:\n\t\treturn -1\n\ndef compute(y1, y2, n, b):\n\tx1 = b[0]\n\tx2 = b[1]\n\tarr = []\n\tarr.append((x1 + y1, x2 + y2))\n\tarr.append((x1 + y1, x2 - y2))\n\tarr.append((x1 - y1, x2 + y2))\n\tarr.append((x1 - y1, x2 - y2))\n\tarr.append((x1 + y2, x2 + y1))\n\tarr.append((x1 + y2, x2 - y1))\n\tarr.append((x1 - y2, x2 + y1))\n\tarr.append((x1 - y2, x2 - y1))\n\treturn arr\n\ndef sol(n, y):\n\ttot = 0\n\tb = (n - 1, n - 1)\n\twhile b in y:\n\t\tp = y[b]\n\t\ttot = tot + 1\n\t\tif p == (0, 0):\n\t\t\treturn tot\n\t\telse:\n\t\t\tb = p\nn = int(input())\na = {}\nfor i in range(1, n):\n\tres = result(n, i, a)\n\tprint(str(res)[1:-1].replace(',', ''))\n", "import sys\nn = int(input().strip())\nm = [[-1 for x in range(n)] for y in range(n)]\ng = 1\nwhile g <= n - 1:\n\td = 1\n\twhile d <= n - 1:\n\t\tvisited = []\n\t\tvisited.append((n - 1, n - 1))\n\t\tcounter = 0\n\t\tcur_len = 0\n\t\tdiff = len(visited) - cur_len\n\t\tif m[g][d] == -1:\n\t\t\twhile len(visited) > cur_len and (0, 0) not in visited:\n\t\t\t\tcur_len = len(visited)\n\t\t\t\tarr = visited[len(visited) - diff:len(visited)]\n\t\t\t\th = 0\n\t\t\t\twhile h <= len(arr) - 1:\n\t\t\t\t\t(t, r) = arr[h]\n\t\t\t\t\tif (t - g <= n - 1 and t - g >= 0) and (r - d <= n - 1 and r - d >= 0) and ((t - g, r - d) not in visited):\n\t\t\t\t\t\tvisited.append((t - g, r - d))\n\t\t\t\t\tif (t - g <= n - 1 and t - g >= 0) and (r + d <= n - 1 and r + d >= 0) and ((t - g, r + d) not in visited):\n\t\t\t\t\t\tvisited.append((t - g, r + d))\n\t\t\t\t\tif (t + g <= n - 1 and t + g >= 0) and (r - d <= n - 1 and r - d >= 0) and ((t + g, r - d) not in visited):\n\t\t\t\t\t\tvisited.append((t + g, r - d))\n\t\t\t\t\tif (t + g <= n - 1 and t + g >= 0) and (r + d <= n - 1 and r + d >= 0) and ((t + g, r + d) not in visited):\n\t\t\t\t\t\tvisited.append((t + g, r + d))\n\t\t\t\t\tif (t - d <= n - 1 and t - d >= 0) and (r - g <= n - 1 and r - g >= 0) and ((t - d, r - g) not in visited):\n\t\t\t\t\t\tvisited.append((t - d, r - g))\n\t\t\t\t\tif (t - d <= n - 1 and t - d >= 0) and (r + g <= n - 1 and r + g >= 0) and ((t - d, r + g) not in visited):\n\t\t\t\t\t\tvisited.append((t - d, r + g))\n\t\t\t\t\tif (t + d <= n - 1 and t + d >= 0) and (r - g <= n - 1 and r - g >= 0) and ((t + d, r - g) not in visited):\n\t\t\t\t\t\tvisited.append((t + d, r - g))\n\t\t\t\t\tif (t + d <= n - 1 and t + d >= 0) and (r + g <= n - 1 and r + g >= 0) and ((t + d, r + g) not in visited):\n\t\t\t\t\t\tvisited.append((t + d, r + g))\n\t\t\t\t\th = h + 1\n\t\t\t\tdiff = len(visited) - cur_len\n\t\t\t\tcounter = counter + 1\n\t\t\tif (0, 0) in visited:\n\t\t\t\tm[g][d] = counter\n\t\t\t\tm[d][g] = m[g][d]\n\t\td = d + 1\n\tg = g + 1\np = 1\nwhile p <= n - 1:\n\tline = ''\n\tg = 1\n\twhile g <= n - 1:\n\t\tline = line + ' ' + str(m[p][g])\n\t\tg = g + 1\n\tprint(line.lstrip())\n\tp = p + 1\n", "import sys\nn = int(input().strip())\n\ndef possibles(i, j, x, y, n):\n\tp = []\n\tfor c in range(-1, 2, 2):\n\t\tfor d in range(-1, 2, 2):\n\t\t\tfor (a, b) in [(i, j), (j, i)]:\n\t\t\t\ttx = x + a * c\n\t\t\t\tty = y + b * d\n\t\t\t\tif tx >= 0 and tx < n and (ty >= 0) and (ty < n):\n\t\t\t\t\tp.append((tx, ty))\n\treturn p\n\ndef dijkstra(a, b, tx, ty, n):\n\tx = 0\n\ty = 0\n\tvisited = []\n\ttoVisit = [(x, y)]\n\tdistance = {(x, y): 0}\n\twhile len(toVisit) > 0:\n\t\tcurrent = toVisit[0]\n\t\tfor node in possibles(a, b, current[0], current[1], n):\n\t\t\tif node not in visited and node not in toVisit:\n\t\t\t\ttoVisit.append(node)\n\t\t\t\tdistance[node] = distance[current] + 1\n\t\t\telse:\n\t\t\t\tdistance[node] = min(distance[node], distance[current] + 1)\n\t\ttoVisit.remove(current)\n\t\tvisited.append(current)\n\tif (tx, ty) in distance:\n\t\treturn distance[tx, ty]\n\treturn -1\nfor a in range(1, n):\n\tfor b in range(1, n):\n\t\td = dijkstra(a, b, n - 1, n - 1, n)\n\t\tprint(d, end=' ')\n\tprint()\n", "import sys\nn = int(input().strip())\n\nclass Graph:\n\n\tdef __init__(self, board_size, a, b):\n\t\tself.board_size = board_size\n\t\tnodes = [(x, y) for x in range(board_size) for y in range(board_size)]\n\t\tself.path_dict = {k: set() for k in nodes}\n\t\tfor node in self.path_dict:\n\t\t\tself.path_dict[node] = {(node[0] + x, node[1] + y) for (x, y) in [(a, b), (-a, -b), (a, -b), (-a, b), (b, a), (-b, -a), (b, -a), (-b, a)] if 0 <= node[0] + x < board_size and 0 <= node[1] + y < board_size}\n\n\tdef solution(self):\n\t\tdistance = {(x, y): -1 for x in range(self.board_size) for y in range(self.board_size)}\n\t\tvisited = {(self.board_size - 1, self.board_size - 1)}\n\t\tcurrentDistance = 0\n\t\ttoVisitNext = self.path_dict[self.board_size - 1, self.board_size - 1]\n\t\tdistance[self.board_size - 1, self.board_size - 1] = 0\n\t\twhile len(toVisitNext) > 0:\n\t\t\tnewDestinations = set()\n\t\t\tcurrentDistance += 1\n\t\t\tfor node in toVisitNext:\n\t\t\t\tvisited.add(node)\n\t\t\t\tdistance[node] = currentDistance\n\t\t\t\tnewDestinations |= self.path_dict[node]\n\t\t\ttoVisitNext = set(newDestinations) - visited\n\t\treturn distance[0, 0]\nfor a in range(1, n):\n\trow = ''\n\tfor b in range(1, n):\n\t\tgraph = Graph(n, a, b)\n\t\trow += str(graph.solution()) + ' '\n\tprint(row.strip())\n", "import sys\nn = int(input().strip())\n\ndef getMoves(x, y, i):\n\tmoves = []\n\tm1 = i + x + n * y\n\tm2 = i + x - n * y\n\tm3 = i - x + n * y\n\tm4 = i - x - n * y\n\tm5 = i + y + n * x\n\tm6 = i + y - n * x\n\tm7 = i - y + n * x\n\tm8 = i - y - n * x\n\tif i % n >= x:\n\t\tif y <= int(i / n):\n\t\t\tmoves.append(m4)\n\t\tif y + int(i / n) < n:\n\t\t\tmoves.append(m3)\n\tif i % n >= y:\n\t\tif x <= int(i / n):\n\t\t\tmoves.append(m8)\n\t\tif x + int(i / n) < n:\n\t\t\tmoves.append(m7)\n\tif i % n + x < n:\n\t\tif y <= int(i / n):\n\t\t\tmoves.append(m2)\n\t\tif y + int(i / n) < n:\n\t\t\tmoves.append(m1)\n\tif i % n + y < n:\n\t\tif x <= int(i / n):\n\t\t\tmoves.append(m6)\n\t\tif x + int(i / n) < n:\n\t\t\tmoves.append(m5)\n\treturn moves\n\ndef shortestPath(start, end, x, y):\n\tfound = False\n\tqueue = [start]\n\tprev = {start: -1}\n\tvisited = set()\n\twhile len(queue) > 0:\n\t\tc = queue.pop(0)\n\t\tmoves = getMoves(x, y, c)\n\t\tvisited.add(c)\n\t\tif end in moves:\n\t\t\tfound = True\n\t\t\tprev[end] = c\n\t\t\tbreak\n\t\telse:\n\t\t\tfor u in moves:\n\t\t\t\tif u not in visited and u not in queue:\n\t\t\t\t\tqueue.append(u)\n\t\t\t\t\tprev[u] = c\n\tif found:\n\t\tcount = 0\n\t\tpath = [end]\n\t\tx = end\n\t\twhile x != -1:\n\t\t\tx = prev[x]\n\t\t\tpath.append(x)\n\t\t\tcount += 1\n\t\treturn count - 1\n\telse:\n\t\treturn -1\nstart = 0\nend = n * n - 1\nanswer = []\nfor y in range(n):\n\tanswer.append([-1] * n)\nfor y in range(n - 1):\n\tfor x in range(n - 1):\n\t\tanswer[x][y] = shortestPath(start, end, x + 1, y + 1)\n\t\tprint(answer[x][y], end=' ')\n\tprint('')\n", "import sys\nn = int(input().strip())\n\ndef get_moves(p, d):\n\tmoves = set()\n\tfor i in (d[0], -d[0]):\n\t\tfor j in (d[1], -d[1]):\n\t\t\tx = p[0] + i\n\t\t\ty = p[1] + j\n\t\t\tmove = (x, y)\n\t\t\tif 0 <= x < n and 0 <= y < n:\n\t\t\t\tmoves.add((x, y))\n\treturn moves\n\ndef make_move(p, d):\n\tm1 = get_moves(p, d)\n\tm2 = get_moves(p, d[::-1])\n\tposs = set.union(m1, m2)\n\treturn poss\n\ndef get_to(init, dest, step):\n\thistory = set()\n\tc = 0\n\thistory.add(init)\n\tobs = [(init, c)]\n\twhile obs:\n\t\t(point, cost) = obs.pop(0)\n\t\tnp = make_move(point, step)\n\t\tfor p in np:\n\t\t\tif p == dest:\n\t\t\t\treturn cost + 1\n\t\t\tif not p in history:\n\t\t\t\thistory.add(p)\n\t\t\t\tobs.append((p, cost + 1))\n\treturn -1\n\ndef build_matrix(n):\n\tinit = (0, 0)\n\tdest = (n - 1, n - 1)\n\tres = [[None for i in range(n - 1)] for j in range(n - 1)]\n\tfor i in range(1, n):\n\t\tfor j in range(1, i + 1):\n\t\t\tstep = (i, j)\n\t\t\tcost = get_to(init, dest, step)\n\t\t\tres[i - 1][j - 1] = cost\n\t\t\tres[j - 1][i - 1] = cost\n\tfor x in res:\n\t\tline = ' '.join([str(y) for y in x])\n\t\tprint(line)\n\ndef test(num):\n\tfrom timeit import default_timer as timer\n\tt = timer()\n\tfor i in range(num):\n\t\tbuild_matrix(n)\n\tprint(timer() - t)\nbuild_matrix(n)\n", "def path_len(l_knight):\n\tboard = []\n\tfor n in range(N):\n\t\tboard.append([-1] * N)\n\t(n, m) = l_knight\n\t(x, y) = [0, 0]\n\n\tdef possible_moves(x, y, n, m):\n\t\tmoves = []\n\t\tedge = len(board)\n\t\txn_safe = x + n < edge\n\t\txm_safe = x + m < edge\n\t\tym_safe = y + m < edge\n\t\tyn_safe = y + n < edge\n\t\tym0_safe = y - m >= 0\n\t\tyn0_safe = y - n >= 0\n\t\txn0_safe = x - n >= 0\n\t\txm0_safe = x - m >= 0\n\t\tif xn_safe and ym_safe:\n\t\t\tmoves.append([x + n, y + m])\n\t\tif xn_safe and ym0_safe:\n\t\t\tmoves.append([x + n, y - m])\n\t\tif xn0_safe and ym_safe:\n\t\t\tmoves.append([x - n, y + m])\n\t\tif xn0_safe and ym0_safe:\n\t\t\tmoves.append([x - n, y - m])\n\t\tif xm_safe and yn_safe:\n\t\t\tmoves.append([x + m, y + n])\n\t\tif xm_safe and yn0_safe:\n\t\t\tmoves.append([x + m, y - n])\n\t\tif xm0_safe and yn_safe:\n\t\t\tmoves.append([x - m, y + n])\n\t\tif xm0_safe and yn0_safe:\n\t\t\tmoves.append([x - m, y - n])\n\t\treturn moves\n\tqueue = []\n\tqueue.append((x, y, 0))\n\twhile len(queue) > 0:\n\t\t(x, y, moves) = queue.pop(0)\n\t\tif board[x][y] != -1 and moves >= board[x][y]:\n\t\t\tcontinue\n\t\tboard[x][y] = moves\n\t\tnext_moves = possible_moves(x, y, n, m)\n\t\tfor next in next_moves:\n\t\t\tqueue.append((next[0], next[1], moves + 1))\n\treturn board[-1][-1]\nN = int(input())\nresults = [0] * (N - 1)\ndiagonal_length = N - 1\nfor n in range(N - 1):\n\tresults[n] = [0] * N\n\tfor m in range(n + 1):\n\t\tl_knight = (n + 1, m + 1)\n\t\tif m == n and diagonal_length % (n + 1) == 0:\n\t\t\tpath = int(diagonal_length / (m + 1))\n\t\telse:\n\t\t\tpath = path_len(l_knight)\n\t\tresults[n][m] = path\n\t\tresults[m][n] = path\nfor n in range(len(results)):\n\tfor m in range(len(results)):\n\t\tprint(results[n][m], end=' ')\n\tprint()\n", "import sys\nn = int(input().strip())\nmoves = [[0 for x in range(n - 1)] for y in range(n - 1)]\nfor i in range(1, n):\n\tfor j in range(i, n):\n\t\tlookup = [[(0, 0)]]\n\t\tcurrent = set()\n\t\tcurrent.add((0, 0))\n\t\tunvisited = set()\n\t\tfor k in range(n):\n\t\t\tfor l in range(n):\n\t\t\t\tunvisited.add((k, l))\n\t\tunvisited.remove((0, 0))\n\t\td = 0\n\t\twhile len(unvisited) > 0:\n\t\t\tcurrent = set()\n\t\t\tfor loc in lookup[d]:\n\t\t\t\tif loc[0] + i < n and loc[1] + j < n and ((loc[0] + i, loc[1] + j) in unvisited):\n\t\t\t\t\tcurrent.add((loc[0] + i, loc[1] + j))\n\t\t\t\tif loc[0] + i < n and loc[1] - j >= 0 and ((loc[0] + i, loc[1] - j) in unvisited):\n\t\t\t\t\tcurrent.add((loc[0] + i, loc[1] - j))\n\t\t\t\tif loc[0] - i >= 0 and loc[1] + j < n and ((loc[0] - i, loc[1] + j) in unvisited):\n\t\t\t\t\tcurrent.add((loc[0] - i, loc[1] + j))\n\t\t\t\tif loc[0] - i >= 0 and loc[1] - j >= 0 and ((loc[0] - i, loc[1] - j) in unvisited):\n\t\t\t\t\tcurrent.add((loc[0] - i, loc[1] - j))\n\t\t\t\tif loc[0] + j < n and loc[1] + i < n and ((loc[0] + j, loc[1] + i) in unvisited):\n\t\t\t\t\tcurrent.add((loc[0] + j, loc[1] + i))\n\t\t\t\tif loc[0] + j < n and loc[1] - i >= 0 and ((loc[0] + j, loc[1] - i) in unvisited):\n\t\t\t\t\tcurrent.add((loc[0] + j, loc[1] - i))\n\t\t\t\tif loc[0] - j >= 0 and loc[1] + i < n and ((loc[0] - j, loc[1] + i) in unvisited):\n\t\t\t\t\tcurrent.add((loc[0] - j, loc[1] + i))\n\t\t\t\tif loc[0] - j >= 0 and loc[1] - i >= 0 and ((loc[0] - j, loc[1] - i) in unvisited):\n\t\t\t\t\tcurrent.add((loc[0] - j, loc[1] - i))\n\t\t\tif (n - 1, n - 1) in current:\n\t\t\t\tmoves[i - 1][j - 1] = d + 1\n\t\t\t\tmoves[j - 1][i - 1] = d + 1\n\t\t\t\tbreak\n\t\t\tif current == set():\n\t\t\t\tmoves[i - 1][j - 1] = -1\n\t\t\t\tmoves[j - 1][i - 1] = -1\n\t\t\t\tbreak\n\t\t\tunvisited -= current\n\t\t\tlookup.append(current)\n\t\t\td += 1\nfor a in moves:\n\tfor b in a:\n\t\tprint(b, end=' ')\n\tprint()\n", "n = int(input().strip())\npairs = []\n(start, end) = ((0, 0), (n - 1, n - 1))\n\ndef validPos(pos):\n\treturn pos[0] >= 0 and pos[1] >= 0 and (pos[0] < n) and (pos[1] < n)\n\ndef moves(x, pair):\n\tmoves = []\n\t(a, b) = (pair[0], pair[1])\n\t(x1, x2) = (x[0], x[1])\n\tmoves.append((x1 + a, x2 + b))\n\tmoves.append((x1 + a, x2 - b))\n\tmoves.append((x1 - a, x2 + b))\n\tmoves.append((x1 - a, x2 - b))\n\tmoves.append((x1 + b, x2 + a))\n\tmoves.append((x1 + b, x2 - a))\n\tmoves.append((x1 - b, x2 + a))\n\tmoves.append((x1 - b, x2 - a))\n\treturn set(filter(validPos, moves))\n\ndef minPath(pair):\n\told_moves = [start]\n\tnew_moves = moves(start, pair)\n\tcount = 1\n\twhile len(new_moves) > 0 and end not in new_moves:\n\t\tcount += 1\n\t\tfor move in new_moves.copy():\n\t\t\tif move not in old_moves:\n\t\t\t\told_moves.append(move)\n\t\t\t\tnew_moves.remove(move)\n\t\t\t\tfor m in moves(move, pair):\n\t\t\t\t\tif m not in old_moves:\n\t\t\t\t\t\tnew_moves.add(m)\n\tif len(new_moves) == 0:\n\t\treturn -1\n\telse:\n\t\treturn count\nfor i in range(1, n):\n\tprint(*[minPath((i, j)) for j in range(1, n)], sep=' ')\n", "import sys\nn = int(input().strip())\ntarget = (n - 1, n - 1)\n\ndef knightL(x, y, n, target):\n\tv = 1\n\tpos = [(x, y, v), (x, y, v)]\n\tvisited = set([(0, 0)])\n\tfine = []\n\twhile pos != []:\n\t\ti = pos.pop(0)\n\t\tif i[:2] == target:\n\t\t\tfine.append(i[2])\n\t\tif i[:2] in visited:\n\t\t\tcontinue\n\t\tif i[0] + x < n and i[1] + y < n:\n\t\t\tpos.append((i[0] + x, i[1] + y, i[2] + 1))\n\t\tif i[0] + x < n and i[1] - y >= 0:\n\t\t\tpos.append((i[0] + x, i[1] - y, i[2] + 1))\n\t\tif i[0] - x >= 0 and i[1] + y < n:\n\t\t\tpos.append((i[0] - x, i[1] + y, i[2] + 1))\n\t\tif i[0] - x >= 0 and i[1] - y >= 0:\n\t\t\tpos.append((i[0] - x, i[1] - y, i[2] + 1))\n\t\tif i[0] + y < n and i[1] + x < n:\n\t\t\tpos.append((i[0] + y, i[1] + x, i[2] + 1))\n\t\tif i[0] + y < n and i[1] - x >= 0:\n\t\t\tpos.append((i[0] + y, i[1] - x, i[2] + 1))\n\t\tif i[0] - y >= 0 and i[1] + x < n:\n\t\t\tpos.append((i[0] - y, i[1] + x, i[2] + 1))\n\t\tif i[0] - y >= 0 and i[1] - x >= 0:\n\t\t\tpos.append((i[0] - y, i[1] - x, i[2] + 1))\n\t\tvisited.add(i[:2])\n\tif len(fine) > 0:\n\t\treturn min(fine)\n\telse:\n\t\treturn -1\nresults = []\nfor i in range(n - 1):\n\tresults.append([])\n\tfor j in range(n - 1):\n\t\tresults[i].append(0)\nfor i in range(1, n):\n\tfor j in range(i, n):\n\t\tresults[i - 1][j - 1] = results[j - 1][i - 1] = knightL(i, j, n, target)\nfor i in range(n - 1):\n\tfor j in range(n - 1):\n\t\tprint(results[i][j], end=' ')\n\tprint()\n", "import sys\no = int(input().strip())\nans = [[[4, 4, 2, 8], [4, 2, 4, 4], [2, 4, -1, -1], [8, 4, -1, 1]], [[5, 4, 3, 2, 5], [4, -1, 2, -1, -1], [3, 2, -1, -1, -1], [2, -1, -1, -1, -1], [5, -1, -1, -1, 1]], [[6, 4, 4, 8, 2, 12], [4, 3, 4, 2, 16, 3], [4, 4, 2, 4, 4, 4], [8, 2, 4, -1, -1, -1], [2, 16, 4, -1, -1, -1], [12, 3, 4, -1, -1, 1]], [[7, 6, 5, 6, 5, 2, 7], [6, -1, 6, -1, 2, -1, -1], [5, 6, -1, 2, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1], [5, 2, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1], [7, -1, -1, -1, -1, -1, 1]], [[8, 6, 4, 4, 6, 12, 2, 16], [6, 4, 6, 4, 8, 2, 8, 8], [4, 6, -1, 4, 2, -1, -1, -1], [4, 4, 4, 2, 4, 4, 4, 4], [6, 8, 2, 4, -1, -1, -1, -1], [12, 2, -1, 4, -1, -1, -1, -1], [2, 8, -1, 4, -1, -1, -1, -1], [16, 8, -1, 4, -1, -1, -1, 1]], [[9, 6, 5, 8, 5, 6, 7, 2, 9], [6, -1, 6, -1, 10, -1, 2, -1, -1], [5, 6, 3, 6, 7, 2, 13, -1, 3], [8, -1, 6, -1, 2, -1, -1, -1, -1], [5, 10, 7, 2, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1], [7, 2, 13, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1], [9, -1, 3, -1, -1, -1, -1, -1, 1]], [[10, 8, 6, 4, 4, 8, 6, 16, 2, 20], [8, 5, 4, 4, 4, 3, 8, 2, 28, 5], [6, 4, -1, 8, 4, -1, 2, 16, -1, -1], [4, 4, 8, -1, 4, 2, -1, -1, -1, -1], [4, 4, 4, 4, 2, 4, 4, 4, 4, 4], [8, 3, -1, 2, 4, -1, -1, -1, -1, -1], [6, 8, 2, -1, 4, -1, -1, -1, -1, -1], [16, 2, 16, -1, 4, -1, -1, -1, -1, -1], [2, 28, -1, -1, 4, -1, -1, -1, -1, -1], [20, 5, -1, -1, 4, -1, -1, -1, -1, 1]], [[11, 8, 7, 6, 7, 10, 7, 6, 9, 2, 11], [8, -1, 6, -1, 6, -1, 14, -1, 2, -1, -1], [7, 6, -1, 8, 7, -1, 7, 2, -1, -1, -1], [6, -1, 8, -1, 6, -1, 2, -1, -1, -1, -1], [7, 6, 7, 6, -1, 2, -1, -1, -1, -1, -1], [10, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1], [7, 14, 7, 2, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[12, 8, 6, 8, 4, 4, 8, 12, 6, 20, 2, 24], [8, 6, 6, 4, 10, 4, 12, 8, 12, 2, 12, 12], [6, 6, 4, 8, 6, 4, 8, 8, 2, 8, 8, 8], [8, 4, 8, 3, 8, 4, 12, 2, 36, 16, -1, 3], [4, 10, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4], [8, 12, 8, 12, 2, 4, -1, -1, -1, -1, -1, -1], [12, 8, 8, 2, -1, 4, -1, -1, -1, -1, -1, -1], [6, 12, 2, 36, -1, 4, -1, -1, -1, -1, -1, -1], [20, 2, 8, 16, -1, 4, -1, -1, -1, -1, -1, -1], [2, 12, 8, -1, -1, 4, -1, -1, -1, -1, -1, -1], [24, 12, 8, 3, -1, 4, -1, -1, -1, -1, -1, 1]], [[13, 10, 7, 6, 5, 12, 7, 10, 9, 6, 11, 2, 13], [10, -1, 6, -1, 6, -1, 6, -1, 18, -1, 2, -1, -1], [7, 6, -1, 6, 7, -1, 9, 14, -1, 2, -1, -1, -1], [6, -1, 6, -1, 10, -1, 10, -1, 2, -1, -1, -1, -1], [5, 6, 7, 10, -1, 6, 11, 2, -1, -1, -1, -1, -1], [12, -1, -1, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1], [7, 6, 9, 10, 11, 2, -1, -1, -1, -1, -1, -1, -1], [10, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 18, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[14, 10, 8, 8, 6, 4, 4, 8, 10, 16, 6, 24, 2, 28], [10, 7, 8, 6, 4, 5, 4, 6, 8, 5, 12, 2, 40, 7], [8, 8, -1, 4, 6, -1, 4, 16, -1, 8, 2, -1, -1, -1], [8, 6, 4, -1, 10, 6, 4, -1, 20, 2, 16, -1, -1, -1], [6, 4, 6, 10, -1, 8, 4, 12, 2, -1, -1, -1, -1, -1], [4, 5, -1, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4], [8, 6, 16, -1, 12, 2, 4, -1, -1, -1, -1, -1, -1, -1], [10, 8, -1, 20, 2, -1, 4, -1, -1, -1, -1, -1, -1, -1], [16, 5, 8, 2, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1], [6, 12, 2, 16, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1], [24, 2, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1], [2, 40, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1], [28, 7, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, 1]], [[15, 10, 9, 6, 7, 10, 9, 14, 9, 10, 11, 6, 13, 2, 15], [10, -1, 6, -1, 10, -1, 10, -1, 6, -1, 22, -1, 2, -1, -1], [9, 6, 5, 6, 5, 4, 7, 10, 3, 14, 13, 2, 23, -1, 5], [6, -1, 6, -1, 10, -1, 14, -1, 10, -1, 2, -1, -1, -1, -1], [7, 10, 5, 10, 3, 10, 9, 14, 13, 2, 23, -1, -1, -1, 3], [10, -1, 4, -1, 10, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1], [9, 10, 7, 14, 9, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1], [14, -1, 10, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 6, 3, 10, 13, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, 22, 13, 2, 23, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 2, 23, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [15, -1, 5, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[16, 12, 8, 8, 6, 8, 4, 4, 8, 12, 10, 20, 6, 28, 2, 32], [12, 8, 8, 6, 8, 4, 14, 4, 16, 6, 16, 12, 16, 2, 16, 16], [8, 8, -1, 8, 4, -1, 6, 4, -1, 20, 8, -1, 2, 28, -1, -1], [8, 6, 8, 4, 8, 6, 8, 4, 8, 8, 8, 2, 8, 8, 8, 8], [6, 8, 4, 8, -1, 12, 6, 4, 10, -1, 2, 68, 16, -1, -1, -1], [8, 4, -1, 6, 12, -1, 8, 4, -1, 2, -1, -1, -1, -1, -1, -1], [4, 14, 6, 8, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4], [8, 16, -1, 8, 10, -1, 2, 4, -1, -1, -1, -1, -1, -1, -1, -1], [12, 6, 20, 8, -1, 2, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1], [10, 16, 8, 8, 2, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1], [20, 12, -1, 2, 68, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1], [6, 16, 2, 8, 16, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1], [28, 2, 28, 8, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1], [2, 16, -1, 8, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1], [32, 16, -1, 8, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, 1]], [[17, 12, 9, 8, 7, 6, 7, 16, 9, 14, 11, 10, 13, 6, 15, 2, 17], [12, -1, 8, -1, 6, -1, 10, -1, 14, -1, 6, -1, 26, -1, 2, -1, -1], [9, 8, -1, 8, 5, -1, 9, 6, -1, 18, 13, -1, 13, 2, -1, -1, -1], [8, -1, 8, -1, 6, -1, 6, -1, 18, -1, 14, -1, 2, -1, -1, -1, -1], [7, 6, 5, 6, -1, 12, 11, 10, 9, -1, 13, 2, -1, -1, -1, -1, -1], [6, -1, -1, -1, 12, -1, 10, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1], [7, 10, 9, 6, 11, 10, -1, 6, 15, 2, -1, -1, -1, -1, -1, -1, -1], [16, -1, 6, -1, 10, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 14, -1, 18, 9, -1, 15, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, -1, 18, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, 6, 13, 14, 13, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 26, 13, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [15, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [17, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[18, 12, 10, 8, 6, 12, 8, 4, 4, 8, 12, 16, 10, 24, 6, 32, 2, 36], [12, 9, 8, 6, 8, 5, 4, 8, 4, 5, 8, 6, 12, 7, 16, 2, 52, 9], [10, 8, 6, 8, 6, 4, 6, 12, 4, 12, 12, 8, 12, 12, 2, 12, 12, 12], [8, 6, 8, -1, 4, 6, 14, -1, 4, 10, 20, -1, 8, 2, -1, -1, -1, -1], [6, 8, 6, 4, -1, 12, 8, 16, 4, -1, 10, 20, 2, 16, -1, -1, -1, -1], [12, 5, 4, 6, 12, 3, 12, 6, 4, 7, 24, 2, 56, 13, 16, -1, -1, 3], [8, 4, 6, 14, 8, 12, -1, 8, 4, 20, 2, -1, -1, -1, -1, -1, -1, -1], [4, 8, 12, -1, 16, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4], [8, 5, 12, 10, -1, 7, 20, 2, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [12, 8, 12, 20, 10, 24, 2, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [16, 6, 8, -1, 20, 2, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, 12, 12, 8, 2, 56, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [24, 7, 12, 2, 16, 13, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, 16, 2, -1, -1, 16, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [32, 2, 12, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, 52, 12, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1], [36, 9, 12, -1, -1, 3, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[19, 14, 11, 10, 7, 6, 7, 14, 11, 18, 11, 14, 13, 10, 15, 6, 17, 2, 19], [14, -1, 10, -1, 10, -1, 6, -1, 10, -1, 18, -1, 6, -1, 30, -1, 2, -1, -1], [11, 10, -1, 10, 7, -1, 7, 16, -1, 6, 11, -1, 15, 22, -1, 2, -1, -1, -1], [10, -1, 10, -1, 6, -1, 6, -1, 14, -1, 22, -1, 14, -1, 2, -1, -1, -1, -1], [7, 10, 7, 6, -1, 10, 11, 6, 13, -1, 13, 26, 17, 2, -1, -1, -1, -1, -1], [6, -1, -1, -1, 10, -1, 14, -1, -1, -1, 10, -1, 2, -1, -1, -1, -1, -1, -1], [7, 6, 7, 6, 11, 14, -1, 10, 13, 14, 17, 2, -1, -1, -1, -1, -1, -1, -1], [14, -1, 16, -1, 6, -1, 10, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [11, 10, -1, 14, 13, -1, 13, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [18, -1, 6, -1, -1, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, 18, 11, 22, 13, 10, 17, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, -1, -1, -1, 26, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 6, 15, 14, 17, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, -1, 22, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [15, 30, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [17, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [19, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[20, 14, 10, 8, 8, 12, 6, 8, 4, 4, 8, 12, 14, 20, 10, 28, 6, 36, 2, 40], [14, 10, 8, 8, 8, 6, 12, 4, 18, 4, 20, 8, 20, 6, 20, 16, 20, 2, 20, 20], [10, 8, -1, 8, 8, -1, 4, 12, -1, 4, 6, -1, 8, 28, -1, 12, 2, -1, -1, -1], [8, 8, 8, 5, 8, 4, 8, 4, 12, 4, 16, 3, 20, 8, 24, 2, 64, 28, -1, 5], [8, 8, 8, 8, 4, 8, 8, 8, 8, 4, 8, 8, 8, 8, 2, 8, 8, 8, 8, 8], [12, 6, -1, 4, 8, -1, 14, 8, -1, 4, 12, -1, 32, 2, -1, 16, -1, -1, -1, -1], [6, 12, 4, 8, 8, 14, -1, 12, 6, 4, 12, 12, 2, -1, -1, -1, -1, -1, -1, -1], [8, 4, 12, 4, 8, 8, 12, -1, 8, 4, 20, 2, -1, -1, -1, -1, -1, -1, -1, -1], [4, 18, -1, 12, 8, -1, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [8, 20, 6, 16, 8, 12, 12, 20, 2, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [12, 8, -1, 3, 8, -1, 12, 2, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, 20, 8, 20, 8, 32, 2, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [20, 6, 28, 8, 8, 2, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, 20, -1, 24, 2, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [28, 16, 12, 2, 8, 16, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, 20, 2, 64, 8, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [36, 2, -1, 28, 8, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, 20, -1, -1, 8, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [40, 20, -1, 5, 8, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[21, 14, 11, 10, 9, 6, 9, 10, 9, 20, 11, 18, 13, 14, 15, 10, 17, 6, 19, 2, 21], [14, -1, 10, -1, 6, -1, 14, -1, 10, -1, 10, -1, 22, -1, 6, -1, 34, -1, 2, -1, -1], [11, 10, 7, 6, 9, 6, 7, 6, 5, 10, 11, 6, 13, 18, 5, 22, 19, 2, 33, -1, 7], [10, -1, 6, -1, 10, -1, 14, -1, 6, -1, 10, -1, 26, -1, 18, -1, 2, -1, -1, -1, -1], [9, 6, 9, 10, -1, 6, 9, 16, 9, -1, 15, 10, 15, 14, -1, 2, -1, -1, -1, -1, -1], [6, -1, 6, -1, 6, -1, 14, -1, 6, -1, 18, -1, 10, -1, 2, -1, -1, -1, -1, -1, -1], [9, 14, 7, 14, 9, 14, 3, 14, 13, 18, 15, 22, 19, 2, 33, -1, -1, -1, -1, -1, 3], [10, -1, 6, -1, 16, -1, 14, -1, 10, -1, 22, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 10, 5, 6, 9, 6, 13, 10, -1, 6, 19, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [20, -1, 10, -1, -1, -1, 18, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, 10, 11, 10, 15, 18, 15, 22, 19, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [18, -1, 6, -1, 10, -1, 22, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 22, 13, 26, 15, 10, 19, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, -1, 18, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [15, 6, 5, 18, -1, 2, 33, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, -1, 22, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [17, 34, 19, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [19, 2, 33, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [21, -1, 7, -1, -1, -1, 3, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[22, 16, 12, 10, 8, 8, 6, 12, 8, 4, 4, 8, 12, 16, 14, 24, 10, 32, 6, 40, 2, 44], [16, 11, 10, 8, 10, 7, 8, 6, 4, 7, 4, 10, 8, 7, 12, 6, 16, 9, 20, 2, 64, 11], [12, 10, -1, 8, 8, -1, 8, 4, -1, 16, 4, -1, 6, 8, -1, 32, 12, -1, 2, 40, -1, -1], [10, 8, 8, -1, 10, 6, 4, -1, 18, 6, 4, -1, 24, 14, 8, -1, 32, 2, 28, -1, -1, -1], [8, 10, 8, 10, -1, 4, 6, 8, 6, -1, 4, 24, 14, 20, -1, 8, 2, -1, -1, -1, -1, -1], [8, 7, -1, 6, 4, -1, 12, 8, -1, 7, 4, -1, 20, 7, -1, 2, 16, -1, -1, -1, -1, -1], [6, 8, 8, 4, 6, 12, -1, 16, 8, 12, 4, 20, 10, -1, 2, 36, -1, 16, -1, -1, -1, -1], [12, 6, 4, -1, 8, 8, 16, -1, 12, 6, 4, -1, 12, 2, -1, -1, -1, -1, -1, -1, -1, -1], [8, 4, -1, 18, 6, -1, 8, 12, -1, 8, 4, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [4, 7, 16, 6, -1, 7, 12, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [8, 10, -1, -1, 24, -1, 20, -1, -1, 2, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [12, 8, 6, 24, 14, 20, 10, 12, 2, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [16, 7, 8, 14, 20, 7, -1, 2, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, 12, -1, 8, -1, -1, 2, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [24, 6, 32, -1, 8, 2, 36, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, 16, 12, 32, 2, 16, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [32, 9, -1, 2, -1, -1, 16, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, 20, 2, 28, -1, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [40, 2, 40, -1, -1, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, 64, -1, -1, -1, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [44, 11, -1, -1, -1, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[23, 16, 13, 10, 9, 10, 9, 6, 9, 18, 13, 22, 13, 18, 15, 14, 17, 10, 19, 6, 21, 2, 23], [16, -1, 10, -1, 10, -1, 6, -1, 14, -1, 14, -1, 10, -1, 26, -1, 6, -1, 38, -1, 2, -1, -1], [13, 10, -1, 10, 7, -1, 9, 10, -1, 20, 11, -1, 13, 6, -1, 26, 19, -1, 19, 2, -1, -1, -1], [10, -1, 10, -1, 10, -1, 10, -1, 6, -1, 6, -1, 18, -1, 30, -1, 18, -1, 2, -1, -1, -1, -1], [9, 10, 7, 10, -1, 6, 7, 6, 13, -1, 11, 14, 17, 26, -1, 14, 21, 2, -1, -1, -1, -1, -1], [10, -1, -1, -1, 6, -1, 10, -1, -1, -1, 22, -1, 18, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1], [9, 6, 9, 10, 7, 10, -1, 16, 15, 6, 11, 10, 15, -1, 19, 2, 55, -1, -1, -1, -1, -1, -1], [6, -1, 10, -1, 6, -1, 16, -1, 14, -1, 14, -1, 22, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 14, -1, 6, 13, -1, 15, 14, -1, 10, 17, -1, 17, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [18, -1, 20, -1, -1, -1, 6, -1, 10, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 14, 11, 6, 11, 22, 11, 14, 17, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [22, -1, -1, -1, 14, -1, 10, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 10, 13, 18, 17, 18, 15, 22, 17, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [18, -1, 6, -1, 26, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [15, 26, -1, 30, -1, -1, 19, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, -1, 26, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [17, 6, 19, 18, 21, 2, 55, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, -1, -1, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [19, 38, 19, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [21, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [23, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[24, 16, 12, 12, 8, 8, 6, 16, 10, 8, 4, 4, 8, 12, 16, 20, 14, 28, 10, 36, 6, 44, 2, 48], [16, 12, 12, 8, 8, 6, 8, 8, 16, 4, 22, 4, 24, 8, 24, 12, 24, 6, 24, 20, 24, 2, 24, 24], [12, 12, 8, 8, 6, 6, 6, 16, 4, 16, 10, 4, 14, 16, 6, 16, 16, 12, 16, 16, 2, 16, 16, 16], [12, 8, 8, 6, 12, 6, 12, 4, 12, 10, 12, 4, 12, 12, 12, 8, 12, 12, 12, 2, 12, 12, 12, 12], [8, 8, 6, 12, -1, 8, 4, 16, 6, -1, 12, 4, 10, 28, -1, 20, 8, 24, 2, -1, -1, -1, -1, -1], [8, 6, 6, 6, 8, 4, 8, 8, 6, 6, 8, 4, 8, 8, 8, 8, 8, 2, 8, 8, 8, 8, 8, 8], [6, 8, 6, 12, 4, 8, -1, 16, 10, 20, 10, 4, 12, -1, 10, 20, 2, -1, 16, -1, -1, -1, -1, -1], [16, 8, 16, 4, 16, 8, 16, 3, 16, 8, 20, 4, 24, 12, 36, 2, 76, 36, -1, 16, -1, -1, -1, 3], [10, 16, 4, 12, 6, 6, 10, 16, -1, 12, 6, 4, 14, 32, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [8, 4, 16, 10, -1, 6, 20, 8, 12, -1, 8, 4, 24, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [4, 22, 10, 12, 12, 8, 10, 20, 6, 8, -1, 4, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 2, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4, 4], [8, 24, 14, 12, 10, 8, 12, 24, 14, 24, 2, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [12, 8, 16, 12, 28, 8, -1, 12, 32, 2, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [16, 24, 6, 12, -1, 8, 10, 36, 2, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [20, 12, 16, 8, 20, 8, 20, 2, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, 24, 16, 12, 8, 8, 2, 76, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [28, 6, 12, 12, 24, 2, -1, 36, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, 24, 16, 12, 2, 8, 16, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [36, 20, 16, 2, -1, 8, -1, 16, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, 24, 2, 12, -1, 8, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [44, 2, 16, 12, -1, 8, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, 24, 16, 12, -1, 8, -1, -1, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [48, 24, 16, 12, -1, 8, -1, 3, -1, -1, -1, 4, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]], [[25, 18, 13, 10, 9, 12, 7, 6, 9, 14, 11, 24, 13, 22, 15, 18, 17, 14, 19, 10, 21, 6, 23, 2, 25], [18, -1, 10, -1, 10, -1, 14, -1, 6, -1, 14, -1, 18, -1, 10, -1, 30, -1, 6, -1, 42, -1, 2, -1, -1], [13, 10, -1, 8, 7, -1, 7, 14, -1, 10, 13, -1, 13, 26, -1, 6, 17, -1, 21, 30, -1, 2, -1, -1, -1], [10, -1, 8, -1, 10, -1, 6, -1, 14, -1, 18, -1, 6, -1, 14, -1, 34, -1, 22, -1, 2, -1, -1, -1, -1], [9, 10, 7, 10, 5, 10, 7, 10, 9, 4, 11, 18, 13, 22, 3, 26, 19, 30, 23, 2, 41, -1, -1, -1, 5], [12, -1, -1, -1, 10, -1, 6, -1, -1, -1, 14, -1, 26, -1, -1, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1], [7, 14, 7, 6, 7, 6, -1, 14, 15, 10, 17, 14, 15, -1, 19, 38, 21, 2, -1, -1, -1, -1, -1, -1, -1], [6, -1, 14, -1, 10, -1, 14, -1, 18, -1, 6, -1, 14, -1, 10, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1], [9, 6, -1, 14, 9, -1, 15, 18, -1, 14, 15, -1, 17, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, -1, 10, -1, 4, -1, 10, -1, 14, -1, 10, -1, 22, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [11, 14, 13, 18, 11, 14, 17, 6, 15, 10, -1, 6, 23, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [24, -1, -1, -1, 18, -1, 14, -1, -1, -1, 6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [13, 18, 13, 6, 13, 26, 15, 14, 17, 22, 23, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [22, -1, 26, -1, 22, -1, -1, -1, 14, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [15, 10, -1, 14, 3, -1, 19, 10, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [18, -1, 6, -1, 26, -1, 38, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [17, 30, 17, 34, 19, 14, 21, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [14, -1, -1, -1, 30, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [19, 6, 21, 22, 23, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [10, -1, 30, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [21, 42, -1, 2, 41, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [6, -1, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [23, 2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [2, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1], [25, -1, -1, -1, 5, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 1]]]\nfor i in range(0, o - 1):\n\tfor j in range(0, o - 1):\n\t\tprint(ans[o - 5][i][j], end=' ')\n\tprint('')\n", "from collections import deque\n\ndef _neighbor(a, b, pos):\n\t(x, y) = pos\n\tfor i in [-a, a]:\n\t\tfor j in [-b, b]:\n\t\t\tyield (x + i, y + j)\n\t\t\tyield (x + j, y + i)\n\ndef inbounds(pos, n):\n\t(x, y) = pos\n\treturn 0 <= x < n and 0 <= y < n\n\ndef neighbor(a, b, pos, n):\n\tfor newpos in _neighbor(a, b, pos):\n\t\tif inbounds(newpos, n):\n\t\t\tyield newpos\n\ndef find_path_length(a, b, n):\n\tq = deque()\n\tparent_of = dict()\n\tq.append((0, 0))\n\twhile q:\n\t\tv = q.popleft()\n\t\tif v == (n - 1, n - 1):\n\t\t\tbreak\n\t\tfor u in neighbor(a, b, v, n):\n\t\t\tif u not in parent_of:\n\t\t\t\tparent_of[u] = v\n\t\t\t\tq.append(u)\n\tlength = -1\n\tv = (n - 1, n - 1)\n\twhile v != (0, 0) and v in parent_of:\n\t\tlength += 1\n\t\tv = parent_of[v]\n\treturn length + 1 if length != -1 else -1\n\ndef solve():\n\tn = int(input())\n\tout = [[0] * n for i in range(n)]\n\tfor a in range(1, n):\n\t\tfor b in range(a, n):\n\t\t\tout[a][b] = find_path_length(a, b, n)\n\t\t\tout[b][a] = out[a][b]\n\tfor a in range(1, n):\n\t\tfor b in range(1, n):\n\t\t\tprint(out[a][b], end=' ')\n\t\tprint()\nsolve()\n", "import sys\nn = int(input().strip())\n\ndef twoIntToString(i1, i2):\n\treturn str(i1) + ',' + str(i2)\n\ndef stringToTwo(couple):\n\treturn list(map(int, couple.split(',')))\n\ndef nextSquares(x, y, a, b, n):\n\tvalidSquares = []\n\tif x + a < n and y + b < n:\n\t\tvalidSquares.append(twoIntToString(x + a, y + b))\n\tif x + b < n and y + a < n:\n\t\tvalidSquares.append(twoIntToString(x + b, y + a))\n\tif x + a < n and y - b >= 0:\n\t\tvalidSquares.append(twoIntToString(x + a, y - b))\n\tif x + b < n and y - a >= 0:\n\t\tvalidSquares.append(twoIntToString(x + b, y - a))\n\tif x - a >= 0 and y - b >= 0:\n\t\tvalidSquares.append(twoIntToString(x - a, y - b))\n\tif x - b >= 0 and y - a >= 0:\n\t\tvalidSquares.append(twoIntToString(x - b, y - a))\n\tif x - a >= 0 and y + b < n:\n\t\tvalidSquares.append(twoIntToString(x - a, y + b))\n\tif x - b >= 0 and y + a < n:\n\t\tvalidSquares.append(twoIntToString(x - b, y + a))\n\treturn validSquares\nres = ''\nfor a in range(1, n):\n\tfor b in range(1, n):\n\t\tsquareValue = {'0,0': 0}\n\t\tsquareToVisit = ['0,0']\n\t\ttemp = []\n\t\tgiro = 1\n\t\twhile True:\n\t\t\tsquareToVisit = list(map(stringToTwo, squareToVisit))\n\t\t\tfor couple in squareToVisit:\n\t\t\t\tvalidSquares = nextSquares(couple[0], couple[1], a, b, n)\n\t\t\t\tfor square in validSquares:\n\t\t\t\t\tif square not in squareValue:\n\t\t\t\t\t\tsquareValue[square] = giro\n\t\t\t\t\t\ttemp.append(square)\n\t\t\tsquareToVisit = temp\n\t\t\ttemp = []\n\t\t\tgiro += 1\n\t\t\tif str(n - 1) + ',' + str(n - 1) in squareValue:\n\t\t\t\tres += str(squareValue[str(n - 1) + ',' + str(n - 1)]) + ' '\n\t\t\t\tbreak\n\t\t\tif squareToVisit == []:\n\t\t\t\tres += str(-1) + ' '\n\t\t\t\tbreak\n\tprint(res)\n\tres = ''\n", "import sys\n\ndef valid_move_combine(start, dpos, n):\n\tend = (start[0] + dpos[0], start[1] + dpos[1])\n\tif end[0] >= 0 and end[0] < n and (end[1] >= 0) and (end[1] < n):\n\t\treturn end\n\telse:\n\t\treturn None\n\ndef KnightL(a, b, n):\n\thalfMoves = [(a, b), (-a, b), (a, -b), (-a, -b)]\n\tmoves = halfMoves + [(y, x) for (x, y) in halfMoves]\n\tmoves = set(moves)\n\tQ = []\n\tstart = (0, 0)\n\tend = (n - 1, n - 1)\n\tQ.append([start])\n\tvisited = set()\n\twhile Q:\n\t\tpath = Q.pop(0)\n\t\tnode = path[-1]\n\t\tif node == end:\n\t\t\treturn path\n\t\tif node not in visited:\n\t\t\tvisited.add(node)\n\t\t\tfor dpos in moves:\n\t\t\t\tadj = valid_move_combine(node, dpos, n)\n\t\t\t\tif adj:\n\t\t\t\t\tQ.append(path + [adj])\n\treturn None\nn = int(input().strip())\nfor a in range(1, n):\n\tres = []\n\tfor b in range(1, n):\n\t\ttemp = KnightL(a, b, n)\n\t\tif temp:\n\t\t\tres.append(len(temp) - 1)\n\t\telse:\n\t\t\tres.append(-1)\n\tprint(*res, sep=' ')\n", "n = int(input().strip())\ne = n ** 2 - 1\n\ndef moves(s, a, b, n):\n\tc = set()\n\t(xs, ys) = (s % n, s // n)\n\tm = [(xs + a, ys + b), (xs + a, ys - b), (xs - a, ys + b), (xs - a, ys - b), (xs + b, ys + a), (xs + b, ys - a), (xs - b, ys + a), (xs - b, ys - a)]\n\tfor (x, y) in m:\n\t\tif 0 <= x < n and 0 <= y < n:\n\t\t\tc |= {x + n * y}\n\treturn c\n\ndef explore(g, s, a, b, n):\n\tif s not in g:\n\t\tm = moves(s, a, b, n)\n\t\tg[s] = m\n\t\tfor c in m:\n\t\t\texplore(g, c, a, b, n)\n\ndef dijkstra(g, s):\n\tq = list(g.keys())\n\td = {k: len(q) for k in q}\n\td[s] = 0\n\tp = {k: None for k in q}\n\twhile q != []:\n\t\tqd = sorted([(n, d[n]) for n in q], key=lambda x: x[1])\n\t\t(u, du) = qd[0]\n\t\tq.remove(u)\n\t\tfor v in g[u]:\n\t\t\tif v in q:\n\t\t\t\tdv = du + 1\n\t\t\t\tif dv < d[v]:\n\t\t\t\t\td[v] = dv\n\t\t\t\t\tp[v] = u\n\treturn (d, p)\n\ndef route(p, e):\n\tpath = []\n\tu = e\n\twhile p[u] is not None:\n\t\tpath.insert(0, u)\n\t\tu = p[u]\n\tpath.insert(0, u)\n\treturn path\nfor a in range(1, n):\n\tfor b in range(1, n):\n\t\tg = {}\n\t\texplore(g, 0, a, b, n)\n\t\tif e not in g:\n\t\t\tr = -1\n\t\telse:\n\t\t\t(d, p) = dijkstra(g, 0)\n\t\t\tr = len(route(p, e)) - 1\n\t\tprint(r, end=' ')\n\tprint()\n", "import sys\nfrom queue import Queue\n\ndef next_valid_cells(visited, x, y, a_delta, b_delta, n):\n\tvalid_cells = []\n\tup = x - a_delta\n\tdown = x + a_delta\n\tleft = y - b_delta\n\tright = y + b_delta\n\tif (up >= 0 and left >= 0) and (up, left) not in visited:\n\t\tvalid_cells.append((up, left))\n\t\tvisited.add((up, left))\n\tif (up >= 0 and right < n) and (up, right) not in visited:\n\t\tvalid_cells.append((up, right))\n\t\tvisited.add((up, right))\n\tif (down < n and left >= 0) and (down, left) not in visited:\n\t\tvalid_cells.append((down, left))\n\t\tvisited.add((down, left))\n\tif (down < n and right < n) and (down, right) not in visited:\n\t\tvalid_cells.append((down, right))\n\t\tvisited.add((down, right))\n\treturn valid_cells\n\ndef breadth_first_search(a_delta, b_delta, n):\n\tvisited = set()\n\tq = Queue()\n\tq.put([(0, 0), 0])\n\twhile q.empty() == False:\n\t\t((curr_x, curr_y), depth) = q.get()\n\t\tif curr_x == n - 1 and curr_y == n - 1:\n\t\t\treturn depth\n\t\tnext_cells = next_valid_cells(visited, curr_x, curr_y, a_delta, b_delta, n)\n\t\tnext_cells += next_valid_cells(visited, curr_x, curr_y, b_delta, a_delta, n)\n\t\tfor cell in next_cells:\n\t\t\tif cell == (n - 1, n - 1):\n\t\t\t\treturn depth + 1\n\t\t\tq.put([cell, depth + 1])\n\treturn -1\n\ndef main():\n\tn = int(input().strip())\n\tfinal_result = [['-1'] * (n - 1) for _ in range(n - 1)]\n\tfor outer in range(1, n):\n\t\tfor inner in range(outer, n):\n\t\t\tif inner == 1 and outer == 1:\n\t\t\t\tfinal_result[0][0] = str(n - 1)\n\t\t\telif inner == n - 1 and outer == n - 1:\n\t\t\t\tfinal_result[inner - 1][outer - 1] = '1'\n\t\t\telse:\n\t\t\t\tr = str(breadth_first_search(outer, inner, n))\n\t\t\t\tfinal_result[inner - 1][outer - 1] = r\n\t\t\t\tfinal_result[outer - 1][inner - 1] = r\n\tfor row in final_result:\n\t\tprint(' '.join(row))\nmain()\n", "import sys\ndisplay = False\n\ndef getChoices(curr, a, b, n1):\n\tif display:\n\t\tprint('bgn getChoices curr:', curr)\n\tresult = set()\n\tlimits = range(n1 + 1)\n\t(x, y) = (curr // 30, curr % 30)\n\t(al, bl) = ([a, a, -a, -a, b, b, -b, -b], [b, -b, b, -b, a, -a, a, -a])\n\txn = [i + x if i + x in limits else -99 for i in al]\n\tyn = [i + y if i + y in limits else -99 for i in bl]\n\tresult = {30 * xn[i] + yn[i] for i in range(8) if xn[i] in limits and yn[i] in limits}\n\tif display:\n\t\tprint('end getChoices result:', result)\n\treturn result\n\ndef mincalc(a, b, n1):\n\tif display:\n\t\tprint('bgn mincalc a:', a, ' b:', b, ' n1:', n1)\n\tresult = 0\n\ttarget = 31 * n1\n\tfound = False\n\tmoves = set()\n\tchoices = {0}\n\twhile len(choices - moves) and (not found):\n\t\tchoices -= moves\n\t\tif display:\n\t\t\tprint('moves:', *moves)\n\t\t\tprint('choices:', *choices)\n\t\tnxtchoices = set()\n\t\tfor choice in choices:\n\t\t\tmoves.add(choice)\n\t\t\tnxtchoices = nxtchoices | getChoices(choice, a, b, n1)\n\t\t\tif target in nxtchoices:\n\t\t\t\tfound = True\n\t\t\t\tbreak\n\t\tresult += 1\n\t\tchoices = nxtchoices\n\t\tif display:\n\t\t\tprint('nxtchoices:', *choices)\n\tif not found:\n\t\tresult = -1\n\tif display:\n\t\tprint('end mincalc result:', result)\n\treturn result\nn = int(input().strip())\nn1 = n - 1\nmx = [[0 for x in range(n1)] for y in range(n1)]\nfor i in range(n1):\n\tfor j in range(i, n1):\n\t\tif False and i == 1 and (j == 9):\n\t\t\tdisplay = True\n\t\telse:\n\t\t\tdisplay = False\n\t\tmx[i][j] = mincalc(i + 1, j + 1, n1)\nfor i in range(n1):\n\tfor j in range(0, i):\n\t\tmx[i][j] = mx[j][i]\nfor row in mx:\n\tfor cell in row:\n\t\tprint(cell, end=' ')\n\tprint()\n", "import sys\nn = int(input().strip())\n\ndef find_reachable_squares(x, y, a, b, n):\n\tsquares = set()\n\tif x + a >= 0 and x + a < n:\n\t\tif y + b >= 0 and y + b < n:\n\t\t\tsquares.add((x + a, y + b))\n\t\tif y - b >= 0 and y - b < n:\n\t\t\tsquares.add((x + a, y - b))\n\tif x - a >= 0 and x - a < n:\n\t\tif y + b >= 0 and y + b < n:\n\t\t\tsquares.add((x - a, y + b))\n\t\tif y - b >= 0 and y - b < n:\n\t\t\tsquares.add((x - a, y - b))\n\tif x + b >= 0 and x + b < n:\n\t\tif y + a >= 0 and y + a < n:\n\t\t\tsquares.add((x + b, y + a))\n\t\tif y - a >= 0 and y - a < n:\n\t\t\tsquares.add((x + b, y - a))\n\tif x - b >= 0 and x - b < n:\n\t\tif y + a >= 0 and y + a < n:\n\t\t\tsquares.add((x - b, y + a))\n\t\tif y - a >= 0 and y - a < n:\n\t\t\tsquares.add((x - b, y - a))\n\treturn squares\nmatrix = [[0 for x in range(n - 1)] for y in range(n - 1)]\nfor i in range(1, n):\n\tfor j in range(i, n):\n\t\treachable_squares = set([(n - 1, n - 1)])\n\t\tprevious_squares = set([(n - 1, n - 1)])\n\t\thistory_sq = set([(n - 1, n - 1)])\n\t\tcount = 0\n\t\twhile len(reachable_squares) > 0 and (0, 0) not in history_sq:\n\t\t\treachable_squares = set()\n\t\t\tcount = count + 1\n\t\t\tfor s in previous_squares:\n\t\t\t\treachable_squares = reachable_squares | find_reachable_squares(s[0], s[1], i, j, n)\n\t\t\treachable_squares = reachable_squares - history_sq\n\t\t\tprevious_squares = set()\n\t\t\tfor s in reachable_squares:\n\t\t\t\tprevious_squares.add(s)\n\t\t\t\thistory_sq.add(s)\n\t\tval = -1\n\t\tif (0, 0) in history_sq:\n\t\t\tval = count\n\t\tmatrix[i - 1][j - 1] = val\n\t\tmatrix[j - 1][i - 1] = val\nfor i in matrix:\n\tstring = ''\n\tfor j in i:\n\t\tstring = string + ' ' + str(j)\n\tprint(string[1:])\n", "import sys\nfrom collections import deque\nn = int(input().strip())\nfor i in range(1, n):\n\tcurans = []\n\tfor j in range(1, n):\n\t\tgoal = False\n\t\tdi = {(0, 0): 0}\n\t\tvalid = False\n\t\tq = deque()\n\t\tq.append((0, 0))\n\t\ttried = set()\n\t\twhile not goal:\n\t\t\tvalid = False\n\t\t\ttemp = q.popleft()\n\t\t\tif temp[0] - i >= 0:\n\t\t\t\tif temp[1] - j >= 0:\n\t\t\t\t\tif (temp[0] - i, temp[1] - j) not in tried:\n\t\t\t\t\t\tq.append((temp[0] - i, temp[1] - j))\n\t\t\t\t\t\ttried.add((temp[0] - i, temp[1] - j))\n\t\t\t\t\t\tdi[temp[0] - i, temp[1] - j] = di[temp] + 1\n\t\t\t\tif temp[1] + j <= n - 1:\n\t\t\t\t\tif (temp[0] - i, temp[1] + j) not in tried:\n\t\t\t\t\t\tq.append((temp[0] - i, temp[1] + j))\n\t\t\t\t\t\ttried.add((temp[0] - i, temp[1] + j))\n\t\t\t\t\t\tdi[temp[0] - i, temp[1] + j] = di[temp] + 1\n\t\t\tif temp[0] + i <= n - 1:\n\t\t\t\tif temp[1] - j >= 0:\n\t\t\t\t\tif (temp[0] + i, temp[1] - j) not in tried:\n\t\t\t\t\t\tq.append((temp[0] + i, temp[1] - j))\n\t\t\t\t\t\ttried.add((temp[0] + i, temp[1] - j))\n\t\t\t\t\t\tdi[temp[0] + i, temp[1] - j] = di[temp] + 1\n\t\t\t\tif temp[1] + j <= n - 1:\n\t\t\t\t\tif (temp[0] + i, temp[1] + j) not in tried:\n\t\t\t\t\t\tq.append((temp[0] + i, temp[1] + j))\n\t\t\t\t\t\ttried.add((temp[0] + i, temp[1] + j))\n\t\t\t\t\t\tdi[temp[0] + i, temp[1] + j] = di[temp] + 1\n\t\t\tif temp[0] - j >= 0:\n\t\t\t\tif temp[1] - i >= 0:\n\t\t\t\t\tif (temp[0] - j, temp[1] - i) not in tried:\n\t\t\t\t\t\tq.append((temp[0] - j, temp[1] - i))\n\t\t\t\t\t\ttried.add((temp[0] - j, temp[1] - i))\n\t\t\t\t\t\tdi[temp[0] - j, temp[1] - i] = di[temp] + 1\n\t\t\t\tif temp[1] + i <= n - 1:\n\t\t\t\t\tif (temp[0] - j, temp[1] + i) not in tried:\n\t\t\t\t\t\tq.append((temp[0] - j, temp[1] + i))\n\t\t\t\t\t\ttried.add((temp[0] - j, temp[1] + i))\n\t\t\t\t\t\tdi[temp[0] - j, temp[1] + i] = di[temp] + 1\n\t\t\tif temp[0] + j <= n - 1:\n\t\t\t\tif temp[1] - i >= 0:\n\t\t\t\t\tif (temp[0] + j, temp[1] - i) not in tried:\n\t\t\t\t\t\tq.append((temp[0] + j, temp[1] - i))\n\t\t\t\t\t\ttried.add((temp[0] + j, temp[1] - i))\n\t\t\t\t\t\tdi[temp[0] + j, temp[1] - i] = di[temp] + 1\n\t\t\t\tif temp[1] + i <= n - 1:\n\t\t\t\t\tif (temp[0] + j, temp[1] + i) not in tried:\n\t\t\t\t\t\tq.append((temp[0] + j, temp[1] + i))\n\t\t\t\t\t\ttried.add((temp[0] + j, temp[1] + i))\n\t\t\t\t\t\tdi[temp[0] + j, temp[1] + i] = di[temp] + 1\n\t\t\tif (n - 1, n - 1) in di:\n\t\t\t\tgoal = True\n\t\t\t\tcurans.append(di[n - 1, n - 1])\n\t\t\tif len(q) == 0:\n\t\t\t\tgoal = True\n\t\t\t\tcurans.append(-1)\n\tfor l in range(len(curans)):\n\t\tprint(str(curans[l]) + ' ', end='')\n\tprint('')\n", "import sys\nfrom collections import deque\nn = int(input().strip())\n\ndef find(n, i, j):\n\tvisited = {}\n\tvisited[0, 0] = 0\n\tpath = deque()\n\tpath.append((0, 0))\n\twhile len(path) != 0:\n\t\tcell = path.pop()\n\t\tcoefs = [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (-j, i), (j, -i), (-j, -i)]\n\t\tif cell[0] + i == n - 1 and cell[1] + j == n - 1 or (cell[0] + j == n - 1 and cell[1] + i == n - 1):\n\t\t\treturn visited[cell] + 1\n\t\tfor (a, b) in coefs:\n\t\t\ttmp = (cell[0] + a, cell[1] + b)\n\t\t\tif tmp[0] >= 0 and tmp[0] < n and (tmp[1] >= 0) and (tmp[1] < n) and (not tmp in visited):\n\t\t\t\tpath.appendleft(tmp)\n\t\t\t\tvisited[tmp] = visited[cell] + 1\n\treturn -1\nanswer = []\nfor i in range(n - 1):\n\tanswer.append([])\n\tfor j in range(n - 1):\n\t\tanswer[i].append(0)\nfor i in range(1, n):\n\tfor j in range(i, n):\n\t\tanswer[i - 1][j - 1] = find(n, i, j)\n\t\tanswer[j - 1][i - 1] = answer[i - 1][j - 1]\nfor i in range(0, n - 1):\n\tfor j in range(0, n - 1):\n\t\tprint(answer[i][j], end=' ')\n\tprint()\n", "import sys\n\ndef make_act_set(a, b):\n\tactset = []\n\tactset.append([a, b])\n\tactset.append([-a, b])\n\tactset.append([a, -b])\n\tactset.append([-a, -b])\n\tactset.append([b, a])\n\tactset.append([-b, a])\n\tactset.append([b, -a])\n\tactset.append([-b, -a])\n\treturn actset\n\ndef make_xy_set(N):\n\txyset = []\n\tfor x in range(N):\n\t\tfor y in range(N):\n\t\t\txyset.append([x, y])\n\txyset.remove([0, 0])\n\treturn xyset\n\ndef take_step(cur_xy_list, actset, xyset, N):\n\tnew_xy_list = []\n\tfor curxy in cur_xy_list:\n\t\tfor act in actset:\n\t\t\tnew_xy = [i for i in curxy]\n\t\t\tnew_xy[0] += act[0]\n\t\t\tnew_xy[1] += act[1]\n\t\t\tif new_xy in xyset:\n\t\t\t\tnew_xy_list.append(new_xy)\n\t\t\t\txyset.remove(new_xy)\n\t\tif not [N - 1, N - 1] in xyset:\n\t\t\tbreak\n\treturn (new_xy_list, xyset)\n\ndef find_sol(N, index_pair):\n\txyset = make_xy_set(N)\n\tactset = make_act_set(index_pair[0], index_pair[1])\n\tstep = 0\n\tcur_xy_list = [[0, 0]]\n\twhile 1:\n\t\t(cur_xy_list, xyset) = take_step(cur_xy_list, actset, xyset, N)\n\t\tstep += 1\n\t\tif len(cur_xy_list) == 0:\n\t\t\tstep = -1\n\t\t\tbreak\n\t\telif not [N - 1, N - 1] in xyset:\n\t\t\tbreak\n\treturn step\nN = int(input().strip())\nsol = []\nfor loof in range(N - 1):\n\tsol.append([0 for i in range(N - 1)])\nfor row in range(N - 1):\n\tfor col in range(N - 1):\n\t\tif row > col:\n\t\t\tsol[row][col] = sol[col][row]\n\t\telse:\n\t\t\tsol[row][col] = find_sol(N, [row + 1, col + 1])\nfor i in range(N - 1):\n\tfor j in range(N - 1):\n\t\tif j < N - 2:\n\t\t\tprint(sol[i][j], end=' ')\n\t\telse:\n\t\t\tprint(sol[i][j])\n", "import sys\nimport queue\n\ndef valid(x, y, n, visited):\n\treturn x >= 0 and x < n and (y >= 0) and (y < n) and (visited[x][y] == 0)\nn = int(input().strip())\nsolution = {}\nfor a in range(1, n):\n\tfor b in range(1, n):\n\t\tif (b, a) in solution:\n\t\t\tsolution[a, b] = solution[b, a]\n\t\telse:\n\t\t\tvisited = [[0 for _ in range(n)] for _ in range(n)]\n\t\t\tQ = queue.Queue()\n\t\t\tQ.put([0, 0, 0])\n\t\t\tvisited[0][0] = 1\n\t\t\tfound = False\n\t\t\twhile not Q.empty():\n\t\t\t\t(x, y, s) = Q.get()\n\t\t\t\tif x == n - 1 and y == n - 1:\n\t\t\t\t\tfound = True\n\t\t\t\t\tsolution[a, b] = s\n\t\t\t\t\tbreak\n\t\t\t\tfor p in range(-1, 2, 2):\n\t\t\t\t\tfor q in range(-1, 2, 2):\n\t\t\t\t\t\tif valid(x + p * a, y + q * b, n, visited):\n\t\t\t\t\t\t\tQ.put([x + p * a, y + q * b, s + 1])\n\t\t\t\t\t\t\tvisited[x + p * a][y + q * b] = 1\n\t\t\t\t\t\tif valid(x + p * b, y + q * a, n, visited):\n\t\t\t\t\t\t\tQ.put([x + p * b, y + q * a, s + 1])\n\t\t\t\t\t\t\tvisited[x + p * b][y + q * a] = 1\n\t\t\tif not found:\n\t\t\t\tsolution[a, b] = -1\nfor a in range(1, n):\n\tfor b in range(1, n):\n\t\tprint(solution[a, b], end=' ')\n\tprint()\n", "import sys\ndebug = False\ninf = 1e+100\n\ndef minmove(n, a, b):\n\tif debug:\n\t\tprint('init', n, a, b)\n\tmemo = [[inf] * n for i in range(n)]\n\n\tdef move(x, y, step):\n\t\tif x < 0 or x > n - 1:\n\t\t\treturn False\n\t\tif y < 0 or y > n - 1:\n\t\t\treturn False\n\t\tif memo[x][y] <= step:\n\t\t\treturn False\n\t\tmemo[x][y] = step\n\t\tif x == n - 1 and y == n - 1:\n\t\t\tif debug:\n\t\t\t\tprint('memo', x, y, step)\n\t\t\treturn True\n\t\tstep += 1\n\t\tmove(x + a, y + b, step)\n\t\tmove(x + a, y - b, step)\n\t\tmove(x - a, y + b, step)\n\t\tmove(x - a, y - b, step)\n\t\tmove(x + b, y + a, step)\n\t\tmove(x + b, y - a, step)\n\t\tmove(x - b, y + a, step)\n\t\tmove(x - b, y - a, step)\n\tmove(0, 0, 0)\n\tif memo[n - 1][n - 1] < inf:\n\t\treturn memo[n - 1][n - 1]\n\telse:\n\t\treturn -1\nn = int(input().strip())\nminmoves = [[0] * (n - 1) for i in range(n - 1)]\nfor a in range(1, n):\n\tfor b in range(1, a + 1):\n\t\ti = a - 1\n\t\tj = b - 1\n\t\tminmoves[i][j] = minmove(n, a, b)\n\t\tminmoves[j][i] = minmoves[i][j]\n\t\tif debug:\n\t\t\tprint('save', i, j, minmoves[i][j])\nfor i in range(n - 1):\n\tprint(' '.join([str(s) for s in minmoves[i]]))\n", "import sys\nimport queue\nmemo = dict()\nn = int(input().strip())\nmemo[1, 1] = n - 1\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tif (min(i, j), max(i, j)) in memo:\n\t\t\tcontinue\n\t\tq = queue.Queue()\n\t\tq.put(((0, 0), 0, []))\n\t\tdone = set()\n\t\twhile True:\n\t\t\tif q.empty():\n\t\t\t\tmemo[min(i, j), max(i, j)] = -1\n\t\t\t\tbreak\n\t\t\t(pos, nmoves, prevmoves) = q.get()\n\t\t\tif pos in done:\n\t\t\t\tcontinue\n\t\t\tdone.add(pos)\n\n\t\t\tdef move():\n\t\t\t\t(x, y) = pos\n\t\t\t\tfor mx in (-1, 1):\n\t\t\t\t\tfor my in (-1, 1):\n\t\t\t\t\t\tfor r in (True, False):\n\t\t\t\t\t\t\tmv = (x + i * mx, y + j * my) if r else (x + j * mx, y + i * my)\n\t\t\t\t\t\t\tif mv == (n - 1, n - 1):\n\t\t\t\t\t\t\t\tmemo[min(i, j), max(i, j)] = nmoves + 1\n\t\t\t\t\t\t\t\treturn\n\t\t\t\t\t\t\tif mv[0] >= 0 and mv[1] >= 0 and (mv[0] < n) and (mv[1] < n) and (mv not in done):\n\t\t\t\t\t\t\t\tq.put((mv, nmoves + 1, prevmoves + [mv]))\n\t\t\tmove()\n\t\t\tif (min(i, j), max(i, j)) in memo:\n\t\t\t\tbreak\n\tprint(' '.join([str(memo[min(i, j), max(i, j)]) for j in range(1, n)]))\n", "import sys\n\ndef print_ans(results):\n\tfor row in results:\n\t\tfor val in row:\n\t\t\tprint(str(val), end=' ')\n\t\tprint('')\n\ndef find_ans(n, a, b):\n\tsteps = 0\n\tx = 0\n\tif a == b:\n\t\twhile x < n - 1:\n\t\t\tx += a\n\t\t\tsteps += 1\n\t\tif x != n - 1:\n\t\t\tsteps = -1\n\t\treturn steps\n\telse:\n\t\ty = 0\n\t\tmoves = ((a, b), (b, a), (a, -b), (b, -a), (-a, -b), (-b, -a), (-a, b), (-b, a))\n\t\tpresent = []\n\t\tvisited = [(0, 0)]\n\t\tpresent.append(moves[0])\n\t\tpresent.append(moves[1])\n\t\tsteps = 1\n\t\twhile len(present) != 0:\n\t\t\tfor pos in present.copy():\n\t\t\t\tfor movex in moves:\n\t\t\t\t\tn_pos = tuple((item1 + item2 for (item1, item2) in zip(pos, movex)))\n\t\t\t\t\tif n_pos[0] < 0 or n_pos[1] < 0 or n_pos[0] >= n or (n_pos[1] >= n):\n\t\t\t\t\t\tpass\n\t\t\t\t\telif n_pos in present:\n\t\t\t\t\t\tcontinue\n\t\t\t\t\telif n_pos in visited:\n\t\t\t\t\t\tcontinue\n\t\t\t\t\telif n_pos == (n - 1, n - 1):\n\t\t\t\t\t\treturn steps + 1\n\t\t\t\t\telse:\n\t\t\t\t\t\tvisited.append(n_pos)\n\t\t\t\t\t\tpresent.append(n_pos)\n\t\t\t\tpresent.remove(pos)\n\t\t\tsteps += 1\n\t\tsteps = -1\n\t\treturn steps\nn = int(input().strip())\nresults = []\ndone = []\nfor a in range(n - 1):\n\tresults.append([])\n\tfor b in range(n - 1):\n\t\tif (b + 1, a + 1) in done:\n\t\t\tresults[a].append(results[b][a])\n\t\telse:\n\t\t\tresults[a].append(find_ans(n, a + 1, b + 1))\n\t\tdone.append((a + 1, b + 1))\nprint_ans(results)\n", "import sys\n\ndef min_dist(n, a, b):\n\tstart = (0, 0)\n\tfinish = (n - 1, n - 1)\n\tchessboard = dict()\n\tchessboard[start] = 0\n\tfrontline = [start]\n\twhile len(frontline):\n\t\t(row, col) = frontline.pop(0)\n\t\tnext = [(row + r, col + c) for r in [-a, a] for c in [-b, b]]\n\t\tnext.extend([(row + r, col + c) for r in [-b, b] for c in [-a, a]])\n\t\tnext = filter(lambda pt: all((coord >= 0 and coord < n for coord in pt)), next)\n\t\tcurr_step = chessboard[row, col] + 1\n\t\tfor pt in next:\n\t\t\tif pt not in chessboard:\n\t\t\t\tchessboard[pt] = curr_step\n\t\t\t\tfrontline.append(pt)\n\t\t\telif chessboard[pt] > curr_step:\n\t\t\t\tchessboard[pt] = curr_step\n\t\t\t\tfrontline.append(pt)\n\treturn chessboard[finish] if finish in chessboard else -1\nn = int(input().strip())\nanswer = [[min_dist(n, a, b) for a in range(1, n)] for b in range(1, n)]\nfor line in answer:\n\tprint(*line)\n", "import sys\nn = int(input().strip())\nfor a in range(1, n):\n\tfor b in range(1, n):\n\t\tmin_moves = {}\n\n\t\tdef BFSfunction():\n\t\t\torigin = (1, 1)\n\t\t\tend = (n, n)\n\t\t\tline = [origin]\n\t\t\tmin_moves[origin] = 0\n\t\t\twhile len(line):\n\t\t\t\tcurrent = line[0]\n\t\t\t\tline.pop(0)\n\t\t\t\tif current == end:\n\t\t\t\t\tprint(min_moves[current], end=' ')\n\t\t\t\t\treturn\n\t\t\t\tfor move in [(a, b), (b, a), (-a, -b), (-b, -a), (a, -b), (-a, b), (-b, a), (b, -a)]:\n\t\t\t\t\tplus = (current[0] + move[0], current[1] + move[1])\n\t\t\t\t\tif plus[0] > end[0] or plus[1] > end[1] or plus[0] < 1 or (plus[1] < 1):\n\t\t\t\t\t\tcontinue\n\t\t\t\t\tif plus not in min_moves:\n\t\t\t\t\t\tmin_moves[plus] = min_moves[current] + 1\n\t\t\t\t\t\tline.append(plus)\n\t\t\telse:\n\t\t\t\tprint(-1, end=' ')\n\t\tBFSfunction()\n\tprint()\n", "import sys\n\ndef min_path(n, a, b):\n\tm = []\n\tprocessed = []\n\tfor i in range(n):\n\t\tm.append([-1] * n)\n\t\tprocessed.append([False] * n)\n\tm[0][0] = 0\n\twhile True:\n\t\tmn = -1\n\t\tmni = -1\n\t\tmnj = -1\n\t\tfor i in range(n):\n\t\t\tfor j in range(n):\n\t\t\t\tif m[i][j] != -1 and (not processed[i][j]):\n\t\t\t\t\tif mn == -1 or m[i][j] < mn:\n\t\t\t\t\t\tmn = m[i][j]\n\t\t\t\t\t\tmni = i\n\t\t\t\t\t\tmnj = j\n\t\tif mni == -1 and mnj == -1:\n\t\t\tbreak\n\t\tdirs = [[1, 1], [1, -1], [-1, 1], [-1, -1]]\n\t\tfor d in dirs:\n\t\t\tii = mni + d[0] * a\n\t\t\tjj = mnj + d[1] * b\n\t\t\tif ii >= 0 and ii < n and (jj >= 0) and (jj < n):\n\t\t\t\tif m[ii][jj] == -1:\n\t\t\t\t\tm[ii][jj] = mn + 1\n\t\t\t\telse:\n\t\t\t\t\tm[ii][jj] = min(mn + 1, m[ii][jj])\n\t\t\tii = mni + d[0] * b\n\t\t\tjj = mnj + d[1] * a\n\t\t\tif ii >= 0 and ii < n and (jj >= 0) and (jj < n):\n\t\t\t\tif m[ii][jj] == -1:\n\t\t\t\t\tm[ii][jj] = mn + 1\n\t\t\t\telse:\n\t\t\t\t\tm[ii][jj] = min(mn + 1, m[ii][jj])\n\t\tprocessed[mni][mnj] = True\n\t\tif mni == n - 1 and mnj == n - 1:\n\t\t\tbreak\n\treturn m[n - 1][n - 1]\nN = int(input())\nfor i in range(1, N):\n\tfor j in range(1, N):\n\t\tprint(min_path(N, i, j), end=' ')\n\tprint()\n", "import sys\nn = int(input().strip())\nboard = []\nfor i in range(n):\n\tfor j in range(n):\n\t\tboard.append([i, j])\nzero = [0, 0]\nreached = [[n - 1, n - 1]]\nfor i in range(1, n):\n\tans = []\n\tfor j in range(1, n):\n\t\treached = [[n - 1, n - 1]]\n\t\treachable = []\n\t\tmoves = [[i, j], [i, -j], [-i, j], [-i, -j], [j, i], [j, -i], [-j, i], [-j, -i]]\n\t\tfor square in reached:\n\t\t\tfor move in moves:\n\t\t\t\tnewsquare = [square[0] + move[0], square[1] + move[1]]\n\t\t\t\tif newsquare in board:\n\t\t\t\t\treachable.append(newsquare)\n\t\tmovecount = 1\n\t\twhile zero not in reachable and len(reachable) > 0 and (movecount < 100):\n\t\t\tnewreachable = []\n\t\t\tfor square in reachable:\n\t\t\t\tfor move in moves:\n\t\t\t\t\tnewsquare = [square[0] + move[0], square[1] + move[1]]\n\t\t\t\t\tif newsquare in board:\n\t\t\t\t\t\tif newsquare not in newreachable:\n\t\t\t\t\t\t\tnewreachable.append(newsquare)\n\t\t\tfor x in reached:\n\t\t\t\tif x in newreachable:\n\t\t\t\t\tnewreachable.remove(x)\n\t\t\tfor x in newreachable:\n\t\t\t\treached.append(x)\n\t\t\treachable = newreachable.copy()\n\t\t\tmovecount += 1\n\t\tif zero in reachable:\n\t\t\tans.append(movecount)\n\t\tif len(reachable) == 0:\n\t\t\tans.append(-1)\n\tfor x in ans:\n\t\tprint(x, end=' ')\n\tprint()\n", "import sys\n\ndef inBoardAndNotVisited(x, y, knight_visited, n):\n\tresult = False\n\tif x >= 0 and y >= 0 and (x < n) and (y < n) and (not knight_visited[x][y]):\n\t\tresult = True\n\treturn result\n\ndef knightNewReached(x_ini, y_ini, x_goal, y_goal, jump, knight_visited, next_pos, knight_new_reach, n):\n\tfor i in range(8):\n\t\tx_n = x_ini + next_pos[i][0]\n\t\ty_n = y_ini + next_pos[i][1]\n\t\tif inBoardAndNotVisited(x_n, y_n, knight_visited, n):\n\t\t\tknight_visited[x_n][y_n] = True\n\t\t\tknight_new_reach.add((x_n, y_n))\n\ndef knightl(a, b, x_goal, y_goal, n):\n\tjump = 0\n\tnext_pos = [[a, b], [a, -b], [-a, b], [-a, -b], [b, a], [b, -a], [-b, a], [-b, -a]]\n\tx_ini = 0\n\ty_ini = 0\n\tknight_visited = [[False for j in range(n)] for i in range(n)]\n\tknight_visited[x_ini][y_ini] = True\n\tknight_reach = {(x_ini, y_ini)}\n\treached = False\n\twhile not reached and len(knight_reach) > 0:\n\t\tknight_new_reach = set()\n\t\tfor i in knight_reach:\n\t\t\tx_ini = i[0]\n\t\t\ty_ini = i[1]\n\t\t\tknightNewReached(x_ini, y_ini, x_goal, y_goal, jump, knight_visited, next_pos, knight_new_reach, n)\n\t\tknight_reach = knight_new_reach\n\t\tjump += 1\n\t\tif (x_goal, y_goal) in knight_reach:\n\t\t\treached = True\n\tif not reached:\n\t\tjump = -1\n\treturn jump\nn = int(input().strip())\npaths = []\nknight_taken = [[False for j in range(n)] for i in range(n)]\nknight_value = [[0 for j in range(n)] for i in range(n)]\nfor a in range(1, n, 1):\n\tline = []\n\tfor b in range(1, n, 1):\n\t\tif not knight_taken[a][b]:\n\t\t\tjump = knightl(a, b, n - 1, n - 1, n)\n\t\t\tknight_taken[a][b] = True\n\t\t\tknight_taken[b][a] = True\n\t\t\tknight_value[a][b] = jump\n\t\t\tknight_value[b][a] = jump\n\t\tline.append(knight_value[a][b])\n\tpaths.append(line)\nfor line in paths:\n\tprint(line[0], end='')\n\tfor i in range(1, len(line), 1):\n\t\tprint('', line[i], end='')\n\tprint('')\n", "import sys\nfrom collections import deque\nn = int(input().strip())\n\ndef bfs(n, a, b):\n\tfront = set()\n\tque = deque()\n\tque.append((1, 1, 0))\n\tfront.add((1, 1))\n\twhile len(que) != 0:\n\t\t(cur_i, cur_j, step) = que.popleft()\n\t\tif cur_i == n and cur_j == n:\n\t\t\treturn step\n\t\tdirections = [(a, b), (a, -b), (-a, b), (-a, -b), (b, a), (b, -a), (-b, a), (-b, -a)]\n\t\tfor dir in directions:\n\t\t\t(new_i, new_j) = (cur_i + dir[0], cur_j + dir[1])\n\t\t\tif new_i >= 1 and new_i <= n and (new_j >= 1) and (new_j <= n) and ((new_i, new_j) not in front):\n\t\t\t\tque.append((new_i, new_j, step + 1))\n\t\t\t\tfront.add((new_i, new_j))\n\treturn -1\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tprint(bfs(n, i, j), end=' ')\n\tprint()\n", "import sys\n\ndef calc_coords(current, movement, n):\n\tcoords = []\n\tcoords.append((current[0] + movement[0], current[1] + movement[1]))\n\tcoords.append((current[0] + movement[0], current[1] - movement[1]))\n\tcoords.append((current[0] - movement[0], current[1] + movement[1]))\n\tcoords.append((current[0] - movement[0], current[1] - movement[1]))\n\tcoords.append((current[0] + movement[1], current[1] + movement[0]))\n\tcoords.append((current[0] + movement[1], current[1] - movement[0]))\n\tcoords.append((current[0] - movement[1], current[1] + movement[0]))\n\tcoords.append((current[0] - movement[1], current[1] - movement[0]))\n\tcopy = coords[:]\n\tfor i in coords:\n\t\tif i[0] not in range(n) or i[1] not in range(n):\n\t\t\tcopy.remove(i)\n\treturn copy\n\ndef knightL(i, j, n):\n\tseen = set()\n\tqueue = []\n\tsteps = 0\n\tmovement = (i, j)\n\tnext_nodes = 0\n\tcurrent_nodes = 1\n\tseen.add((0, 0))\n\tqueue.append((0, 0))\n\twhile queue:\n\t\tcurrent = queue.pop(0)\n\t\tcurrent_nodes -= 1\n\t\tif current[0] == n - 1 and current[1] == n - 1:\n\t\t\treturn steps\n\t\tnext_coords = calc_coords(current, movement, n)\n\t\tfor coords in next_coords:\n\t\t\tif coords not in seen:\n\t\t\t\tseen.add(coords)\n\t\t\t\tqueue.append(coords)\n\t\t\t\tnext_nodes += 1\n\t\tif current_nodes <= 0:\n\t\t\t(current_nodes, next_nodes) = (next_nodes, current_nodes)\n\t\t\tsteps += 1\n\treturn -1\nn = int(input().strip())\nfor i in range(1, n):\n\tj = 1\n\twhile j < n:\n\t\tprint(knightL(i, j, n), end=' ')\n\t\tj += 1\n\tprint()\n", "def way_finder(a, b, register, position):\n\tglobal count\n\tnewpositions = [position]\n\tcount = 0\n\twhile 1:\n\t\tresult = 0\n\t\tcount += 1\n\t\tfor j in range(len(newpositions)):\n\t\t\ti = 0\n\t\t\tif newpositions[i][0] - b >= 0 and newpositions[i][1] - a >= 0:\n\t\t\t\tnewposition = [newpositions[i][0] - b, newpositions[i][1] - a]\n\t\t\t\tif newposition == [0, 0]:\n\t\t\t\t\tresult = 2\n\t\t\t\t\tbreak\n\t\t\t\tif newposition not in register and newposition not in newpositions:\n\t\t\t\t\tresult = 1\n\t\t\t\t\tnewpositions.append([newpositions[i][0] - b, newpositions[i][1] - a])\n\t\t\tif newpositions[i][0] - a >= 0 and newpositions[i][1] - b >= 0:\n\t\t\t\tnewposition = [newpositions[i][0] - a, newpositions[i][1] - b]\n\t\t\t\tif newposition == [0, 0]:\n\t\t\t\t\tresult = 2\n\t\t\t\t\tbreak\n\t\t\t\tif newposition not in register and newposition not in newpositions:\n\t\t\t\t\tresult = 1\n\t\t\t\t\tnewpositions.append([newpositions[i][0] - a, newpositions[i][1] - b])\n\t\t\tif newpositions[i][0] - a >= 0 and newpositions[i][1] + b < n:\n\t\t\t\tnewposition = [newpositions[i][0] - a, newpositions[i][1] + b]\n\t\t\t\tif newposition == [0, 0]:\n\t\t\t\t\tresult = 2\n\t\t\t\t\tbreak\n\t\t\t\tif newposition not in register and newposition not in newpositions:\n\t\t\t\t\tresult = 1\n\t\t\t\t\tnewpositions.append([newpositions[i][0] - a, newpositions[i][1] + b])\n\t\t\tif newpositions[i][0] + a < n and newpositions[i][1] - b >= 0:\n\t\t\t\tnewposition = [newpositions[i][0] + a, newpositions[i][1] - b]\n\t\t\t\tif newposition == [0, 0]:\n\t\t\t\t\tresult = 2\n\t\t\t\t\tbreak\n\t\t\t\tif newposition not in register and newposition not in newpositions:\n\t\t\t\t\tresult = 1\n\t\t\t\t\tnewpositions.append([newpositions[i][0] + a, newpositions[i][1] - b])\n\t\t\tif newpositions[i][0] - b >= 0 and newpositions[i][1] + a < n:\n\t\t\t\tnewposition = [newpositions[i][0] - b, newpositions[i][1] + a]\n\t\t\t\tif newposition == [0, 0]:\n\t\t\t\t\tresult = 2\n\t\t\t\t\tbreak\n\t\t\t\tif newposition not in register and newposition not in newpositions:\n\t\t\t\t\tresult = 1\n\t\t\t\t\tnewpositions.append([newpositions[i][0] - b, newpositions[i][1] + a])\n\t\t\tif newpositions[i][0] + b < n and newpositions[i][1] - a >= 0:\n\t\t\t\tnewposition = [newpositions[i][0] + b, newpositions[i][1] - a]\n\t\t\t\tif newposition == [0, 0]:\n\t\t\t\t\tresult = 2\n\t\t\t\t\tbreak\n\t\t\t\tif newposition not in register and newposition not in newpositions:\n\t\t\t\t\tresult = 1\n\t\t\t\t\tnewpositions.append([newpositions[i][0] + b, newpositions[i][1] - a])\n\t\t\tif newpositions[i][0] + a < n and newpositions[i][1] + b < n:\n\t\t\t\tnewposition = [newpositions[i][0] + a, newpositions[i][1] + b]\n\t\t\t\tif newposition == [0, 0]:\n\t\t\t\t\tresult = 2\n\t\t\t\t\tbreak\n\t\t\t\tif newposition not in register and newposition not in newpositions:\n\t\t\t\t\tresult = 1\n\t\t\t\t\tnewpositions.append([newpositions[i][0] + a, newpositions[i][1] + b])\n\t\t\tif newpositions[i][0] + b < n and newpositions[i][1] + a < n:\n\t\t\t\tnewposition = [newpositions[i][0] + b, newpositions[i][1] + a]\n\t\t\t\tif newposition == [0, 0]:\n\t\t\t\t\tresult = 2\n\t\t\t\t\tbreak\n\t\t\t\tif newposition not in register and newposition not in newpositions:\n\t\t\t\t\tresult = 1\n\t\t\t\t\tnewpositions.append([newpositions[i][0] + b, newpositions[i][1] + a])\n\t\t\tnewpositions.pop(0)\n\t\tregister = register + newpositions\n\t\tif result == 0:\n\t\t\treturn -1\n\t\tif result == 2:\n\t\t\treturn count\nn = int(input())\nresultmatrix = [[[] for x in range(n - 1)] for x in range(n - 1)]\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tcount = 0\n\t\tposition = [n - 1, n - 1]\n\t\tresultmatrix[i - 1][j - 1] = way_finder(i, j, [[n - 1, n - 1]], position)\nfor i in range(0, n - 1):\n\tprint(' '.join(map(str, resultmatrix[i])))\n", "import collections\nn = int(input().strip())\nGOAL = (n - 1, n - 1)\n\ndef get_neighbors(square, a, b):\n\tdiffs = set([(a, b), (a, -b), (-a, b), (-a, -b), (b, a), (b, -a), (-b, a), (-b, -a)])\n\tfor d in diffs:\n\t\tneighbor = (square[0] + d[0], square[1] + d[1])\n\t\tif 0 <= neighbor[0] < n and 0 <= neighbor[1] < n:\n\t\t\tyield neighbor\n\ndef moves_to_goal(a, b):\n\tclosed_squares = set([(0, 0)])\n\tfrontier_squares = collections.deque([((0, 0), 0)])\n\twhile len(frontier_squares):\n\t\t(current_square, path_len) = frontier_squares.popleft()\n\t\tneighbors = get_neighbors(current_square, a, b)\n\t\tfor neighbor in neighbors:\n\t\t\tif neighbor == GOAL:\n\t\t\t\treturn path_len + 1\n\t\t\tif neighbor not in closed_squares:\n\t\t\t\tclosed_squares.add(neighbor)\n\t\t\t\tfrontier_squares.append((neighbor, path_len + 1))\n\treturn -1\nfor a in range(1, n):\n\trow = []\n\tfor b in range(1, n):\n\t\trow.append(str(moves_to_goal(a, b)))\n\tprint(' '.join(row))\n", "import sys\nn = int(input().strip())\nm = [[-1 for x in range(n)] for y in range(n)]\ng = 1\nwhile g <= n - 1:\n\td = 1\n\twhile d <= n - 1:\n\t\tvisited = []\n\t\tvisited.append((n - 1, n - 1))\n\t\tcounter = 0\n\t\tcur_len = 0\n\t\tdiff = len(visited) - cur_len\n\t\tif m[g][d] == -1:\n\t\t\twhile len(visited) > cur_len and (0, 0) not in visited:\n\t\t\t\tcur_len = len(visited)\n\t\t\t\tarr = visited[len(visited) - diff:len(visited)]\n\t\t\t\th = 0\n\t\t\t\twhile h <= len(arr) - 1:\n\t\t\t\t\t(t, r) = arr[h]\n\t\t\t\t\tif (t - g <= n - 1 and t - g >= 0) and (r - d <= n - 1 and r - d >= 0) and ((t - g, r - d) not in visited):\n\t\t\t\t\t\tvisited.append((t - g, r - d))\n\t\t\t\t\tif (t - g <= n - 1 and t - g >= 0) and (r + d <= n - 1 and r + d >= 0) and ((t - g, r + d) not in visited):\n\t\t\t\t\t\tvisited.append((t - g, r + d))\n\t\t\t\t\tif (t + g <= n - 1 and t + g >= 0) and (r - d <= n - 1 and r - d >= 0) and ((t + g, r - d) not in visited):\n\t\t\t\t\t\tvisited.append((t + g, r - d))\n\t\t\t\t\tif (t + g <= n - 1 and t + g >= 0) and (r + d <= n - 1 and r + d >= 0) and ((t + g, r + d) not in visited):\n\t\t\t\t\t\tvisited.append((t + g, r + d))\n\t\t\t\t\tif (t - d <= n - 1 and t - d >= 0) and (r - g <= n - 1 and r - g >= 0) and ((t - d, r - g) not in visited):\n\t\t\t\t\t\tvisited.append((t - d, r - g))\n\t\t\t\t\tif (t - d <= n - 1 and t - d >= 0) and (r + g <= n - 1 and r + g >= 0) and ((t - d, r + g) not in visited):\n\t\t\t\t\t\tvisited.append((t - d, r + g))\n\t\t\t\t\tif (t + d <= n - 1 and t + d >= 0) and (r - g <= n - 1 and r - g >= 0) and ((t + d, r - g) not in visited):\n\t\t\t\t\t\tvisited.append((t + d, r - g))\n\t\t\t\t\tif (t + d <= n - 1 and t + d >= 0) and (r + g <= n - 1 and r + g >= 0) and ((t + d, r + g) not in visited):\n\t\t\t\t\t\tvisited.append((t + d, r + g))\n\t\t\t\t\th = h + 1\n\t\t\t\tdiff = len(visited) - cur_len\n\t\t\t\tcounter = counter + 1\n\t\t\tif (0, 0) in visited:\n\t\t\t\tm[g][d] = counter\n\t\t\t\tm[d][g] = m[g][d]\n\t\td = d + 1\n\tg = g + 1\np = 1\nwhile p <= n - 1:\n\tline = ''\n\tg = 1\n\twhile g <= n - 1:\n\t\tline = line + ' ' + str(m[p][g])\n\t\tg = g + 1\n\tprint(line.lstrip())\n\tp = p + 1\n", "import sys\nn = int(input().strip())\nfor a in range(1, n):\n\tfor b in range(1, n):\n\t\tmin_moves = {}\n\n\t\tdef BFSfunction():\n\t\t\torigin = (1, 1)\n\t\t\tend = (n, n)\n\t\t\tline = [origin]\n\t\t\tmin_moves[origin] = 0\n\t\t\twhile len(line):\n\t\t\t\tcurrent = line[0]\n\t\t\t\tline.pop(0)\n\t\t\t\tif current == end:\n\t\t\t\t\tprint(min_moves[current], end=' ')\n\t\t\t\t\treturn\n\t\t\t\tfor move in [(a, b), (b, a), (-a, -b), (-b, -a), (a, -b), (-a, b), (-b, a), (b, -a)]:\n\t\t\t\t\tplus = (current[0] + move[0], current[1] + move[1])\n\t\t\t\t\tif plus[0] > end[0] or plus[1] > end[1] or plus[0] < 1 or (plus[1] < 1):\n\t\t\t\t\t\tcontinue\n\t\t\t\t\tif plus not in min_moves:\n\t\t\t\t\t\tmin_moves[plus] = min_moves[current] + 1\n\t\t\t\t\t\tline.append(plus)\n\t\t\telse:\n\t\t\t\tprint(-1, end=' ')\n\t\tBFSfunction()\n\tprint()\n", "import sys\nn = int(input().strip())\nA = []\nfor a in range(1, n):\n\tB = []\n\tfor b in range(1, n):\n\t\tP = {(0, 0)}\n\t\tc = 0\n\t\tf = True\n\t\tV = set()\n\t\twhile f:\n\t\t\tc += 1\n\t\t\tQ = set()\n\t\t\tV = V | P\n\t\t\tfor p in P:\n\t\t\t\tif (p[0] == n - 1) & (p[1] == n - 1):\n\t\t\t\t\tf = False\n\t\t\t\t\tbreak\n\t\t\t\tif (0 <= p[0] + a < n) & (0 <= p[1] + b < n):\n\t\t\t\t\tQ.add((p[0] + a, p[1] + b))\n\t\t\t\tif (0 <= p[0] - a < n) & (0 <= p[1] - b < n):\n\t\t\t\t\tQ.add((p[0] - a, p[1] - b))\n\t\t\t\tif (0 <= p[0] - a < n) & (0 <= p[1] + b < n):\n\t\t\t\t\tQ.add((p[0] - a, p[1] + b))\n\t\t\t\tif (0 <= p[0] + a < n) & (0 <= p[1] - b < n):\n\t\t\t\t\tQ.add((p[0] + a, p[1] - b))\n\t\t\t\tif (0 <= p[0] + b < n) & (0 <= p[1] + a < n):\n\t\t\t\t\tQ.add((p[0] + b, p[1] + a))\n\t\t\t\tif (0 <= p[0] - b < n) & (0 <= p[1] - a < n):\n\t\t\t\t\tQ.add((p[0] - b, p[1] - a))\n\t\t\t\tif (0 <= p[0] - b < n) & (0 <= p[1] + a < n):\n\t\t\t\t\tQ.add((p[0] - b, p[1] + a))\n\t\t\t\tif (0 <= p[0] + b < n) & (0 <= p[1] - a < n):\n\t\t\t\t\tQ.add((p[0] + b, p[1] - a))\n\t\t\tP = set()\n\t\t\tP = P | Q\n\t\t\tP = P - V\n\t\t\tif len(P) == 0:\n\t\t\t\tbreak\n\t\tif not f:\n\t\t\tB.append(c - 1)\n\t\telse:\n\t\t\tB.append(-1)\n\tA.append(B)\nfor a in A:\n\tfor b in a:\n\t\tprint(b, end=' ')\n\tprint('')\n", "from collections import deque\nn = int(input())\n\ndef is_square(a):\n\treturn a[0] >= 0 and a[1] >= 0 and (a[0] < n) and (a[1] < n)\n\ndef getDist(dx, dy):\n\tdist = {}\n\tque = deque()\n\tque.append((0, 0, 0))\n\tdirec = [(dx, dy), (dy, dx), (-dx, dy), (-dy, dx), (-dx, -dy), (-dy, -dx), (dx, -dy), (dy, -dx)]\n\twhile len(que) > 0:\n\t\t(a0, a1, d) = que.popleft()\n\t\ta = (a0, a1)\n\t\tif not is_square(a) or (a in dist and d >= dist[a]):\n\t\t\tcontinue\n\t\tdist[a] = d\n\t\tfor dire in direc:\n\t\t\tque.append((a[0] + dire[0], a[1] + dire[1], d + 1))\n\tif (n - 1, n - 1) in dist:\n\t\treturn dist[n - 1, n - 1]\n\telse:\n\t\treturn -1\nfor dx in range(1, n):\n\tout = []\n\tfor dy in range(1, n):\n\t\tout.append(getDist(dx, dy))\n\tprint(*out)\n", "from collections import deque\nfrom itertools import product, permutations\n\ndef deltas(y, x):\n\tperms = permutations([y, x])\n\tmul = product((1, -1), repeat=2)\n\treturn ((p[0] * m[0], p[1] * m[1]) for (p, m) in product(perms, mul))\nn = int(input())\nres = [[None] * (n - 1) for _ in range(n - 1)]\nfor i in range(1, n):\n\tfor j in range(i, n):\n\t\tdp = [[-1] * n for _ in range(n)]\n\t\tque = deque(((0, 0),))\n\t\tdp[0][0] = 0\n\t\twhile que:\n\t\t\t(y, x) = que.popleft()\n\t\t\tfor (dy, dx) in deltas(i, j):\n\t\t\t\ty1 = y + dy\n\t\t\t\tx1 = x + dx\n\t\t\t\tif 0 <= y1 < n and 0 <= x1 < n and (dp[y1][x1] == -1):\n\t\t\t\t\tdp[y1][x1] = dp[y][x] + 1\n\t\t\t\t\tque.append((y1, x1))\n\t\tres[i - 1][j - 1] = dp[-1][-1]\n\t\tres[j - 1][i - 1] = dp[-1][-1]\nprint(*(' '.join((str(x) for x in row)) for row in res), sep='\\n')\n", "import sys\nfrom collections import deque\nimport ast\n\ndef build_graph(graph, start, end, movement, n):\n\tqueue = deque([start])\n\tvisited = {start: False}\n\tcount = 0\n\twhile queue:\n\t\tu = queue[0]\n\t\tqueue.remove(u)\n\t\tif not visited.get(u, False):\n\t\t\tcount += 1\n\t\t\tvisited[u] = True\n\t\t\tfill_neighbours(graph, u, movement, n)\n\t\t\tneighbours = graph.get(u)\n\t\t\tfor v in neighbours:\n\t\t\t\tif not visited.get(v, False):\n\t\t\t\t\tqueue.append(v)\n\ndef add_neighbour(graph, node, neighbours):\n\tfor n in neighbours:\n\t\tif n not in graph.get(node, []):\n\t\t\tgraph.get(node).append(neighbours)\n\ndef fill_neighbours(graph, node, movement, n):\n\ta = movement[0]\n\tb = movement[1]\n\tpos = ast.literal_eval(node)\n\tx = pos[0]\n\ty = pos[1]\n\tlegal_pos = deque()\n\tfor i in [x + a, x - a]:\n\t\tfor j in [y - b, y + b]:\n\t\t\tif 0 <= i < n and 0 <= j < n:\n\t\t\t\tlegal_pos.append((i, j))\n\tfor i in [x + b, x - b]:\n\t\tfor j in [y - a, y + a]:\n\t\t\tif 0 <= i < n and 0 <= j < n:\n\t\t\t\tlegal_pos.append((i, j))\n\tfor pos in legal_pos:\n\t\tif str(pos) in graph:\n\t\t\tneighbours = graph.get(str(pos))\n\t\telse:\n\t\t\tgraph[str(pos)] = []\n\t\tadd_neighbour(graph, node, str(pos))\n\ndef BFS(graph, source_id, target_id):\n\tQ = deque([source_id])\n\tdistance = {source_id: 0}\n\tprevious = {}\n\tFlag = {source_id: True}\n\twhile Q:\n\t\tu = Q[0]\n\t\tQ.remove(u)\n\t\tfor v in graph.get(u):\n\t\t\tif Flag.get(v) is not True:\n\t\t\t\tdistance[v] = distance[u] + 1\n\t\t\t\tprevious[v] = u\n\t\t\t\tFlag[v] = True\n\t\t\t\tQ.append(v)\n\treturn (previous, distance)\n\ndef main():\n\tmode = int(input().strip())\n\tfor i in range(1, mode):\n\t\tline = []\n\t\tfor j in range(1, mode):\n\t\t\tstart = str((0, 0))\n\t\t\tend = str((mode - 1, mode - 1))\n\t\t\tgraph = {start: [], end: []}\n\t\t\tbuild_graph(graph, start, end, (i, j), mode)\n\t\t\t(previous, distance) = BFS(graph, start, end)\n\t\t\td = distance.get(end, -1)\n\t\t\tline.append(d)\n\t\tprint(*line)\nmain()\n", "from operator import __add__, __sub__\nfunctions = [(f, g) for f in [__add__, __sub__] for g in [__add__, __sub__]]\n\ndef positions(i, j, a, b):\n\treturn [(f(i, x), g(j, k)) for (x, k) in [(a, b), (b, a)] for (f, g) in functions]\n\ndef onmap(i, j, n):\n\t_o = lambda i, n: i < n and i >= 0\n\treturn _o(i, n) and _o(j, n)\n\ndef f(i, j, a, b, n, T, D, P):\n\tp = positions(i, j, a, b)\n\tfor (i, j) in p:\n\t\tif onmap(i, j, n):\n\t\t\tif T[i, j] == -1:\n\t\t\t\tT[i, j] = D\n\t\t\t\tP.append((i, j, D + 1))\n\tif len(P) > 0:\n\t\t(i, j, D) = P.pop(0)\n\t\tf(i, j, a, b, n, T, D, P)\nn = int(input())\nK = {(i, j): -1 for i in range(n) for j in range(n)}\nfor X in range(1, n):\n\tfor Y in range(1, n):\n\t\tT = {(i, j): -1 for i in range(n) for j in range(n)}\n\t\tT[n - 1, n - 1] = 0\n\t\tf(n - 1, n - 1, X, Y, n, T, 1, list())\n\t\tK[X, Y] = T[0, 0]\nfor X in range(1, n):\n\tfor Y in range(1, n):\n\t\tprint(K[X, Y], end=' ')\n\tprint()\n", "import sys\nn = int(input().strip())\n\ndef isOk(i, j):\n\tif i >= 0 and i < n and (j >= 0) and (j < n):\n\t\treturn True\n\telse:\n\t\treturn False\n\ndef bfs(i, j, a, b, res):\n\tqueue = []\n\ttemp = (i, j)\n\tqueue.append(temp)\n\tvisited[i][j] = True\n\tres[i][j] = 0\n\tdist = 0\n\tx = [a, a, -a, -a, b, b, -b, -b]\n\ty = [b, -b, b, -b, a, -a, a, -a]\n\twhile len(queue) != 0:\n\t\ttemp = queue.pop(0)\n\t\tfor w in range(len(x)):\n\t\t\tif isOk(temp[0] + x[w], temp[1] + y[w]) and (not visited[temp[0] + x[w]][temp[1] + y[w]]):\n\t\t\t\tres[temp[0] + x[w]][temp[1] + y[w]] = res[temp[0]][temp[1]] + 1\n\t\t\t\tvisited[temp[0] + x[w]][temp[1] + y[w]] = True\n\t\t\t\ttemp2 = (temp[0] + x[w], temp[1] + y[w])\n\t\t\t\tqueue.append(temp2)\n\treturn res[n - 1][n - 1]\nresult = [[-1] * n for _ in range(n)]\nfor i in range(n):\n\tfor j in range(n):\n\t\tvisited = [[False] * n for _ in range(n)]\n\t\tres = [[-1] * n for _ in range(n)]\n\t\ttemp = bfs(0, 0, i, j, res)\n\t\tresult[i][j] = temp\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tprint(result[i][j], end=' ')\n\tprint('')\n", "import sys\nfrom collections import deque\nn = int(input().strip())\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tflag = 0\n\t\tdq = deque()\n\t\tdq.append((0, 0, 0))\n\t\tvstd = dict()\n\n\t\tdef is_valid(x2, y2):\n\t\t\tif x2 >= 0 and y2 >= 0 and (x2 < n) and (y2 < n):\n\t\t\t\treturn 1\n\t\t\treturn 0\n\t\twhile len(dq):\n\t\t\t(x, y, moves) = dq.popleft()\n\t\t\tif vstd.get((x, y)):\n\t\t\t\tcontinue\n\t\t\tvstd[x, y] = 1\n\t\t\tif (x, y) == (n - 1, n - 1):\n\t\t\t\tprint(moves, end=' ')\n\t\t\t\tflag = 1\n\t\t\t\tbreak\n\t\t\tfor dx in (i, -i):\n\t\t\t\tfor dy in (j, -j):\n\t\t\t\t\tif is_valid(x + dx, y + dy):\n\t\t\t\t\t\tdq.append((x + dx, y + dy, moves + 1))\n\t\t\tfor dx in (j, -j):\n\t\t\t\tfor dy in (i, -i):\n\t\t\t\t\tif is_valid(x + dx, y + dy):\n\t\t\t\t\t\tdq.append((x + dx, y + dy, moves + 1))\n\t\tif not flag:\n\t\t\tprint(-1, end=' ')\n\tprint()\n", "from collections import deque\n\ndef next_move(i, j, a, b, n):\n\tmove1 = [(i + d1, j + d2) for d1 in (-a, a) for d2 in (-b, b)]\n\tmove2 = [(i + d1, j + d2) for d1 in (-b, b) for d2 in (-a, a)]\n\treturn filter(lambda t: all(map(lambda x: 0 <= x < n, t)), move1 + move2)\n\ndef knightl(a, b, n):\n\tvisited = [[False for _ in range(n)] for _ in range(n)]\n\tvisited[0][0] = True\n\tq = deque([(0, 0, 0)])\n\twhile q:\n\t\t(old_x, old_y, c) = q.popleft()\n\t\tfor newpos in next_move(old_x, old_y, a, b, n):\n\t\t\t(x, y) = newpos\n\t\t\tif not visited[x][y]:\n\t\t\t\tif (x, y) == (n - 1, n - 1):\n\t\t\t\t\treturn c + 1\n\t\t\t\tvisited[x][y] = True\n\t\t\t\tq.append((x, y, c + 1))\n\treturn -1\nn = int(input().strip())\nfor a in range(1, n):\n\tline = []\n\tfor b in range(1, n):\n\t\tline.append(knightl(a, b, n))\n\tprint(*line)\n", "import collections\nn = int(input())\nresult = [[-1] * (n - 1) for i in range(n - 1)]\nfor a in range(1, n + 1):\n\tfor b in range(1, n + 1):\n\t\tmoves = [(-a, -b), (-a, b), (a, -b), (a, b), (-b, -a), (-b, a), (b, -a), (b, a)]\n\t\tvisited = [[False] * n for i in range(n)]\n\t\tq = collections.deque([((0, 0), 0)])\n\t\tvisited[0][0] = True\n\t\twhile q:\n\t\t\t(x, steps) = q.popleft()\n\t\t\tvisited[x[0]][x[1]] = True\n\t\t\tif x == (n - 1, n - 1):\n\t\t\t\tresult[a - 1][b - 1] = steps\n\t\t\t\tbreak\n\t\t\tfor move in moves:\n\t\t\t\ttarget = (x[0] + move[0], x[1] + move[1])\n\t\t\t\tif 0 <= target[0] < n and 0 <= target[1] < n and (not visited[target[0]][target[1]]):\n\t\t\t\t\tq.append((target, steps + 1))\n\t\t\t\t\tvisited[target[0]][target[1]] = True\nfor row in result:\n\tprint(*row)\n", "import sys\nfrom collections import deque\n\ndef check_v(n, sol, c, x, y):\n\tif x >= 0 and x < n and (y >= 0) and (y < n):\n\t\tif sol[x][y] == -1:\n\t\t\tsol[x][y] = c + 1\n\t\t\treturn [c + 1, x, y]\n\ndef dfs(n, a, b):\n\tsol = [[-1 for _ in range(n)] for _ in range(n)]\n\tsol[0][0] = 0\n\tq = deque()\n\tq.append([0, 0, 0])\n\twhile len(q) > 0:\n\t\t(c, x, y) = q.popleft()\n\t\tnodes = list()\n\t\tnodes.append(check_v(n, sol, c, x + a, y + b))\n\t\tnodes.append(check_v(n, sol, c, x + a, y - b))\n\t\tnodes.append(check_v(n, sol, c, x - a, y + b))\n\t\tnodes.append(check_v(n, sol, c, x - a, y - b))\n\t\tnodes.append(check_v(n, sol, c, x + b, y + a))\n\t\tnodes.append(check_v(n, sol, c, x + b, y - a))\n\t\tnodes.append(check_v(n, sol, c, x - b, y + a))\n\t\tnodes.append(check_v(n, sol, c, x - b, y - a))\n\t\tfor node in nodes:\n\t\t\tif node != None:\n\t\t\t\tq.append(node)\n\treturn sol[n - 1][n - 1]\nn = int(input().strip())\nsol = list()\nfor i in range(1, n):\n\tl = list()\n\tsol.append(l)\n\tfor j in range(1, n):\n\t\tl.append(dfs(n, i, j))\nfor l in sol:\n\tprint(' '.join([str(i) for i in l]))\n", "import sys\nn = int(input().strip())\ntimes = [-1, 1]\n\ndef shortest(n, i, j):\n\tdist = [[sys.maxsize for _ in range(n)] for _ in range(n)]\n\tdist[0][0] = 0\n\tqueue = [(0, 0)]\n\twhile queue and dist[n - 1][n - 1] == sys.maxsize:\n\t\t(x, y) = queue.pop(0)\n\t\tcnt = dist[x][y]\n\t\tfor i1 in times:\n\t\t\tfor i2 in times:\n\t\t\t\tnx = x + i1 * i\n\t\t\t\tny = y + i2 * j\n\t\t\t\tif nx < n and nx >= 0 and (ny < n) and (ny >= 0):\n\t\t\t\t\tif dist[nx][ny] > cnt + 1:\n\t\t\t\t\t\tdist[nx][ny] = cnt + 1\n\t\t\t\t\t\tqueue.append((nx, ny))\n\t\t\t\tnx = x + i1 * j\n\t\t\t\tny = y + i2 * i\n\t\t\t\tif nx < n and nx >= 0 and (ny < n) and (ny >= 0):\n\t\t\t\t\tif dist[nx][ny] > cnt + 1:\n\t\t\t\t\t\tdist[nx][ny] = cnt + 1\n\t\t\t\t\t\tqueue.append((nx, ny))\n\treturn dist[n - 1][n - 1]\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\trslt = shortest(n, i, j)\n\t\tif rslt == sys.maxsize:\n\t\t\tprint('-1', end=' ')\n\t\telse:\n\t\t\tprint(rslt, end=' ')\n\tprint('')\n", "import sys\nn = int(input().strip())\nfor i in range(1, n):\n\tmvs = []\n\tfor j in range(1, n):\n\t\tv = set([])\n\t\tq = [(0, 0)]\n\t\tql = [0]\n\t\twhile q:\n\t\t\tx = q.pop(0)\n\t\t\tlv = ql.pop(0)\n\t\t\tif x == (n - 1, n - 1):\n\t\t\t\tmvs.append(lv)\n\t\t\t\tbreak\n\t\t\tif x in v:\n\t\t\t\tcontinue\n\t\t\tv.add(x)\n\t\t\tl = [y for y in [(x[0] + j, x[1] + i), (x[0] + i, x[1] + j), (x[0] + j, x[1] - i), (x[0] + i, x[1] - j), (x[0] - j, x[1] - i), (x[0] - i, x[1] - j), (x[0] - j, x[1] + i), (x[0] - i, x[1] + j)] if y[0] >= 0 and y[0] < n and (y[1] >= 0) and (y[1] < n)]\n\t\t\tq.extend(l)\n\t\t\tql.extend([lv + 1 for _ in l])\n\t\tif not q:\n\t\t\tmvs.append(-1)\n\tprint(' '.join([str(x) for x in mvs]))\n", "import sys\n\ndef all_moves(n, p, l):\n\t(a, b) = l\n\t(x, y) = p\n\tif x - a >= 0 and y - b >= 0:\n\t\tyield (x - a, y - b)\n\tif x - a >= 0 and y + b <= n:\n\t\tyield (x - a, y + b)\n\tif y - a >= 0 and x - b >= 0:\n\t\tyield (x - b, y - a)\n\tif y - a >= 0 and x + b <= n:\n\t\tyield (x + b, y - a)\n\tif x + a <= n and y - b >= 0:\n\t\tyield (x + a, y - b)\n\tif x + a <= n and y + b <= n:\n\t\tyield (x + a, y + b)\n\tif y + a <= n and x - b >= 0:\n\t\tyield (x - b, y + a)\n\tif y + a <= n and x + b <= n:\n\t\tyield (x + b, y + a)\n\ndef play(N, l):\n\tG = {(0, 0): {'visited': False, 'distance': 0, 'prev': None}, (N, N): {'visited': False, 'distance': float('inf'), 'prev': None}}\n\tp = (0, 0)\n\twhile True:\n\t\tc = G[p]\n\t\tfor neighbor in all_moves(N, p, l):\n\t\t\tif neighbor not in G:\n\t\t\t\tG[neighbor] = {'visited': False, 'distance': float('inf'), 'prev': None}\n\t\t\tn = G[neighbor]\n\t\t\tif not n['visited']:\n\t\t\t\tnew_distance = c['distance'] + 1\n\t\t\t\tif new_distance < n['distance']:\n\t\t\t\t\tn['distance'] = new_distance\n\t\t\t\t\tn['prev'] = p\n\t\tc['visited'] = True\n\t\tif p == (N, N):\n\t\t\tbreak\n\t\tp = sorted(filter(lambda l: not l[1]['visited'], G.items()), key=lambda l: l[1]['distance'])[0][0]\n\t\tif G[p] == float('inf'):\n\t\t\treturn -1\n\tp = (N, N)\n\tif G[p]['prev'] is None:\n\t\treturn -1\n\tsum = 0\n\twhile True:\n\t\tsum += 1\n\t\tp = G[p]['prev']\n\t\tif p == (0, 0):\n\t\t\tbreak\n\treturn sum\nn = int(input().strip())\nfor a in range(1, n):\n\tans = []\n\tfor b in range(1, n):\n\t\tans.append(play(n - 1, (a, b)))\n\tprint(' '.join(map(str, ans)))\n", "from queue import Queue\n\ndef getNumMovesForKnight(i, j, n):\n\ts = set()\n\tq = Queue()\n\troot = (0, 0, 0)\n\ts.add(root)\n\tq.put(root)\n\tmoves = [(i, j), (-i, j), (i, -j), (-i, -j), (j, i), (-j, i), (j, -i), (-j, -i)]\n\twhile not q.empty():\n\t\tc = q.get()\n\t\tif c[0] == n - 1 and c[1] == n - 1:\n\t\t\treturn str(c[2])\n\t\tfor move in moves:\n\t\t\tx = c[0] + move[0]\n\t\t\ty = c[1] + move[1]\n\t\t\tif x >= 0 and x < n and (y >= 0) and (y < n) and ((x, y) not in s):\n\t\t\t\ts.add((x, y))\n\t\t\t\tq.put((x, y, c[2] + 1))\n\treturn '-1'\nn = int(input().strip())\nfor i in range(1, n):\n\tnumMoves = []\n\tfor j in range(1, n):\n\t\tnumMoves.append(getNumMovesForKnight(i, j, n))\n\tprint(' '.join(numMoves))\n", "class GridBfsGraph:\n\n\tdef __init__(self, n, neighbours):\n\t\tself.visited = {}\n\t\tself.n = n\n\t\tself.neighbours = neighbours\n\n\tdef is_node_valid(self, node):\n\t\tif 0 <= node[0] and node[0] < self.n and (0 <= node[1]) and (node[1] < self.n):\n\t\t\treturn True\n\t\treturn False\n\n\tdef get_neighbours(self, node):\n\t\tnext_nodes = [(node[0] + dr, node[1] + dc) for (dr, dc) in self.neighbours]\n\t\treturn [node for node in next_nodes if self.is_node_valid(node)]\n\n\tdef breadth_first_search(self, starting_node):\n\t\tfrom collections import deque\n\t\tqueue = deque([])\n\t\tqueue.append((starting_node, 0))\n\t\twhile len(queue) > 0:\n\t\t\t(current_node, steps) = queue.popleft()\n\t\t\tif not self.is_node_valid(current_node):\n\t\t\t\tcontinue\n\t\t\tif current_node[0] == self.n - 1 and current_node[1] == self.n - 1:\n\t\t\t\treturn steps\n\t\t\tif current_node in self.visited:\n\t\t\t\tcontinue\n\t\t\tself.visited[current_node] = True\n\t\t\tfor next_node in self.get_neighbours(current_node):\n\t\t\t\tqueue.append((next_node, steps + 1))\n\t\treturn -1\nn = int(input())\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tgraph = GridBfsGraph(n, [(-i, j), (-i, -j), (i, j), (i, -j), (j, i), (j, -i), (-j, i), (-j, -i)])\n\t\tprint(graph.breadth_first_search((0, 0)), end=' ')\n\tprint()\n", "def bfs(x, y, target_x, target_y, movements):\n\tstack = list()\n\tstack.append((x, y, 0))\n\tto_visit = set()\n\tif x == target_x and y == target_y:\n\t\treturn 0\n\telse:\n\t\ti = 0\n\t\twhile len(stack) > 0:\n\t\t\t(x, y, depth) = stack.pop(0)\n\t\t\tfor (dx, dy) in movements:\n\t\t\t\tpx = x + dx\n\t\t\t\tpy = y + dy\n\t\t\t\tif px == target_x and py == target_y:\n\t\t\t\t\treturn depth + 1\n\t\t\t\telif (0 <= px < N and 0 <= py < N) and (not (px, py) in to_visit):\n\t\t\t\t\tstack.append((px, py, depth + 1))\n\t\t\t\t\tto_visit.add((px, py))\n\t\t\ti += 1\n\treturn -1\nN = int(input())\nfor i in range(1, N):\n\tfor j in range(1, N):\n\t\tcache = dict()\n\t\tmovements = [(i, j), (i, -j), (-i, -j), (-i, j), (j, i), (j, -i), (-j, -i), (-j, i)]\n\t\tdistance = bfs(0, 0, N - 1, N - 1, movements)\n\t\tprint(distance, end=' ')\n\tprint('')\n", "from collections import deque\n\ndef dfs(i, j):\n\tboard = tuple(([-1] * n for _ in range(n)))\n\tboard[0][0] = 0\n\tcache = deque(((0, 0),))\n\twhile cache:\n\t\t(x, y) = cache.popleft()\n\t\tsteps = board[x][y] + 1\n\t\tfor (a, b) in ((x + i, y + j), (x + i, y - j), (x - i, y + j), (x - i, y - j), (x + j, y + i), (x + j, y - i), (x - j, y + i), (x - j, y - i)):\n\t\t\tif 0 <= a < n and 0 <= b < n and (board[a][b] == -1):\n\t\t\t\tcache.append((a, b))\n\t\t\t\tboard[a][b] = steps\n\treturn str(board[-1][-1])\nn = int(input().strip())\nnm1 = n - 1\nresult = tuple(([None] * nm1 for _ in range(nm1)))\nfor i in range(nm1):\n\tfor j in range(i, nm1):\n\t\tresult[i][j] = result[j][i] = dfs(i + 1, j + 1)\nprint('\\n'.join((' '.join(row) for row in result)))\n", "import sys\nfrom collections import deque\nn = int(input().strip())\n\ndef moves(visited, x, y, a, b):\n\ttemp = {(x + a, y + b), (x + a, y - b), (x - a, y + b), (x - a, y - b), (x + b, y + a), (x + b, y - a), (x - b, y + a), (x - b, y - a)}\n\tfinal = set()\n\tfor val in temp:\n\t\tif -1 < val[0] < n and -1 < val[1] < n and (visited[val[0]][val[1]] == 0):\n\t\t\tfinal.add(val)\n\treturn final\nfor a in range(1, n):\n\tfor b in range(1, n):\n\t\tqueue = deque()\n\t\tqueue.append((0, 0))\n\t\tchildqueue = set()\n\t\tcount = 0\n\t\tvisited = [[0 for j in range(n)] for i in range(n)]\n\t\twhile queue or childqueue:\n\t\t\tcurrent = queue.popleft()\n\t\t\tvisited[current[0]][current[1]] = 1\n\t\t\ttemp = moves(visited, *current + (a, b))\n\t\t\tif (n - 1, n - 1) in temp:\n\t\t\t\tprint(count + 1, end=' ')\n\t\t\t\tbreak\n\t\t\tchildqueue = childqueue.union(temp)\n\t\t\tif not queue:\n\t\t\t\tqueue = deque(childqueue)\n\t\t\t\tcount += 1\n\t\t\t\tchildqueue = set()\n\t\telse:\n\t\t\tprint('-1', end=' ')\n\tprint('')\n", "import sys\n\ndef check(x, y, n, b, p):\n\tif x >= 0 and x < n and (y >= 0) and (y < n) and (b[x][y] == -1 or b[x][y] > p):\n\t\treturn True\n\treturn False\nn = int(input().strip())\nres = [[-1] * n for k in range(n)]\nfor i in range(1, n, 1):\n\tres = []\n\tfor j in range(1, n, 1):\n\t\tq = [[0, 0, 0]]\n\t\tb = [[-1] * n for k in range(n)]\n\t\tb[0][0] = 0\n\t\twhile q:\n\t\t\tnew_q = []\n\t\t\tfor k in range(len(q)):\n\t\t\t\tp = q[k]\n\t\t\t\tif check(p[0] + i, p[1] + j, n, b, p[2] + 1) == True:\n\t\t\t\t\tb[p[0] + i][p[1] + j] = p[2] + 1\n\t\t\t\t\tnew_q.append([p[0] + i, p[1] + j, p[2] + 1])\n\t\t\t\tif check(p[0] + j, p[1] + i, n, b, p[2] + 1) == True:\n\t\t\t\t\tb[p[0] + j][p[1] + i] = p[2] + 1\n\t\t\t\t\tnew_q.append([p[0] + j, p[1] + i, p[2] + 1])\n\t\t\t\tif check(p[0] - i, p[1] + j, n, b, p[2] + 1) == True:\n\t\t\t\t\tb[p[0] - i][p[1] + j] = p[2] + 1\n\t\t\t\t\tnew_q.append([p[0] - i, p[1] + j, p[2] + 1])\n\t\t\t\tif check(p[0] - j, p[1] + i, n, b, p[2] + 1) == True:\n\t\t\t\t\tb[p[0] - j][p[1] + i] = p[2] + 1\n\t\t\t\t\tnew_q.append([p[0] - j, p[1] + i, p[2] + 1])\n\t\t\t\tif check(p[0] - i, p[1] - j, n, b, p[2] + 1) == True:\n\t\t\t\t\tb[p[0] - i][p[1] - j] = p[2] + 1\n\t\t\t\t\tnew_q.append([p[0] - i, p[1] - j, p[2] + 1])\n\t\t\t\tif check(p[0] - j, p[1] - i, n, b, p[2] + 1) == True:\n\t\t\t\t\tb[p[0] - j][p[1] - i] = p[2] + 1\n\t\t\t\t\tnew_q.append([p[0] - j, p[1] - i, p[2] + 1])\n\t\t\t\tif check(p[0] + i, p[1] - j, n, b, p[2] + 1) == True:\n\t\t\t\t\tb[p[0] + i][p[1] - j] = p[2] + 1\n\t\t\t\t\tnew_q.append([p[0] + i, p[1] - j, p[2] + 1])\n\t\t\t\tif check(p[0] + j, p[1] - i, n, b, p[2] + 1) == True:\n\t\t\t\t\tb[p[0] + j][p[1] - i] = p[2] + 1\n\t\t\t\t\tnew_q.append([p[0] + j, p[1] - i, p[2] + 1])\n\t\t\tq = new_q\n\t\tres.append(b[n - 1][n - 1])\n\tprint(' '.join(('{0}'.format(r) for r in res)))\n", "import sys\n\ndef compute(N, a, b):\n\tpMap = {(0, 0): 0}\n\tnewPositions = [(0, 0)]\n\ttarget = (N - 1, N - 1)\n\twhile len(newPositions):\n\t\t(px, py) = newPositions.pop(0)\n\t\tdests = [(px + a, py + b), (px + a, py - b), (px - a, py + b), (px - a, py - b), (px + b, py + a), (px + b, py - a), (px - b, py + a), (px - b, py - a)]\n\t\tfor d in dests:\n\t\t\tif d not in pMap and 0 <= d[0] < N and (0 <= d[1] < N):\n\t\t\t\tmoves = pMap[px, py] + 1\n\t\t\t\tif d == target:\n\t\t\t\t\treturn moves\n\t\t\t\tpMap[d] = moves\n\t\t\t\tnewPositions.append(d)\n\treturn -1\nN = int(input().strip())\nfor i in range(1, N):\n\trowVals = []\n\tfor j in range(1, N):\n\t\trowVals.append(compute(N, i, j))\n\tprint(' '.join((str(x) for x in rowVals)))\n", "import sys\nimport queue\n\nclass state:\n\n\tdef __init__(self, x, y, num_moves):\n\t\t(self.x, self.y, self.num_moves) = (x, y, num_moves)\n\n\tdef __eq__(self, other):\n\t\treturn self.x == other.x and self.y == other.y\n\n\tdef __hash__(self):\n\t\treturn hash((self.x, self.y))\nn = int(input().strip())\n\ndef get_moves(x, y, num_moves, a, b):\n\tmoves = []\n\tif x + a < n:\n\t\tif y + b < n:\n\t\t\tmoves.append(state(x + a, y + b, num_moves))\n\t\tif y - b >= 0:\n\t\t\tmoves.append(state(x + a, y - b, num_moves))\n\tif x - a >= 0:\n\t\tif y + b < n:\n\t\t\tmoves.append(state(x - a, y + b, num_moves))\n\t\tif y - b >= 0:\n\t\t\tmoves.append(state(x - a, y - b, num_moves))\n\tif x + b < n:\n\t\tif y + a < n:\n\t\t\tmoves.append(state(x + b, y + a, num_moves))\n\t\tif y - a >= 0:\n\t\t\tmoves.append(state(x + b, y - a, num_moves))\n\tif x - b >= 0:\n\t\tif y + a < n:\n\t\t\tmoves.append(state(x - b, y + a, num_moves))\n\t\tif y - a >= 0:\n\t\t\tmoves.append(state(x - b, y - a, num_moves))\n\treturn moves\n\ndef bfs(a, b):\n\tvisited = set()\n\tfringe = queue.Queue()\n\tstart = state(0, 0, 0)\n\tgoal = state(n - 1, n - 1, None)\n\tvisited.add(start)\n\tfringe.put(start)\n\twhile not fringe.empty():\n\t\tcurrent = fringe.get()\n\t\tif current == goal:\n\t\t\treturn current.num_moves\n\t\tfor move in get_moves(current.x, current.y, current.num_moves + 1, a, b):\n\t\t\tif move not in visited:\n\t\t\t\tvisited.add(move)\n\t\t\t\tfringe.put(move)\n\treturn -1\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tprint(bfs(i, j), end=' ')\n\tprint()\n", "import sys\nimport queue as queue\nn = int(input().strip())\n\ndef findRequiredSteps(a, b, n):\n\ts = set([])\n\tq = queue.Queue()\n\tadjNodesCalc = []\n\tadjNodes = []\n\trs = set([(0, 0)])\n\troot = (0, 0)\n\trounds = 0\n\ttarget = (n - 1, n - 1)\n\ts.add(root)\n\tq.put(root)\n\twhile q.empty() != True:\n\t\tcurrent = q.get()\n\t\t(xcor, ycor) = (current[0], current[1])\n\t\tif current not in rs:\n\t\t\trounds += 1\n\t\t\trs = rs | set(adjNodesCalc)\n\t\t\tadjNodesCalc = []\n\t\tadjNodes = list(filter(lambda x: 0 <= x[0] < n and 0 <= x[1] < n, [(xcor - a, ycor + b), (xcor - a, ycor - b), (xcor + a, ycor - b), (xcor - b, ycor + a), (xcor - b, ycor - a), (xcor + b, ycor - a), (xcor + a, ycor + b), (xcor + b, ycor + a)]))\n\t\tadjNodesCalc.extend(adjNodes)\n\t\tif target in adjNodes:\n\t\t\trounds += 1\n\t\t\treturn rounds\n\t\tfor node in adjNodes:\n\t\t\tif node not in s:\n\t\t\t\ts.add(node)\n\t\t\t\tq.put(node)\n\treturn -1\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tprint(findRequiredSteps(i, j, n), end=' ')\n\tprint('\\n', end='')\n", "def minMove(n, a, b):\n\tpositionsToProcess = [[0, 0]]\n\tknightMoves = [[a, b], [a, -1 * b], [-1 * a, b], [-1 * a, -1 * b], [b, a], [b, -1 * a], [-1 * b, a], [-1 * b, -1 * a]]\n\tvisitedPositions = []\n\tdistance = 0\n\twhile len(positionsToProcess) != 0:\n\t\ttemp = []\n\t\tdistance += 1\n\t\tfor position in positionsToProcess:\n\t\t\tfor move in range(8):\n\t\t\t\tnewPosition = [position[0] + knightMoves[move][0], position[1] + knightMoves[move][1]]\n\t\t\t\tif newPosition[0] >= 0 and newPosition[0] <= n - 1:\n\t\t\t\t\tif newPosition[1] >= 0 and newPosition[1] <= n - 1:\n\t\t\t\t\t\tif newPosition not in visitedPositions and newPosition not in temp:\n\t\t\t\t\t\t\tif newPosition == [n - 1, n - 1]:\n\t\t\t\t\t\t\t\treturn distance\n\t\t\t\t\t\t\telse:\n\t\t\t\t\t\t\t\ttemp.append(newPosition)\n\t\tvisitedPositions += positionsToProcess\n\t\tpositionsToProcess = temp\n\treturn -1\nn = int(input())\nfor a in range(1, n):\n\tfor b in range(1, n):\n\t\tanswer = minMove(n, a, b)\n\t\tprint(answer, end=' ')\n\tprint()\n", "import sys\n\ndef get_frontier(cur, level, i, j, n):\n\tfrontier = []\n\tfor k in [-i, i]:\n\t\tfor m in [-j, j]:\n\t\t\tfor (p1, p2) in [(cur[0] + k, cur[1] + m), (cur[0] + m, cur[1] + k)]:\n\t\t\t\tif 0 <= p1 <= n - 1 and 0 <= p2 <= n - 1 and ((p1, p2) not in level):\n\t\t\t\t\tfrontier.append((p1, p2))\n\treturn frontier\n\ndef reach(fr, to, i, j, n):\n\tdist = 0\n\tlevel = {fr: dist}\n\tdist += 1\n\tfrontier = get_frontier(fr, level, i, j, n)\n\twhile frontier:\n\t\tnxt = []\n\t\tfor p in frontier:\n\t\t\tif p not in level:\n\t\t\t\tlevel[p] = dist\n\t\t\t\tif p == to:\n\t\t\t\t\treturn (dist, level)\n\t\t\t\tp_frontier = get_frontier(p, level, i, j, n)\n\t\t\t\tnxt.extend(p_frontier)\n\t\tdist += 1\n\t\tfrontier = nxt\n\treturn (-1, level)\n\ndef min_reach(n, i, j):\n\t(fr, to) = ((0, 0), (n - 1, n - 1))\n\t(m, level) = reach(fr, to, i, j, n)\n\treturn m\n\ndef print_ans(ans):\n\tfor row in ans:\n\t\tstr_row = ' '.join((str(c) for c in row))\n\t\tprint(str_row)\n\ndef enter_data():\n\tn = int(input().strip())\n\tans = []\n\tfor i in range(1, n):\n\t\trow = []\n\t\tfor j in range(1, n):\n\t\t\tm = min_reach(n, i, j)\n\t\t\trow.append(m)\n\t\tans.append(row)\n\treturn ans\nans = enter_data()\nprint_ans(ans)\n", "import sys\nfrom itertools import combinations\nimport collections\n\ndef FindMin(n, a, b):\n\tfound = {}\n\tCombos = [[0, 0]]\n\tdepth = 0\n\twhile len(Combos) > 0:\n\t\tnewCombos = {}\n\t\tfor loc in Combos:\n\t\t\tcurrentKey = '{}x{}'.format(loc[0], loc[1])\n\t\t\tif loc[0] == n - 1 and loc[1] == n - 1:\n\t\t\t\treturn depth\n\t\t\telse:\n\t\t\t\tfound[currentKey] = 1\n\t\t\t\tnewCombos['{}x{}'.format(loc[0] + a, loc[1] + b)] = [loc[0] + a, loc[1] + b]\n\t\t\t\tnewCombos['{}x{}'.format(loc[0] + a, loc[1] - b)] = [loc[0] + a, loc[1] - b]\n\t\t\t\tnewCombos['{}x{}'.format(loc[0] - a, loc[1] + b)] = [loc[0] - a, loc[1] + b]\n\t\t\t\tnewCombos['{}x{}'.format(loc[0] - a, loc[1] - b)] = [loc[0] - a, loc[1] - b]\n\t\t\t\tnewCombos['{}x{}'.format(loc[0] + b, loc[1] + a)] = [loc[0] + b, loc[1] + a]\n\t\t\t\tnewCombos['{}x{}'.format(loc[0] + b, loc[1] - a)] = [loc[0] + b, loc[1] - a]\n\t\t\t\tnewCombos['{}x{}'.format(loc[0] - b, loc[1] + a)] = [loc[0] - b, loc[1] + a]\n\t\t\t\tnewCombos['{}x{}'.format(loc[0] - b, loc[1] - a)] = [loc[0] - b, loc[1] - a]\n\t\tdepth += 1\n\t\tCombos = []\n\t\tfor key in newCombos:\n\t\t\tcombo = newCombos[key]\n\t\t\tif (combo[0] > n - 1 or combo[0] < 0) or (combo[1] > n - 1 or combo[1] < 0):\n\t\t\t\tcontinue\n\t\t\telif key in found:\n\t\t\t\tcontinue\n\t\t\telse:\n\t\t\t\tCombos.append(combo)\n\treturn -1\nn = int(input().strip())\noutput = [[0 for x in range(n - 1)] for y in range(n - 1)]\nfor i in range(0, n - 1):\n\tfor j in range(i, n - 1):\n\t\toutput[i][j] = FindMin(n, i + 1, j + 1)\n\t\toutput[j][i] = output[i][j]\nfor item in output:\n\tprint(' '.join(map(str, item)))\n", "import sys\nfrom collections import deque\n\ndef getdxdy(a, b):\n\tif a == b:\n\t\treturn [(-a, -b), (-a, b), (a, -b), (a, b)]\n\telse:\n\t\treturn [(-a, -b), (-a, b), (a, -b), (a, b), (-b, -a), (-b, a), (b, -a), (b, a)]\n\ndef search(n, a, b):\n\td = deque([(0, 0, 0)])\n\tm = [0 for i in range(n * n)]\n\twhile len(d) > 0:\n\t\t(x, y, level) = d.popleft()\n\t\tm[n * x + y] = 1\n\t\tfor (dx, dy) in getdxdy(a, b):\n\t\t\tnext_x = x + dx\n\t\t\tnext_y = y + dy\n\t\t\tif 0 <= next_x < n and 0 <= next_y < n and (m[n * next_x + next_y] == 0):\n\t\t\t\td.append((next_x, next_y, level + 1))\n\t\t\t\tm[n * next_x + next_y] = 1\n\t\t\tif next_x == n - 1 and next_y == n - 1:\n\t\t\t\treturn level + 1\n\treturn -1\nn = int(input().strip())\nans = [[0 for i in range(n)] for j in range(n)]\nfor a in range(1, n):\n\tfor b in range(a, n):\n\t\tans[a][b] = ans[b][a] = search(n, a, b)\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tprint(ans[i][j], end=' ')\n\tprint('')\n", "import collections as col\n\nclass CNode:\n\n\tdef __init__(self, x, y):\n\t\tself.x = x\n\t\tself.y = y\n\t\tself.distance = None\n\t\tself.parent = None\n\n\tdef get_poss_moves(self, a, b, n):\n\t\tpmoves = []\n\t\tfor (i, j) in [(self.x + a, self.y + b), (self.x + b, self.y + a), (self.x - a, self.y + b), (self.x - b, self.y + a), (self.x + a, self.y - b), (self.x + b, self.y - a), (self.x - a, self.y - b), (self.x - b, self.y - a)]:\n\t\t\tif 0 <= i < n and 0 <= j < n:\n\t\t\t\tif (i, j) not in pmoves:\n\t\t\t\t\tpmoves.append((i, j))\n\t\treturn pmoves\n\n\tdef __hash__(self):\n\t\treturn hash((self.x, self.y))\n\n\tdef __eq__(self, other):\n\t\treturn self.x == other.x and self.y == other.y\n\n\tdef __str__(self):\n\t\treturn str('{},{} : {}'.format(self.x, self.y, self.distance))\n\nclass CTree:\n\n\tdef __init__(self, cnode, a, b, n):\n\t\tself.root = cnode\n\t\tself.a = a\n\t\tself.b = b\n\t\tself.n = n\n\t\tself.dx = n - 1\n\t\tself.dy = n - 1\n\t\tself.visited = []\n\n\tdef do_search(self, node):\n\t\tS = set()\n\t\tQ = col.deque()\n\t\tS.add(node)\n\t\tQ.appendleft(node)\n\t\twhile len(Q) > 0:\n\t\t\tcurrent = Q.pop()\n\t\t\tif current.x == self.dx and current.y == self.dy:\n\t\t\t\tcurrent.distance = 0\n\t\t\t\tlpnode = current\n\t\t\t\twhile lpnode is not None:\n\t\t\t\t\tif lpnode.parent:\n\t\t\t\t\t\tlpnode.parent.distance = lpnode.distance + 1\n\t\t\t\t\t\tlpnode = lpnode.parent\n\t\t\t\t\telse:\n\t\t\t\t\t\tlpnode = None\n\t\t\t\treturn current\n\t\t\telse:\n\t\t\t\tpmoves = current.get_poss_moves(self.a, self.b, self.n)\n\t\t\t\tfor p in pmoves:\n\t\t\t\t\tpnode = CNode(p[0], p[1])\n\t\t\t\t\tif pnode not in S:\n\t\t\t\t\t\tS.add(pnode)\n\t\t\t\t\t\tpnode.parent = current\n\t\t\t\t\t\tQ.appendleft(pnode)\n\ndef do_walk(x, y, a, b, n):\n\tcnode = CNode(x, y)\n\tctree = CTree(cnode, a, b, n)\n\tfnode = ctree.do_search(cnode)\n\treturn cnode.distance if cnode.distance is not None else -1\nnb = int(input())\nfor i in range(1, nb):\n\trl = []\n\tfor j in range(1, nb):\n\t\trl.append(str(do_walk(0, 0, i, j, nb)))\n\tprint(' '.join(rl))\n", "import sys\nn = int(input().strip())\nA = []\nfor a in range(1, n):\n\tB = []\n\tfor b in range(1, n):\n\t\tP = {(0, 0)}\n\t\tc = 0\n\t\tf = True\n\t\tV = set()\n\t\twhile f:\n\t\t\tc += 1\n\t\t\tQ = set()\n\t\t\tV = V | P\n\t\t\tfor p in P:\n\t\t\t\tif (p[0] == n - 1) & (p[1] == n - 1):\n\t\t\t\t\tf = False\n\t\t\t\t\tbreak\n\t\t\t\tif (0 <= p[0] + a < n) & (0 <= p[1] + b < n):\n\t\t\t\t\tQ.add((p[0] + a, p[1] + b))\n\t\t\t\tif (0 <= p[0] - a < n) & (0 <= p[1] - b < n):\n\t\t\t\t\tQ.add((p[0] - a, p[1] - b))\n\t\t\t\tif (0 <= p[0] - a < n) & (0 <= p[1] + b < n):\n\t\t\t\t\tQ.add((p[0] - a, p[1] + b))\n\t\t\t\tif (0 <= p[0] + a < n) & (0 <= p[1] - b < n):\n\t\t\t\t\tQ.add((p[0] + a, p[1] - b))\n\t\t\t\tif (0 <= p[0] + b < n) & (0 <= p[1] + a < n):\n\t\t\t\t\tQ.add((p[0] + b, p[1] + a))\n\t\t\t\tif (0 <= p[0] - b < n) & (0 <= p[1] - a < n):\n\t\t\t\t\tQ.add((p[0] - b, p[1] - a))\n\t\t\t\tif (0 <= p[0] - b < n) & (0 <= p[1] + a < n):\n\t\t\t\t\tQ.add((p[0] - b, p[1] + a))\n\t\t\t\tif (0 <= p[0] + b < n) & (0 <= p[1] - a < n):\n\t\t\t\t\tQ.add((p[0] + b, p[1] - a))\n\t\t\tP = set()\n\t\t\tP = P | Q\n\t\t\tP = P - V\n\t\t\tif len(P) == 0:\n\t\t\t\tbreak\n\t\tif not f:\n\t\t\tB.append(c - 1)\n\t\telse:\n\t\t\tB.append(-1)\n\tA.append(B)\nfor a in A:\n\tfor b in a:\n\t\tprint(b, end=' ')\n\tprint('')\n", "import sys\nimport collections as q\nresults = {}\nn = int(input().strip())\nfor i in range(1, n):\n\tfor j in range(i, n):\n\t\tdirections = [(i, j), (i, -j), (-i, j), (-i, -j), (j, i), (j, -i), (-j, i), (-j, -i)]\n\t\tnum_moves = 0\n\t\tmoves = q.deque([(1, 1, 0)])\n\t\tvisited = {(1, 1)}\n\t\twhile moves and num_moves == 0:\n\t\t\tm = moves.pop()\n\t\t\tfor d in directions:\n\t\t\t\tlr = m[0] + d[0]\n\t\t\t\tud = m[1] + d[1]\n\t\t\t\tif lr == n and ud == n:\n\t\t\t\t\tnum_moves = m[2] + 1\n\t\t\t\t\tbreak\n\t\t\t\telif 1 <= lr and lr <= n and (1 <= ud) and (ud <= n) and ((lr, ud) not in visited):\n\t\t\t\t\tmoves.appendleft([lr, ud, m[2] + 1])\n\t\t\t\t\tvisited.add((lr, ud))\n\t\tresults[i, j] = num_moves\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tif i <= j and results[i, j]:\n\t\t\tprint(results[i, j], end=' ')\n\t\telif i > j and results[j, i]:\n\t\t\tprint(results[j, i], end=' ')\n\t\telse:\n\t\t\tprint(-1, end=' ')\n\t\tif j == n - 1:\n\t\t\tprint()\n", "import sys\nimport collections\n\ndef min_moves(n, a, b):\n\tvisited = set()\n\tqueue = collections.deque()\n\tqueue.appendleft((0, 0, 0))\n\twhile queue:\n\t\t(x, y, l) = queue.popleft()\n\t\tif x == n - 1 and y == n - 1:\n\t\t\treturn l\n\t\tfor nextX in [x + a, x - a]:\n\t\t\tfor nextY in [y + b, y - b]:\n\t\t\t\tif 0 <= nextX < n and 0 <= nextY < n and (not (nextX, nextY) in visited):\n\t\t\t\t\tvisited.add((nextX, nextY))\n\t\t\t\t\tqueue.append((nextX, nextY, l + 1))\n\t\tfor nextX in [x + b, x - b]:\n\t\t\tfor nextY in [y + a, y - a]:\n\t\t\t\tif 0 <= nextX < n and 0 <= nextY < n and (not (nextX, nextY) in visited):\n\t\t\t\t\tvisited.add((nextX, nextY))\n\t\t\t\t\tqueue.append((nextX, nextY, l + 1))\n\treturn -1\nn = int(input().strip())\nfor a in range(1, n):\n\tfor b in range(1, n):\n\t\tprint(min_moves(n, a, b), end=' ')\n\tprint()\n", "from queue import PriorityQueue\n\ndef reach(i, j):\n\tseen = set()\n\tseen.add((0, 0))\n\tq = PriorityQueue()\n\tq.put((0, 0, 0))\n\twhile not q.empty():\n\t\t(p, curx, cury) = q.get()\n\t\tif curx == n - 1 and cury == n - 1:\n\t\t\treturn p\n\t\tif curx >= i and cury >= j and ((curx - i, cury - j) not in seen):\n\t\t\tq.put((p + 1, curx - i, cury - j))\n\t\t\tseen.add((curx - i, cury - j))\n\t\tif curx >= i and cury < n - j and ((curx - i, cury + j) not in seen):\n\t\t\tq.put((p + 1, curx - i, cury + j))\n\t\t\tseen.add((curx - i, cury + j))\n\t\tif curx >= j and cury >= i and ((curx - j, cury - i) not in seen):\n\t\t\tq.put((p + 1, curx - j, cury - i))\n\t\t\tseen.add((curx - j, cury - i))\n\t\tif curx >= j and cury < n - i and ((curx - j, cury + i) not in seen):\n\t\t\tq.put((p + 1, curx - j, cury + i))\n\t\t\tseen.add((curx - j, cury + i))\n\t\tif curx < n - i and cury >= j and ((curx + i, cury - j) not in seen):\n\t\t\tq.put((p + 1, curx + i, cury - j))\n\t\t\tseen.add((curx + i, cury - j))\n\t\tif curx < n - i and cury < n - j and ((curx + i, cury + j) not in seen):\n\t\t\tq.put((p + 1, curx + i, cury + j))\n\t\t\tseen.add((curx + i, cury + j))\n\t\tif curx < n - j and cury >= i and ((curx + j, cury - i) not in seen):\n\t\t\tq.put((p + 1, curx + j, cury - i))\n\t\t\tseen.add((curx + j, cury - i))\n\t\tif curx < n - j and cury < n - i and ((curx + j, cury + i) not in seen):\n\t\t\tq.put((p + 1, curx + j, cury + i))\n\t\t\tseen.add((curx + j, cury + i))\n\treturn -1\nn = int(input())\nfor i in range(1, n):\n\tfor j in range(1, n):\n\t\tprint(reach(i, j), end=' ')\n\tprint()\n", "import sys\nn = int(input().strip())\n\ndef allmoves(i, j, a, b, n):\n\tmoves = []\n\tdeltas = [(a, b), (a, -b), (-a, b), (-a, -b)]\n\tdeltas.extend([(b, a), (b, -a), (-b, a), (-b, -a)])\n\tfor delta in deltas:\n\t\tif i + delta[0] >= 0 and i + delta[0] < n and (j + delta[1] >= 0) and (j + delta[1] < n):\n\t\t\tmoves.append((i + delta[0], j + delta[1]))\n\treturn moves\n\ndef finddist(n, a, b):\n\tdist = [[-1 for x in range(n)] for x in range(n)]\n\tdist[n - 1][n - 1] = 0\n\ttodo = [(n - 1, n - 1)]\n\twhile len(todo) > 0:\n\t\t(i, j) = todo.pop(0)\n\t\tnewmoves = allmoves(i, j, a, b, n)\n\t\tfor move in newmoves:\n\t\t\tif dist[move[0]][move[1]] == -1:\n\t\t\t\tdist[move[0]][move[1]] = dist[i][j] + 1\n\t\t\t\ttodo.append((move[0], move[1]))\n\t\t\t\tif move[0] == 0 and move[1] == 0:\n\t\t\t\t\tbreak\n\treturn dist[0][0]\nans = [[0 for x in range(n - 1)] for x in range(n - 1)]\nfor i in range(n - 1):\n\tfor j in range(n - 1):\n\t\tans[i][j] = finddist(n, i + 1, j + 1)\nfor i in range(n - 1):\n\tprint(' '.join(map(str, ans[i])))\n", "import sys\nfrom collections import deque\n\ndef knight(n, a, b):\n\tM = [[-1] * n for i in range(n)]\n\tM[0][0] = 0\n\tqueue = deque([(0, 0)])\n\twhile queue:\n\t\t(x, y) = queue.popleft()\n\t\tfor i in [x - a, x + a]:\n\t\t\tfor j in [y - b, y + b]:\n\t\t\t\tif 0 <= i < n and 0 <= j < n and (M[i][j] == -1):\n\t\t\t\t\tM[i][j] = M[x][y] + 1\n\t\t\t\t\tqueue.append((i, j))\n\t\tfor i in [x - b, x + b]:\n\t\t\tfor j in [y - a, y + a]:\n\t\t\t\tif 0 <= i < n and 0 <= j < n and (M[i][j] == -1):\n\t\t\t\t\tM[i][j] = M[x][y] + 1\n\t\t\t\t\tqueue.append((i, j))\n\treturn M[n - 1][n - 1]\nn = int(input().strip())\nM = [[None] * (n - 1) for i in range(n - 1)]\nfor i in range(n - 1):\n\tfor j in range(i, n - 1):\n\t\tM[i][j] = M[j][i] = knight(n, i + 1, j + 1)\n\tprint(*M[i], sep=' ')\n", "import sys\nfrom collections import deque\n\ndef moves(i, j, k, l, n):\n\tresult = []\n\tresult.extend(((i0, j0) for i0 in (i - k, i + k) for j0 in (j - l, j + l) if 0 <= i0 < n and 0 <= j0 < n))\n\tresult.extend(((i0, j0) for i0 in (i - l, i + l) for j0 in (j - k, j + k) if 0 <= i0 < n and 0 <= j0 < n))\n\treturn result\n\ndef index(i, j, n):\n\treturn n * i + j\n\ndef pos(kk, n):\n\treturn (k // n, k % n)\n\ndef main():\n\tn = int(input().strip())\n\tmin_moves = [-1] * n ** 2\n\tfor k in range(1, n):\n\t\tfor l in range(k, n):\n\t\t\tboard = [-1] * n ** 2\n\t\t\tboard[0] = 0\n\t\t\tqueue = deque([(0, (0, 0))])\n\t\t\twhile queue and queue[-1][1] != (n - 1, n - 1):\n\t\t\t\t(nmoves, (i, j)) = queue.pop()\n\t\t\t\tnmoves += 1\n\t\t\t\tfor (i0, j0) in moves(i, j, k, l, n):\n\t\t\t\t\tind = index(i0, j0, n)\n\t\t\t\t\tif board[ind] < 0 or board[ind] > nmoves:\n\t\t\t\t\t\tboard[ind] = nmoves\n\t\t\t\t\t\tqueue.appendleft((nmoves, (i0, j0)))\n\t\t\tmin_moves[index(k, l, n)] = min_moves[index(l, k, n)] = board[index(n - 1, n - 1, n)]\n\tfor k in range(1, n):\n\t\tprint(*min_moves[k * n + 1:k * n + n])\nmain()\n", "import collections\nn = int(input())\ngrid = [[-1] * (n - 1) for i in range(n - 1)]\nfor i in range(1, n):\n\tfor j in range(i, n):\n\t\tseen = [[0] * n for i in range(n)]\n\t\tactive = collections.deque()\n\t\tactive.append((0, n - 1, n - 1))\n\t\twhile active:\n\t\t\t(s, x, y) = active.popleft()\n\t\t\tif x == 0 and y == 0:\n\t\t\t\tgrid[i - 1][j - 1] = s\n\t\t\t\tgrid[j - 1][i - 1] = s\n\t\t\t\tbreak\n\t\t\tif x < 0 or y < 0 or x >= n or (y >= n) or seen[y][x]:\n\t\t\t\tcontinue\n\t\t\tseen[y][x] = 1\n\t\t\tseen[x][y] = 1\n\t\t\ts += 1\n\t\t\tactive.extend([(s, x + i, y + j), (s, x + i, y - j), (s, x - i, y + j), (s, x - i, y - j), (s, x + j, y + i), (s, x + j, y - i), (s, x - j, y + i), (s, x - j, y - i)])\nfor row in grid:\n\tprint(' '.join([str(x) for x in row]))\n"]

difficulty: MEDIUM

source: hacker rank

skill_types: ['Complete search']

question:
$\textit{Knight L}$ is a chess piece that moves in an L shape. We define the possible moves of $\textit{Knight L}(a,b)$ as any movement from some position $(x_{1},y_{1})$ to some $(x_2,y_2)$ satisfying either of the following:

$x_2=x_1\pm a$ and $y_2=y_1\pm b$, or
$x_2=x_1\pm b$ and $y_2=y_1\pm a$

Note that $(a,b)$ and $(b,a)$ allow for the same exact set of movements. For example, the diagram below depicts the possible locations that $\textit{Knight L}(1,2)$ or $\textit{Knight L}(2,1)$ can move to from its current location at the center of a $5\times5$ chessboard:

![image](1.png)
Observe that for each possible movement, the Knight moves $2$ units in one direction (i.e., horizontal or vertical) and $\mbox{1}$ unit in the perpendicular direction.

Given the value of $n$ for an $n\times n$ chessboard, answer the following question for each $(a,b)$ pair where $1\leq a,b<n$:

What is the minimum number of moves it takes for $\textit{Knight L}(a,b)$ to get from position $(0,0)$ to position $(n-1,n-1)$? If it's not possible for the Knight to reach that destination, the answer is -1 instead.

Then print the answer for each $\textit{Knight L}(a,b)$ according to the Output Format specified below.

Input Format

A single integer denoting $n$.

Constraints

$5\leq n\leq25$

Output Format

Print exactly $n-1$ lines of output in which each line $\boldsymbol{i}$ (where $1\leq i\lt n$) contains $n-1$ space-separated integers describing the minimum number of moves $\textit{Knight L}(i,j)$ must make for each respective $j$ (where $1\leq j\lt n$). If some $\textit{Knight L}(i,j)$ cannot reach position $(n-1,n-1)$, print -1 instead.

For example, if $n=3$, we organize the answers for all the $(i,j)$ pairs in our output like this:

(1,1) (1,2)
(2,1) (2,2)

Sample Input 0
5

Sample Output 0
4 4 2 8
4 2 4 4
2 4 -1 -1
8 4 -1 1

Explanation 0

The diagram below depicts possible minimal paths for $\textit{Knight L}(1,1)$, $\textit{Knight L}(1,2)$, and $\textit{Knight L}(1,3)$:

![image](2.png)
One minimal path for $\textit{Knight}L(1,4)$ is: $(0,0)\to(1,4)\to(2,0)\to(3,4)\to(4,0)\to(0,1)\to(4,2)\to(0,3)\to(4,4)$

We then print 4 4 2 8 as our first line of output because $\textit{Knight L}(1,1)$ took $\begin{array}{c}A\end{array}$ moves, $\textit{Knight L}(1,2)$ took $\begin{array}{c}A\end{array}$ moves, $\textit{Knight L}(1,3)$ took $2$ moves, and $\textit{Knight}L(1,4)$ took $8$ moves.

In some of the later rows of output, it's impossible for $\textit{Knight L}(i,j)$ to reach position $(4,4)$. For example, $\textit{Knight L}(3,3)$ can only move back and forth between $(0,0)$ and $(3,3)$ so it will never reach $(4,4)$.

image_tags: Chessboard Chessboard

data_split: test