C. Colored Rooks

problem_index: C

time_limit: 1 second

memory_limit: 256 megabytes

note:
Rooks arrangements for all three examples (red is color $$$1$$$, green is color $$$2$$$ and blue is color $$$3$$$).
![image](images/cf_1068_C/1.png)
![image](images/cf_1068_C/2.png)
![image](images/cf_1068_C/3.png)

solutions: ["(cols, pairs) = [int(x) for x in input().split()]\nimport collections\nd = collections.defaultdict(list)\nfor _ in range(pairs):\n\t(a, b) = [int(x) for x in input().split()]\n\td[a].append(b)\nrooks = collections.defaultdict(list)\ncurrent_line = 1\nfor i in range(1, cols + 1):\n\trooks[i].append((i, current_line))\n\tcurrent_line += 1\n\tfor harmony in d[i]:\n\t\trooks[i].append((i, current_line))\n\t\trooks[harmony].append((harmony, current_line))\n\t\tcurrent_line += 1\nfor i in range(1, cols + 1):\n\tprint(len(rooks[i]))\n\tfor (a, b) in rooks[i]:\n\t\tprint(a, b)\n", "from typing import Dict, List\n(n_colors, len_pairs) = (int(val) for val in input().split())\ncolor_pairs = []\nfor i in range(len_pairs):\n\tcolor_pairs.append([int(val) for val in input().split()])\nres = []\ncur_x = 1\ncur_y = 1\nfor color in range(1, n_colors + 1):\n\tcur_color_res = []\n\tcur_color_res.append((cur_x, cur_y))\n\tcur_x += 1\n\tcur_y += 1\n\tres.append(cur_color_res)\nfor pair in color_pairs:\n\tres[pair[0] - 1].append((cur_x, cur_y))\n\tres[pair[0] - 1].append((cur_x, pair[0]))\n\tres[pair[1] - 1].append((cur_x, pair[1]))\n\tcur_x += 1\n\tcur_y += 1\nfor cur_res in res:\n\tprint(len(cur_res))\n\tfor el_cur_res in cur_res:\n\t\tprint('{} {}'.format(el_cur_res[0], el_cur_res[1]))\n", "(n, m) = [int(x) for x in input().split()]\nms = []\ncon = [set() for i in range(n)]\nloc = [0] * n\nfor i in range(m):\n\t(a, b) = [int(x) for x in input().split()]\n\ta -= 1\n\tb -= 1\n\tcon[a].add(b)\n\tcon[b].add(a)\n\tms.append((a, b))\nans = [[] for i in range(n)]\nif len(con[0]) == 0:\n\tcon[0].add(n + 10)\nl = len(con[0])\nans[0] = [i for i in range(l)]\nfor i in range(1, n):\n\tloc[i] = l\n\tif len(con[i]) == 0:\n\t\tcon[i].add(n + 10)\n\tfor s in con[i]:\n\t\tif s < i:\n\t\t\tans[i].append(loc[s])\n\t\t\tloc[s] += 1\n\t\telse:\n\t\t\tans[i].append(l)\n\t\t\tl += 1\nfor i in range(n):\n\tprint(len(ans[i]))\n\tfor s in ans[i]:\n\t\tprint(i + 1, s + 1)\n", "def main():\n\t(n, m) = map(int, input().split())\n\tarr = [[] for i in range(n + 1)]\n\tansw = [[] for i in range(n + 1)]\n\tx = 1\n\tfor i in range(m):\n\t\t(a, b) = map(int, input().split())\n\t\tarr[a].append([a, x])\n\t\tarr[b].append([b, x])\n\t\tx += 1\n\tfor i in range(1, n + 1):\n\t\tif not arr[i]:\n\t\t\tprint(1)\n\t\t\tprint(i, x)\n\t\t\tx += 1\n\t\telse:\n\t\t\tprint(len(arr[i]))\n\t\t\tfor j in arr[i]:\n\t\t\t\tprint(*j)\nmain()\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline()\n\ndef RL():\n\treturn map(int, sys.stdin.readline().split())\n\ndef RLL():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef N():\n\treturn int(input())\n\ndef print_list(l):\n\tprint(' '.join(map(str, l)))\n(n, m) = RL()\ndic = [[i] for i in range(n + 1)]\ncount = [1] * (n + 1)\nfor _ in range(m):\n\t(a, b) = RL()\n\tif a != b:\n\t\tdic[a].append(b)\n\t\tdic[b].append(a)\nfor i in range(1, n + 1):\n\tprint(len(dic[i]) + 1)\n\tprint(i, i)\n\tfor j in dic[i]:\n\t\tprint(i, min(i, j) * n + max(i, j))\n", "3\nimport math\nimport sys\nDEBUG = False\n\ndef inp():\n\treturn sys.stdin.readline().rstrip()\n\ndef dprint(*value, sep=' ', end='\\n'):\n\tif DEBUG:\n\t\tprint(*value, sep=sep, end=end)\n\ndef solve(N, M, A):\n\tans = [[] for _ in range(N)]\n\tfor i in range(1, N + 1):\n\t\tans[i - 1].append((i, i))\n\ty = N + 1\n\tfor a in range(1, N + 1):\n\t\tfor b in range(a + 1, N + 1):\n\t\t\tif A[a][b] == 1:\n\t\t\t\tans[a - 1].append((a, y))\n\t\t\t\tans[b - 1].append((b, y))\n\t\t\t\ty += 1\n\treturn ans\n\ndef main():\n\t(N, M) = [int(e) for e in inp().split()]\n\tA = [bytearray(N + 1) for _ in range(N + 1)]\n\tfor _ in range(M):\n\t\t(a, b) = [int(e) for e in inp().split()]\n\t\tA[a][b] = 1\n\t\tA[b][a] = 1\n\tans = solve(N, M, A)\n\tassert len(ans) == N\n\tfor coords in ans:\n\t\tprint(len(coords))\n\t\tfor (x, y) in coords:\n\t\t\tprint(x, y)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "(n, m) = [int(el) for el in input().split()]\npair = []\nkol = {i: 1 for i in range(1, n + 1)}\nfor i in range(m):\n\t(q, w) = [int(el) for el in input().split()]\n\tif q < w:\n\t\tpair.append((q, w))\n\telse:\n\t\t(q, w) = (w, q)\n\t\tpair.append((q, w))\n\tkol[q] += 1\n\tkol[w] += 1\npair.sort()\nmazy = []\nfor i in range(1, n + 1):\n\tmazy.append((i, i, i))\nfor i in pair:\n\tmazy.append((i[0], 10000 * i[1] + i[0], i[0]))\n\tmazy.append((i[1], 10000 * i[1] + i[0], i[1]))\nmazy.sort()\ncur = 1\nprint(kol[1])\nwhile mazy != []:\n\tq = mazy.pop(0)\n\tif q[0] == cur:\n\t\tprint(q[1], q[0])\n\telse:\n\t\tprint(kol[q[0]])\n\t\tprint(q[1], q[0])\n\t\tcur = q[0]\n", "from collections import defaultdict\n(n, m) = list(map(int, input().split()))\npairs = defaultdict(set)\nfor _ in range(m):\n\t(l, r) = list(map(int, input().split()))\n\tpairs[l - 1].add(r - 1)\n\tpairs[r - 1].add(l - 1)\nanswers = defaultdict(list)\nfree_rooks = defaultdict(int)\ny = 1\nfor color in range(n):\n\tfree_rooks[color] = y\n\tfor c in pairs[color]:\n\t\tif c < color:\n\t\t\tanswers[color].append((color + 1, free_rooks[c]))\n\t\t\tfree_rooks[c] += 1\n\t\telse:\n\t\t\tanswers[color].append((color + 1, y))\n\t\t\ty += 1\n\tanswers[color].append((color + 1, y))\n\ty += 1\nfor color in range(n):\n\tprint(len(answers[color]))\n\tfor (x, y) in answers[color]:\n\t\tprint(x, y)\n", "(n, m) = map(int, input().split())\na = []\nfor i in range(n):\n\ta.append([[i * n, i * n]])\nfor i in range(m):\n\t(x, y) = map(int, input().split())\n\tx -= 1\n\ty -= 1\n\tif x > y:\n\t\t(x, y) = (y, x)\n\ta[x].append([x * n, x * n + y])\n\ta[y].append([y * n, x * n + y])\nfor i in range(n):\n\tprint(len(a[i]))\n\tfor j in a[i]:\n\t\tprint(j[0] + 1, j[1] + 1)\n", "(n, m) = list(map(int, input().split()))\nt = [[] for i in range(n)]\ncid = 1\nfor i in range(n):\n\tt[i].append(cid)\n\tcid += 1\nfor i in range(m):\n\t(a, b) = list(map(int, input().split()))\n\tt[a - 1].append(cid)\n\tt[b - 1].append(cid)\n\tcid += 1\nfor i in range(n):\n\tprint(len(t[i]))\n\tfor j in t[i]:\n\t\tprint(i + 1, j)\n", "(n, m) = map(int, input().split())\nd = {}\nconn = {}\npos = {}\nfor i in range(m):\n\tnew = list(map(int, input().split()))\n\tnew.sort()\n\td[new[0]] = d.get(new[0], 0) + 1\n\tconn[new[0]] = conn.get(new[0], []) + [new[1]]\n(x, y) = (1, 1)\nfor colour in d:\n\ty = colour\n\ttmpx = x\n\tfor i in range(d[colour]):\n\t\tpos[colour] = pos.get(colour, []) + [(x, y)]\n\t\tx += 1\n\tfor i in conn[colour]:\n\t\tpos[i] = pos.get(i, []) + [(tmpx, y + i - colour)]\n\t\ttmpx += 1\nbase = 10 ** 8\nfor i in range(1, n + 1):\n\tif i in pos:\n\t\tprint(len(pos[i]))\n\t\tfor j in pos[i]:\n\t\t\tprint(*j)\n\telse:\n\t\tprint(1)\n\t\tprint(base, i)\n\t\tbase += 1\n", "(n, m) = map(int, input().split())\na = {q: [] for q in range(1, n + 1)}\nfor q in range(m):\n\t(x, y) = map(int, input().split())\n\ta[min(x, y)].append(max(y, x))\na = {q: sorted(a[q]) for q in range(1, n + 1)}\nanswer = [[] for q in range(1, n + 1)]\nq2 = 1\nfor q in range(1, n + 1):\n\tfor q1 in a[q]:\n\t\tanswer[q1 - 1].append(q2)\n\t\tanswer[q - 1].append(q2)\n\t\tq2 += 1\n\tanswer[q - 1].append(q2)\n\tq2 += 1\nfor q in range(n):\n\tprint(len(answer[q]))\n\tfor q1 in answer[q]:\n\t\tprint(q + 1, q1)\n", "import sys\n\ndef main():\n\tinput = sys.stdin.readline\n\t(N, M) = map(int, input().split())\n\tP = sorted([tuple(map(int, input().split())) for _ in range(M)])\n\tA = [[] for _ in range(N)]\n\ty = 1\n\tfor (c1, c2) in P:\n\t\tA[c1 - 1].append((c1, y))\n\t\tA[c2 - 1].append((c2, y))\n\t\ty += 1\n\tfor (c, ai) in enumerate(A):\n\t\tif ai:\n\t\t\tprint(len(ai))\n\t\t\tfor a in ai:\n\t\t\t\tprint(*a)\n\t\telse:\n\t\t\tprint(1)\n\t\t\tprint(c + 1, y)\n\t\t\ty += 1\nmain()\n", "(n, m) = map(int, input().split())\nr = [[] for a in range(n)]\nleft = 0\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\tr[a - 1].append(left)\n\tr[b - 1].append(left)\n\tleft += 1\nfor i in range(n):\n\tif len(r[i]) == 0:\n\t\tr[i].append(left)\n\t\tleft += 1\n\tl = len(r[i])\n\tprint(l)\n\tfor j in range(l):\n\t\tprint(i + 1, r[i][j] + 1)\n", "from collections import namedtuple\nCell = namedtuple('Cell', ['row', 'col'])\n(n, m) = map(int, input().split())\nrooks = {}\nrow = 1\ncol = 1\nfor i in range(1, m + 1):\n\t(a, b) = map(int, input().split())\n\tif a not in rooks and b not in rooks:\n\t\trooks[a] = [Cell(row=row, col=col)]\n\t\trooks[b] = [Cell(row=row, col=col + 1)]\n\t\trow += 1\n\t\tcol += 2\n\telif a in rooks and b in rooks:\n\t\tlast_a = rooks[a][-1]\n\t\tlast_b = rooks[b][-1]\n\t\trooks[a].append(Cell(row=row, col=last_a.col))\n\t\trooks[b].append(Cell(row=row, col=last_b.col))\n\t\trow += 1\n\telse:\n\t\tif b in rooks:\n\t\t\t(a, b) = (b, a)\n\t\tlast_a = rooks[a][-1]\n\t\trooks[a].append(Cell(row=row, col=last_a.col))\n\t\trooks[b] = [Cell(row=row, col=col)]\n\t\trow += 1\n\t\tcol += 1\nfor i in range(1, n + 1):\n\tif i not in rooks:\n\t\trooks[i] = [Cell(row=row, col=col)]\n\t\trow += 1\n\t\tcol += 1\nfor i in range(1, n + 1):\n\tif i not in rooks:\n\t\tprint(0)\n\telse:\n\t\tcells = rooks[i]\n\t\tprint(len(cells))\n\t\tfor cell in cells:\n\t\t\tprint(cell.row, cell.col)\n", "import math\n(n, m) = list(map(int, input().split()))\nhs = []\nfor _ in range(m):\n\t(a, b) = list(map(int, input().split()))\n\ta -= 1\n\tb -= 1\n\ths.append((min(a, b), max(a, b)))\nused = [0] * n\nplaced = [[] for _ in range(n)]\nfor (a, b) in hs:\n\tplaced[a].append(b * n + used[b])\n\tused[b] += 1\nfor i in range(n):\n\tprint(max(1, used[i]) + len(placed[i]))\n\tfor j in range(max(1, used[i])):\n\t\tprint(i * n + j + 1, i + 1)\n\tfor j in placed[i]:\n\t\tprint(j + 1, i + 1)\n", "import os\nimport sys\nimport math\nfrom io import BytesIO, IOBase\nfrom fractions import Fraction\nimport collections\nfrom itertools import permutations\nfrom collections import defaultdict\nimport threading\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n(n, m) = map(int, input().split())\na = [[] for i in range(n)]\nfor i in range(n):\n\ta[i].append((i + 1, i + 1))\nc = n + 1\nfor i in range(m):\n\t(x, y) = map(int, input().split())\n\ta[x - 1].append((x, c))\n\ta[y - 1].append((y, c))\n\tc += 1\nfor i in a:\n\tprint(len(i))\n\tfor j in range(len(i)):\n\t\tprint(*i[j])\n", "(n, m) = [int(x) for x in input().strip().split(' ')]\ndata = [[] for _ in range(105)]\nfor i in range(1, m + 1):\n\t(a, b) = [int(x) for x in input().strip().split(' ')]\n\tdata[a].append((a, a * n + b))\n\tdata[b].append((b, a * n + b))\nfor i in range(1, n + 1):\n\tprint(len(data[i]) + 1)\n\tprint(i, i)\n\tfor (a, b) in data[i]:\n\t\tprint(a, b)\n", "from sys import stdin, stdout\nfrom math import sin, tan, cos\n(n, m) = map(int, stdin.readline().split())\nvertices = [[] for i in range(n + 1)]\ncnt = [1 for i in range(n + 1)]\nstring = [0 for i in range(n + 1)]\nfor i in range(m):\n\t(a, b) = map(int, stdin.readline().split())\n\tif a < b:\n\t\t(a, b) = (b, a)\n\tvertices[a].append(b)\n\tcnt[b] += 1\npositions = {}\ncur = [1, 1]\nfor i in range(1, n + 1):\n\tpositions[i] = []\n\tfor j in range(cnt[i] - 1):\n\t\tpositions[i].append(cur[:])\n\t\tcur[1] = cur[1] + 1\n\t\tpositions[i].append(cur[:])\n\t\tcur[0] = cur[0] + 1\n\tpositions[i].append(cur[:])\n\tstring[i] = cur[0]\n\tcur[0] = cur[0] + 1\n\tcur[1] = cur[1] + 1\nfor i in range(1, n + 1):\n\tfor v in vertices[i]:\n\t\tpositions[i].append([string[v], string[i]])\n\t\tstring[v] -= 1\ncnt = 0\nfor i in range(1, n + 1):\n\tstdout.write(str(len(positions[i])) + '\\n')\n\tfor v in positions[i]:\n\t\tcnt += 1\n\t\tif cnt > 5000:\n\t\t\twhile True:\n\t\t\t\tcnt += 1\n\t\tstdout.write(str(v[0]) + ' ' + str(v[1]) + '\\n')\n", "from collections import defaultdict\n\ndef read():\n\treturn [int(v) for v in input().split()]\n\ndef main():\n\t(n, m) = read()\n\tc = defaultdict(list)\n\tfor i in range(1, n + 1):\n\t\tc[i].append((i, i))\n\tfor i in range(1, m + 1):\n\t\tcolors = read()\n\t\tc[colors[0]].append((100 + 2 * i, colors[0] * 1000 + colors[1]))\n\t\tc[colors[0]].append((100 + 2 * i, colors[0]))\n\t\tc[colors[1]].append((100 + 2 * i + 1, colors[0] * 1000 + colors[1]))\n\t\tc[colors[1]].append((100 + 2 * i + 1, colors[1]))\n\tfor i in range(1, n + 1):\n\t\tprint(len(c[i]))\n\t\tfor v in c[i]:\n\t\t\tprint(v[0], v[1])\nmain()\n", "a = list(map(int, input().split()))\nn = a[0]\nm = a[1]\nb = list()\nfor j in range(m):\n\tb.append(list(map(int, input().split())))\nans = [] * n\nfor i in range(n):\n\tans.append([])\nfor j in range(n):\n\tans[j].append([j + 1, j + 1])\nfree = n + 1\nfor j in range(m):\n\tx = b[j][0]\n\ty = b[j][1]\n\tans[x - 1].append([x, free])\n\tans[y - 1].append([y, free])\n\tfree = free + 1\nfor j in range(n):\n\tprint(len(ans[j]))\n\tfor i in range(len(ans[j])):\n\t\tprint(ans[j][i][0], ans[j][i][1], sep=' ')\n", "s = input().split()\nn = int(s[0])\nm = int(s[1])\ncol = []\nfor i in range(n):\n\tcol.append([i])\nt = n + 1\nfor i in range(m):\n\ts = input().split()\n\ta = int(s[0]) - 1\n\tb = int(s[1]) - 1\n\tcol[a].append(t)\n\tcol[b].append(t)\n\tt += 1\nfor i in range(len(col)):\n\tprint(len(col[i]))\n\tfor j in range(len(col[i])):\n\t\tprint(i + 1, col[i][j] + 1)\n", "(n, m) = map(int, input().split())\nSAME = [list(map(int, input().split())) for i in range(m)]\nC = [[] for i in range(n + 1)]\nfor i in range(len(SAME)):\n\tC[SAME[i][0]].append((i, 2 * i))\n\tC[SAME[i][1]].append((i, 2 * i + 1))\nCONE = [[] for i in range(n + 1)]\nfor i in range(1, n + 1):\n\tfor j in C[i]:\n\t\tCONE[i].append((1001 + i, j[1]))\nfor i in range(1, n + 1):\n\tCONE[i].append((1001 + i, 100000 + i))\nfor i in range(1, n + 1):\n\tprint(len(C[i]) + len(CONE[i]))\n\tfor (j, k) in C[i]:\n\t\tprint(j + 1, k + 1)\n\tfor (j, k) in CONE[i]:\n\t\tprint(j + 1, k + 1)\n", "import sys\n\ndef rint():\n\treturn map(int, sys.stdin.readline().split())\n(n, m) = rint()\nhca = []\nfor i in range(m):\n\t(c1, c2) = rint()\n\thca.append([c1, c2])\npoc = [[] for i in range(n + 1)]\nfor i in range(1, m + 1):\n\t(c1, c2) = hca[i - 1]\n\tpoc[c1].append([c1, i])\n\tpoc[c2].append([c2, i])\nj = m + 1\nfor i in range(1, n + 1):\n\tif len(poc[i]) == 0:\n\t\tpoc[i].append([i, j])\n\t\tj += 1\nfor i in range(1, n + 1):\n\tprint(len(poc[i]))\n\tfor (x, y) in poc[i]:\n\t\tprint(x, y)\n", "(n, m) = map(int, input().split())\nout = [[] for i in range(n)]\nfor i in range(n):\n\tout[i].append((i + 1, i + 1))\ncurr = n + 100\nfor j in range(m):\n\t(a, b) = map(int, input().split())\n\tout[a - 1].append((a, curr))\n\tout[b - 1].append((b, curr))\n\tcurr += 1\nfor l in out:\n\tprint(len(l))\n\tfor (a, b) in l:\n\t\tprint(a, b)\n", "def main():\n\t(n, m) = map(int, input().split())\n\trooks = [[(i, i)] for i in range(n)]\n\tedges = (tuple(map(int, input().split())) for _ in range(m))\n\tcounter = n\n\tfor (a, b) in edges:\n\t\ta -= 1\n\t\tb -= 1\n\t\trooks[a].append((a, counter))\n\t\trooks[b].append((b, counter))\n\t\tcounter += 1\n\tfor i in range(n):\n\t\tprint(len(rooks[i]))\n\t\tfor (x, y) in rooks[i]:\n\t\t\tprint(x + 1, y + 1, sep=' ')\nmain()\n", "import os\nimport sys\nfrom math import *\nfrom collections import *\nfrom fractions import *\nfrom bisect import *\nfrom heapq import *\nfrom io import BytesIO, IOBase\n\ndef vsInput():\n\tsys.stdin = open('input.txt', 'r')\n\tsys.stdout = open('output.txt', 'w')\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nALPHA = 'abcdefghijklmnopqrstuvwxyz'\nMOD = 1000000007\n\ndef value():\n\treturn tuple(map(int, input().split()))\n\ndef array():\n\treturn [int(i) for i in input().split()]\n\ndef Int():\n\treturn int(input())\n\ndef Str():\n\treturn input()\n\ndef arrayS():\n\treturn [i for i in input().split()]\n(n, m) = value()\nans = defaultdict(list)\nfor i in range(n):\n\tans[i + 1].append((i + 1, i + 1))\nk = n + 1\nfor i in range(m):\n\t(x, y) = value()\n\tans[x].append((k, x))\n\tans[y].append((k, y))\n\tk += 1\nfor i in range(1, n + 1):\n\tprint(len(ans[i]))\n\tfor j in ans[i]:\n\t\tprint(*j)\n", "(n, m) = map(int, input().split())\na = []\nfor i in range(n):\n\ta.append([])\n\ta[i].append([i, i])\nc = n\nfor i in range(m):\n\t(c1, c2) = map(int, input().split())\n\ta[c1 - 1].append([c1 - 1, c])\n\ta[c2 - 1].append([c2 - 1, c])\n\tc += 1\nfor z in a:\n\tprint(len(z))\n\tfor t in z:\n\t\tprint(t[0] + 1, t[1] + 1)\n", "(n, m) = map(int, input().split())\narr = []\nfor i in range(m):\n\t(x, y) = map(int, input().split())\n\tarr.append([x, y])\ndict1 = {}\nk = 1\nfor i in range(m):\n\ta = arr[i][0]\n\tb = arr[i][1]\n\ttry:\n\t\tdict1[a].append((k, a))\n\texcept:\n\t\tdict1[a] = [(k, a)]\n\ttry:\n\t\tdict1[b].append((k, b))\n\texcept:\n\t\tKeyError\n\t\tdict1[b] = [(k, b)]\n\tk += 1\nfor i in range(1, n + 1):\n\ttry:\n\t\tz = len(dict1[i])\n\texcept:\n\t\tKeyError\n\t\tdict1[i] = [(k, i)]\n\t\tk += 1\nfor i in range(1, n + 1):\n\tprint(len(dict1[i]))\n\tfor j in dict1[i]:\n\t\tprint(j[0], j[1])\n", "(n, m) = map(int, input().split())\nd = {}\nfor i in range(1, n + 1):\n\td[i] = set()\nfor i in range(m):\n\t(x, y) = map(int, input().split())\n\td[x].add(x * n + y)\n\td[y].add(x * n + y)\nfor i in range(1, n + 1):\n\tprint(len(d[i]) + 1)\n\tprint(i, i)\n\tfor k in d[i]:\n\t\tprint(i, k)\n", "(n, m) = map(int, input().split())\na = [[] for i in range(n + 1)]\nfor i in range(m):\n\t(loc1, loc2) = map(int, input().split())\n\ta[loc1].append(loc2)\n\ta[loc2].append(loc1)\nk = 1\ncvaz = [0] * (n + 1)\nfor i in range(1, n + 1):\n\tl = len(a[i])\n\tprint(l + 1)\n\tprint(i, k)\n\tk += 1\n\tcvaz[i] = k\n\tfor j in range(l):\n\t\tif a[i][j] > i:\n\t\t\tprint(i, k)\n\t\t\tk += 1\n\t\telse:\n\t\t\tprint(i, cvaz[a[i][j]])\n\t\t\tcvaz[a[i][j]] += 1\n", "(n, m) = map(int, input().split())\nans = [[] for i in range(n)]\nfor i in range(n):\n\tans[i].append((i + 1, i + 1))\ng = [set() for i in range(n)]\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\t(a, b) = (a - 1, b - 1)\n\tans[a].append((101 + i, a + 1))\n\tans[b].append((101 + i, b + 1))\nfor i in range(n):\n\tprint(len(ans[i]))\n\tfor j in range(len(ans[i])):\n\t\tprint(*ans[i][j])\n", "(n, m) = map(int, input().split())\nans = [[[i, i]] for i in range(n + 1)]\nj = n + 2\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\ts1 = [j, a]\n\ts2 = [j, b]\n\tans[a].append(s1)\n\tans[b].append(s2)\n\tj += 1\nfor i in range(1, n + 1):\n\tprint(len(ans[i]))\n\tfor j in ans[i]:\n\t\tprint(j[0], j[1])\n", "(n, m) = map(int, input().split())\ncolor_pairs = [list(map(int, input().split())) for i in range(m)]\ntowers = [[(i, i)] for i in range(1, n + 1)]\nlast_coord = n + 1\nfor (c1, c2) in color_pairs:\n\ttowers[c1 - 1].append((last_coord, c1))\n\ttowers[c2 - 1].append((last_coord, c2))\n\tlast_coord += 1\nfor i in range(len(towers)):\n\tprint(len(towers[i]))\n\tfor (x, y) in towers[i]:\n\t\tprint(x, y)\n", "from collections import Counter\n(n, m) = [int(val) for val in input().split()]\nharmony = [set([]) for i in range(n)]\nfor i in range(m):\n\t(a, b) = [int(val) for val in input().split()]\n\ta -= 1\n\tb -= 1\n\tharmony[a].add(b)\n\tharmony[b].add(a)\npos = [[] for i in range(n)]\nv = 1\nvertical_positions = {}\nfor i in range(n):\n\ts = harmony[i]\n\tcount = len(s)\n\tvertical_positions[i] = set([])\n\tif count == 0:\n\t\tvertical_positions[i].add(v)\n\t\tpos[i].append((i + 1, v))\n\t\tv += 1\n\telse:\n\t\tfor color in s:\n\t\t\tif color < i:\n\t\t\t\tval = vertical_positions[color].pop()\n\t\t\t\tpos[i].append((i + 1, val))\n\t\t\telse:\n\t\t\t\tvertical_positions[i].add(v)\n\t\t\t\tpos[i].append((i + 1, v))\n\t\t\t\tv += 1\nfor i in pos:\n\tprint(len(i))\n\tfor j in i:\n\t\tprint(j[0], j[1])\n", "import sys\nfin = sys.stdin.readline\n(n, m) = [int(elem) for elem in input().split(' ')]\nharmonies = [[int(elem) for elem in fin().split(' ')] for _ in range(m)]\ncoords = {i: [(i, i)] for i in range(1, n + 1)}\nfor (i, (color1, color2)) in enumerate(harmonies, start=n + 1):\n\tcoords[color1].append((color1, i))\n\tcoords[color2].append((color2, i))\nfor i in range(1, n + 1):\n\tcoords_each_color = coords[i]\n\tprint(len(coords_each_color))\n\tfor coord in coords_each_color:\n\t\tprint(coord[0], coord[1])\n", "(N, M) = map(int, input().split())\nans = [(0, 0)] + [[(i + 1, i + 10000)] for i in range(N)]\ny = 9999\nfor mi in range(M):\n\t(u, v) = map(int, input().split())\n\tans[u].append((u, y))\n\tans[v].append((v, y))\n\ty -= 1\nfor i in range(1, N + 1):\n\tprint(len(ans[i]))\n\tfor (x, y) in ans[i]:\n\t\tprint('{} {}'.format(x, y))\n", "from collections import defaultdict\n\ndef compute(n, col_pairs):\n\tpos = defaultdict(list)\n\tres = defaultdict(list)\n\tfor i in range(1, n + 1):\n\t\tpos[i].append((i, i))\n\tfor (i, (u, v)) in enumerate(col_pairs, 1):\n\t\tres[u].append((u, n + i))\n\t\tres[v].append((v, n + i))\n\tfor i in range(1, n + 1):\n\t\tif not res[i]:\n\t\t\tprint(1)\n\t\t\tprint(i, i)\n\t\telse:\n\t\t\tprint(len(res[i]))\n\t\t\tfor (p1, p2) in res[i]:\n\t\t\t\tprint(p1, p2)\n\ndef run():\n\t(n, m) = [int(c) for c in input().split()]\n\tcol_pairs = []\n\tfor _ in range(m):\n\t\t(col1, col2) = [int(c) for c in input().split()]\n\t\tcol_pairs.append((col1, col2))\n\tcompute(n, col_pairs)\nrun()\n", "(n, m) = map(int, input().split())\nans = [(i + 1, i + 1) for i in range(n)]\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\tans += [(n + i + 1, a), (n + i + 1, b)]\nfor color in range(n):\n\tls = []\n\tfor (a, b) in ans:\n\t\tif color + 1 == b:\n\t\t\tls += [(a, b)]\n\tprint(len(ls))\n\tfor (a, b) in ls:\n\t\tprint(a, b)\n", "from collections import defaultdict\n(n, m) = map(int, input().split())\nd = defaultdict(list)\nfor i in range(1, n + 1):\n\td[i].append((i, i))\ncur = n + 1\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\td[a].append((cur, a))\n\td[b].append((cur, b))\n\tcur += 1\nfor i in d:\n\tprint(len(d[i]))\n\tfor j in d[i]:\n\t\tprint(*j)\n", "from sys import stdin, stdout\nint_in = lambda : int(stdin.readline())\narr_in = lambda : [int(x) for x in stdin.readline().split()]\nmat_in = lambda rows: [arr_in() for y in range(rows)]\nstr_in = lambda : stdin.readline().strip()\nout = lambda o: stdout.write('{}\\n'.format(o))\narr_out = lambda o: out(' '.join(map(str, o)))\nbool_out = lambda o: out('YES' if o else 'NO')\ntests = lambda : range(1, int_in() + 1)\ncase_out = lambda i, o: out('Case #{}: {}'.format(i, o))\n\ndef solve(n, color_pairs):\n\tresult = {}\n\tfor i in range(1, n + 1):\n\t\tresult[i] = [[i, i]]\n\ti = n + 1\n\tfor p in color_pairs:\n\t\tresult[p[0]].append([i, p[0]])\n\t\tresult[p[1]].append([i, p[1]])\n\t\ti += 1\n\treturn result\n(n, m) = arr_in()\ncolor_pairs = mat_in(m)\nresult = solve(n, color_pairs)\nfor key in range(1, n + 1):\n\tout(len(result[key]))\n\tfor item in result[key]:\n\t\tarr_out(item)\n", "(n, m) = map(int, input().split())\nedges = [[] for _ in range(n)]\nfor (edge_id, i) in enumerate(range(m)):\n\t(a, b) = map(int, input().split())\n\tedges[a - 1].append((b - 1, edge_id))\n\tedges[b - 1].append((a - 1, edge_id))\ncnt = 0\nans = [[] for _ in range(n)]\nfor i in range(n):\n\tfor (j, (node, edge_id)) in enumerate(edges[i]):\n\t\tcnt += 1\n\t\tans[i].append((cnt, i + 1))\n\t\tans[i].append((cnt, n + 1 + edge_id))\n\tif len(edges[i]) == 0:\n\t\tcnt += 1\n\t\tans[i].append((cnt, i + 1))\nprint('\\n'.join(('%d\\n' % len(color) + '\\n'.join(('%d %d' % (x, y) for (x, y) in color)) for color in ans)))\n", "ans = [[] for i in range(1, 103)]\n(U, V) = ([0 for i in range(1, 1003)], [0 for i in range(1, 1003)])\n(n, m) = map(int, input().split())\nfor i in range(0, m):\n\t(u, v) = map(int, input().split())\n\tans[u].append([u, i + n + 1])\n\tans[v].append([v, i + n + 1])\nfor i in range(1, n + 1):\n\tans[i] = ans[i] + [[i, i]]\nfor i in range(1, n + 1):\n\tprint(len(ans[i]))\n\tfor it in ans[i]:\n\t\tprint(it[0], it[1])\n", "import sys\ninput = sys.stdin.readline\n\ndef gcd(a, b):\n\tif a == 0:\n\t\treturn b\n\treturn gcd(b % a, a)\n\ndef lcm(a, b):\n\treturn a * b / gcd(a, b)\nmod = 10 ** 9 + 7\n\ndef main():\n\t(n, m) = map(int, input().split())\n\tharms = []\n\tfor i in range(m):\n\t\tharms.append(list(map(int, input().split())))\n\tharms.sort()\n\tans = []\n\tfor i in range(n + 1):\n\t\tans.append([[i, i]])\n\tj = 0\n\tc = 1\n\tfor i in range(1, n + 1):\n\t\twhile j < len(harms) and harms[j][0] == i:\n\t\t\tans[i].append([n + c, i])\n\t\t\tans[harms[j][1]].append([n + c, harms[j][1]])\n\t\t\tj += 1\n\t\t\tc += 1\n\tfor i in range(1, n + 1):\n\t\tprint(len(ans[i]))\n\t\tfor j in ans[i]:\n\t\t\tprint(*j)\nmain()\n", "(n, m) = input().split(' ')\n(n, m) = (int(n), int(m))\nL = []\nM = []\nfor i in range(101):\n\tL.append([])\n\tM.append([])\nfor i in range(m):\n\t(x, y) = input().split(' ')\n\t(x, y) = (int(x), int(y))\n\tif x > y:\n\t\tz = x\n\t\tx = y\n\t\ty = z\n\tL[x].append(y)\nk = 1\nfor i in range(1, n + 1):\n\tif len(L[i]) == 0:\n\t\tM[i].append(k)\n\t\tk += 1\n\telse:\n\t\tfor j in range(len(L[i])):\n\t\t\tM[i].append(k)\n\t\t\tM[L[i][j]].append(k)\n\t\t\tk += 1\nfor i in range(1, n + 1):\n\tprint(len(M[i]))\n\tfor j in range(len(M[i])):\n\t\tprint(M[i][j], end=' ')\n\t\tprint(i)\n", "from collections import defaultdict\n\ndef main():\n\t(n, m) = [int(c) for c in input().split()]\n\tpos = defaultdict(list)\n\tfor i in range(1, m + 1):\n\t\t(first, second) = [int(c) for c in input().split()]\n\t\tpos[first].append((first, n + i))\n\t\tpos[second].append((second, n + i))\n\tfor i in range(1, n + 1):\n\t\tif not pos[i]:\n\t\t\tpos[i].append((i, i))\n\t\tprint(len(pos[i]))\n\t\tfor (p1, p2) in pos[i]:\n\t\t\tprint(p1, p2)\nmain()\n", "(n, m) = map(int, input().split())\nans = [[(i, i)] for i in range(n)]\nk = n\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\tans[a - 1].append((a - 1, k))\n\tans[b - 1].append((b - 1, k))\n\tk += 1\nfor i in ans:\n\tprint(len(i))\n\tfor j in i:\n\t\tprint(j[0] + 1, j[1] + 1)\n", "from math import *\n(n, m) = map(int, input().split())\nref = {i: set() for i in range(1, n + 1)}\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\tref[a].add(a * n + b)\n\tref[b].add(a * n + b)\nfor i in range(1, n + 1):\n\ty = len(ref[i]) + 1\n\tprint(y)\n\tprint(i, i)\n\tfor j in ref[i]:\n\t\tprint(i, j)\n", "(n, m) = [int(x) for x in input().split(' ')]\npositions_collection = []\nfor i in range(n):\n\tpositions_collection.append([(i, i)])\nfor i in range(m):\n\t(f, t) = [int(x) - 1 for x in input().split(' ')]\n\tpositions_collection[f].append((f, n + i))\n\tpositions_collection[t].append((t, n + i))\nfor (e, q) in enumerate(positions_collection):\n\tprint(len(q))\n\tfor (c1, c2) in q:\n\t\tprint(c1 + 1, c2 + 1)\n", "(n, m) = [int(i) for i in input().split()]\nharmonies = []\nfor i in range(m):\n\tharmonies.append([int(i) for i in input().split()])\nrooks_by_colour = [[] for i in range(n + 1)]\nfor i in range(1, n + 1):\n\trooks_by_colour[i].append((i, i))\nnext_row = n + 1\nfor harmony in harmonies:\n\t(colour1, colour2) = harmony\n\trooks_by_colour[colour1].append((next_row, colour1))\n\trooks_by_colour[colour2].append((next_row, colour2))\n\tnext_row += 1\nfor i in range(1, n + 1):\n\tprint(len(rooks_by_colour[i]))\n\tfor i in rooks_by_colour[i]:\n\t\tprint(i[0], i[1])\n", "(n, m) = map(int, input().split())\nj = 0\nlis = [[] for i in range(n)]\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\tlis[a - 1].append(j + 1)\n\tlis[b - 1].append(j + 1)\n\tj += 1\nfor pos in range(n):\n\tif len(lis[pos]) > 0:\n\t\tprint(len(lis[pos]))\n\t\tfor i in lis[pos]:\n\t\t\tprint(str(i), str(pos + 1))\n\telse:\n\t\tprint(1)\n\t\tprint(j + 1, pos + 1)\n\t\tj += 1\n", "import math\nimport heapq, bisect\nimport sys\nfrom collections import deque, defaultdict\nfrom fractions import Fraction\nimport sys\nmod = 10 ** 9 + 7\nmod1 = 998244353\nimport os\nimport sys\nfrom io import BytesIO, IOBase\nBUFSIZE = 8192\n\nclass FastIO(IOBase):\n\tnewlines = 0\n\n\tdef __init__(self, file):\n\t\tself._fd = file.fileno()\n\t\tself.buffer = BytesIO()\n\t\tself.writable = 'x' in file.mode or 'r' not in file.mode\n\t\tself.write = self.buffer.write if self.writable else None\n\n\tdef read(self):\n\t\twhile True:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tif not b:\n\t\t\t\tbreak\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines = 0\n\t\treturn self.buffer.read()\n\n\tdef readline(self):\n\t\twhile self.newlines == 0:\n\t\t\tb = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))\n\t\t\tself.newlines = b.count(b'\\n') + (not b)\n\t\t\tptr = self.buffer.tell()\n\t\t\t(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))\n\t\tself.newlines -= 1\n\t\treturn self.buffer.readline()\n\n\tdef flush(self):\n\t\tif self.writable:\n\t\t\tos.write(self._fd, self.buffer.getvalue())\n\t\t\t(self.buffer.truncate(0), self.buffer.seek(0))\n\nclass IOWrapper(IOBase):\n\n\tdef __init__(self, file):\n\t\tself.buffer = FastIO(file)\n\t\tself.flush = self.buffer.flush\n\t\tself.writable = self.buffer.writable\n\t\tself.write = lambda s: self.buffer.write(s.encode('ascii'))\n\t\tself.read = lambda : self.buffer.read().decode('ascii')\n\t\tself.readline = lambda : self.buffer.readline().decode('ascii')\n(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\n\nclass TreeNode:\n\n\tdef __init__(self, k, v):\n\t\tself.key = k\n\t\tself.value = v\n\t\tself.left = None\n\t\tself.right = None\n\t\tself.parent = None\n\t\tself.height = 1\n\t\tself.num_left = 1\n\t\tself.num_total = 1\n\nclass AvlTree:\n\n\tdef __init__(self):\n\t\tself._tree = None\n\n\tdef add(self, k, v):\n\t\tif not self._tree:\n\t\t\tself._tree = TreeNode(k, v)\n\t\t\treturn\n\t\tnode = self._add(k, v)\n\t\tif node:\n\t\t\tself._rebalance(node)\n\n\tdef _add(self, k, v):\n\t\tnode = self._tree\n\t\twhile node:\n\t\t\tif k < node.key:\n\t\t\t\tif node.left:\n\t\t\t\t\tnode = node.left\n\t\t\t\telse:\n\t\t\t\t\tnode.left = TreeNode(k, v)\n\t\t\t\t\tnode.left.parent = node\n\t\t\t\t\treturn node.left\n\t\t\telif node.key < k:\n\t\t\t\tif node.right:\n\t\t\t\t\tnode = node.right\n\t\t\t\telse:\n\t\t\t\t\tnode.right = TreeNode(k, v)\n\t\t\t\t\tnode.right.parent = node\n\t\t\t\t\treturn node.right\n\t\t\telse:\n\t\t\t\tnode.value = v\n\t\t\t\treturn\n\n\t@staticmethod\n\tdef get_height(x):\n\t\treturn x.height if x else 0\n\n\t@staticmethod\n\tdef get_num_total(x):\n\t\treturn x.num_total if x else 0\n\n\tdef _rebalance(self, node):\n\t\tn = node\n\t\twhile n:\n\t\t\tlh = self.get_height(n.left)\n\t\t\trh = self.get_height(n.right)\n\t\t\tn.height = max(lh, rh) + 1\n\t\t\tbalance_factor = lh - rh\n\t\t\tn.num_total = 1 + self.get_num_total(n.left) + self.get_num_total(n.right)\n\t\t\tn.num_left = 1 + self.get_num_total(n.left)\n\t\t\tif balance_factor > 1:\n\t\t\t\tif self.get_height(n.left.left) < self.get_height(n.left.right):\n\t\t\t\t\tself._rotate_left(n.left)\n\t\t\t\tself._rotate_right(n)\n\t\t\telif balance_factor < -1:\n\t\t\t\tif self.get_height(n.right.right) < self.get_height(n.right.left):\n\t\t\t\t\tself._rotate_right(n.right)\n\t\t\t\tself._rotate_left(n)\n\t\t\telse:\n\t\t\t\tn = n.parent\n\n\tdef _remove_one(self, node):\n\t\treplacement = node.left or node.right\n\t\tif node.parent:\n\t\t\tif AvlTree._is_left(node):\n\t\t\t\tnode.parent.left = replacement\n\t\t\telse:\n\t\t\t\tnode.parent.right = replacement\n\t\t\treplacement.parent = node.parent\n\t\t\tnode.parent = None\n\t\telse:\n\t\t\tself._tree = replacement\n\t\t\treplacement.parent = None\n\t\tnode.left = None\n\t\tnode.right = None\n\t\tnode.parent = None\n\t\tself._rebalance(replacement)\n\n\tdef _remove_leaf(self, node):\n\t\tif node.parent:\n\t\t\tif AvlTree._is_left(node):\n\t\t\t\tnode.parent.left = None\n\t\t\telse:\n\t\t\t\tnode.parent.right = None\n\t\t\tself._rebalance(node.parent)\n\t\telse:\n\t\t\tself._tree = None\n\t\tnode.parent = None\n\t\tnode.left = None\n\t\tnode.right = None\n\n\tdef remove(self, k):\n\t\tnode = self._get_node(k)\n\t\tif not node:\n\t\t\treturn\n\t\tif AvlTree._is_leaf(node):\n\t\t\tself._remove_leaf(node)\n\t\t\treturn\n\t\tif node.left and node.right:\n\t\t\tnxt = AvlTree._get_next(node)\n\t\t\tnode.key = nxt.key\n\t\t\tnode.value = nxt.value\n\t\t\tif self._is_leaf(nxt):\n\t\t\t\tself._remove_leaf(nxt)\n\t\t\telse:\n\t\t\t\tself._remove_one(nxt)\n\t\t\tself._rebalance(node)\n\t\telse:\n\t\t\tself._remove_one(node)\n\n\tdef get(self, k):\n\t\tnode = self._get_node(k)\n\t\treturn node.value if node else -1\n\n\tdef _get_node(self, k):\n\t\tif not self._tree:\n\t\t\treturn None\n\t\tnode = self._tree\n\t\twhile node:\n\t\t\tif k < node.key:\n\t\t\t\tnode = node.left\n\t\t\telif node.key < k:\n\t\t\t\tnode = node.right\n\t\t\telse:\n\t\t\t\treturn node\n\t\treturn None\n\n\tdef get_at(self, pos):\n\t\tx = pos + 1\n\t\tnode = self._tree\n\t\twhile node:\n\t\t\tif x < node.num_left:\n\t\t\t\tnode = node.left\n\t\t\telif node.num_left < x:\n\t\t\t\tx -= node.num_left\n\t\t\t\tnode = node.right\n\t\t\telse:\n\t\t\t\treturn (node.key, node.value)\n\t\traise IndexError('Out of ranges')\n\n\t@staticmethod\n\tdef _is_left(node):\n\t\treturn node.parent.left and node.parent.left == node\n\n\t@staticmethod\n\tdef _is_leaf(node):\n\t\treturn node.left is None and node.right is None\n\n\tdef _rotate_right(self, node):\n\t\tif not node.parent:\n\t\t\tself._tree = node.left\n\t\t\tnode.left.parent = None\n\t\telif AvlTree._is_left(node):\n\t\t\tnode.parent.left = node.left\n\t\t\tnode.left.parent = node.parent\n\t\telse:\n\t\t\tnode.parent.right = node.left\n\t\t\tnode.left.parent = node.parent\n\t\tbk = node.left.right\n\t\tnode.left.right = node\n\t\tnode.parent = node.left\n\t\tnode.left = bk\n\t\tif bk:\n\t\t\tbk.parent = node\n\t\tnode.height = max(self.get_height(node.left), self.get_height(node.right)) + 1\n\t\tnode.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)\n\t\tnode.num_left = 1 + self.get_num_total(node.left)\n\n\tdef _rotate_left(self, node):\n\t\tif not node.parent:\n\t\t\tself._tree = node.right\n\t\t\tnode.right.parent = None\n\t\telif AvlTree._is_left(node):\n\t\t\tnode.parent.left = node.right\n\t\t\tnode.right.parent = node.parent\n\t\telse:\n\t\t\tnode.parent.right = node.right\n\t\t\tnode.right.parent = node.parent\n\t\tbk = node.right.left\n\t\tnode.right.left = node\n\t\tnode.parent = node.right\n\t\tnode.right = bk\n\t\tif bk:\n\t\t\tbk.parent = node\n\t\tnode.height = max(self.get_height(node.left), self.get_height(node.right)) + 1\n\t\tnode.num_total = 1 + self.get_num_total(node.left) + self.get_num_total(node.right)\n\t\tnode.num_left = 1 + self.get_num_total(node.left)\n\n\t@staticmethod\n\tdef _get_next(node):\n\t\tif not node.right:\n\t\t\treturn node.parent\n\t\tn = node.right\n\t\twhile n.left:\n\t\t\tn = n.left\n\t\treturn n\n\nclass SegmentTree1:\n\n\tdef __init__(self, data, default=0, func=lambda a, b: max(a, b)):\n\t\tself._default = default\n\t\tself._func = func\n\t\tself._len = len(data)\n\t\tself._size = _size = 1 << (self._len - 1).bit_length()\n\t\tself.data = [default] * (2 * _size)\n\t\tself.data[_size:_size + self._len] = data\n\t\tfor i in reversed(range(_size)):\n\t\t\tself.data[i] = func(self.data[i + i], self.data[i + i + 1])\n\n\tdef __delitem__(self, idx):\n\t\tself[idx] = self._default\n\n\tdef __getitem__(self, idx):\n\t\treturn self.data[idx + self._size]\n\n\tdef __setitem__(self, idx, value):\n\t\tidx += self._size\n\t\tself.data[idx] = value\n\t\tidx >>= 1\n\t\twhile idx:\n\t\t\tself.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n\t\t\tidx >>= 1\n\n\tdef __len__(self):\n\t\treturn self._len\n\n\tdef query(self, start, stop):\n\t\tif start == stop:\n\t\t\treturn self.__getitem__(start)\n\t\tstop += 1\n\t\tstart += self._size\n\t\tstop += self._size\n\t\tres = self._default\n\t\twhile start < stop:\n\t\t\tif start & 1:\n\t\t\t\tres = self._func(res, self.data[start])\n\t\t\t\tstart += 1\n\t\t\tif stop & 1:\n\t\t\t\tstop -= 1\n\t\t\t\tres = self._func(res, self.data[stop])\n\t\t\tstart >>= 1\n\t\t\tstop >>= 1\n\t\treturn res\n\n\tdef __repr__(self):\n\t\treturn 'SegmentTree({0})'.format(self.data)\n\nclass SegmentTree:\n\n\tdef __init__(self, data, default=0, func=lambda a, b: a + b):\n\t\tself._default = default\n\t\tself._func = func\n\t\tself._len = len(data)\n\t\tself._size = _size = 1 << (self._len - 1).bit_length()\n\t\tself.data = [default] * (2 * _size)\n\t\tself.data[_size:_size + self._len] = data\n\t\tfor i in reversed(range(_size)):\n\t\t\tself.data[i] = func(self.data[i + i], self.data[i + i + 1])\n\n\tdef __delitem__(self, idx):\n\t\tself[idx] = self._default\n\n\tdef __getitem__(self, idx):\n\t\treturn self.data[idx + self._size]\n\n\tdef __setitem__(self, idx, value):\n\t\tidx += self._size\n\t\tself.data[idx] = value\n\t\tidx >>= 1\n\t\twhile idx:\n\t\t\tself.data[idx] = self._func(self.data[2 * idx], self.data[2 * idx + 1])\n\t\t\tidx >>= 1\n\n\tdef __len__(self):\n\t\treturn self._len\n\n\tdef query(self, start, stop):\n\t\tif start == stop:\n\t\t\treturn self.__getitem__(start)\n\t\tstop += 1\n\t\tstart += self._size\n\t\tstop += self._size\n\t\tres = self._default\n\t\twhile start < stop:\n\t\t\tif start & 1:\n\t\t\t\tres = self._func(res, self.data[start])\n\t\t\t\tstart += 1\n\t\t\tif stop & 1:\n\t\t\t\tstop -= 1\n\t\t\t\tres = self._func(res, self.data[stop])\n\t\t\tstart >>= 1\n\t\t\tstop >>= 1\n\t\treturn res\n\n\tdef __repr__(self):\n\t\treturn 'SegmentTree({0})'.format(self.data)\n\nclass Factorial:\n\n\tdef __init__(self, MOD):\n\t\tself.MOD = MOD\n\t\tself.factorials = [1, 1]\n\t\tself.invModulos = [0, 1]\n\t\tself.invFactorial_ = [1, 1]\n\n\tdef calc(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate n!')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tif n < len(self.factorials):\n\t\t\treturn self.factorials[n]\n\t\tnextArr = [0] * (n + 1 - len(self.factorials))\n\t\tinitialI = len(self.factorials)\n\t\tprev = self.factorials[-1]\n\t\tm = self.MOD\n\t\tfor i in range(initialI, n + 1):\n\t\t\tprev = nextArr[i - initialI] = prev * i % m\n\t\tself.factorials += nextArr\n\t\treturn self.factorials[n]\n\n\tdef inv(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate n^(-1)')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tp = self.MOD\n\t\tpi = n % p\n\t\tif pi < len(self.invModulos):\n\t\t\treturn self.invModulos[pi]\n\t\tnextArr = [0] * (n + 1 - len(self.invModulos))\n\t\tinitialI = len(self.invModulos)\n\t\tfor i in range(initialI, min(p, n + 1)):\n\t\t\tnext = -self.invModulos[p % i] * (p // i) % p\n\t\t\tself.invModulos.append(next)\n\t\treturn self.invModulos[pi]\n\n\tdef invFactorial(self, n):\n\t\tif n <= -1:\n\t\t\tprint('Invalid argument to calculate (n^(-1))!')\n\t\t\tprint('n must be non-negative value. But the argument was ' + str(n))\n\t\t\texit()\n\t\tif n < len(self.invFactorial_):\n\t\t\treturn self.invFactorial_[n]\n\t\tself.inv(n)\n\t\tnextArr = [0] * (n + 1 - len(self.invFactorial_))\n\t\tinitialI = len(self.invFactorial_)\n\t\tprev = self.invFactorial_[-1]\n\t\tp = self.MOD\n\t\tfor i in range(initialI, n + 1):\n\t\t\tprev = nextArr[i - initialI] = prev * self.invModulos[i % p] % p\n\t\tself.invFactorial_ += nextArr\n\t\treturn self.invFactorial_[n]\n\nclass Combination:\n\n\tdef __init__(self, MOD):\n\t\tself.MOD = MOD\n\t\tself.factorial = Factorial(MOD)\n\n\tdef ncr(self, n, k):\n\t\tif k < 0 or n < k:\n\t\t\treturn 0\n\t\tk = min(k, n - k)\n\t\tf = self.factorial\n\t\treturn f.calc(n) * f.invFactorial(max(n - k, k)) * f.invFactorial(min(k, n - k)) % self.MOD\n\ndef powm(a, n, m):\n\tif a == 1 or n == 0:\n\t\treturn 1\n\tif n % 2 == 0:\n\t\ts = powm(a, n // 2, m)\n\t\treturn s * s % m\n\telse:\n\t\treturn a * powm(a, n - 1, m) % m\n\ndef sort_list(list1, list2):\n\tzipped_pairs = zip(list2, list1)\n\tz = [x for (_, x) in sorted(zipped_pairs)]\n\treturn z\n\ndef product(l):\n\tpor = 1\n\tfor i in range(len(l)):\n\t\tpor *= l[i]\n\treturn por\n\ndef binarySearchCount(arr, n, key):\n\tleft = 0\n\tright = n - 1\n\tcount = 0\n\twhile left <= right:\n\t\tmid = int((right + left) / 2)\n\t\tif arr[mid] < key:\n\t\t\tcount = mid + 1\n\t\t\tleft = mid + 1\n\t\telse:\n\t\t\tright = mid - 1\n\treturn count\n\ndef countdig(n):\n\tc = 0\n\twhile n > 0:\n\t\tn //= 10\n\t\tc += 1\n\treturn c\n\ndef binary(x, length):\n\ty = bin(x)[2:]\n\treturn y if len(y) >= length else '0' * (length - len(y)) + y\n\ndef countGreater(arr, n, k):\n\tl = 0\n\tr = n - 1\n\tleftGreater = n\n\twhile l <= r:\n\t\tm = int(l + (r - l) / 2)\n\t\tif arr[m] >= k:\n\t\t\tleftGreater = m\n\t\t\tr = m - 1\n\t\telse:\n\t\t\tl = m + 1\n\treturn n - leftGreater\n(n, m) = map(int, input().split())\nd = defaultdict(list)\nt = n + 1\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\td[a].append([t, a])\n\td[b].append([t, b])\n\tt += 1\nfor i in range(n):\n\tprint(len(d[i + 1]) + 1)\n\tprint(i + 1, i + 1)\n\tfor j in d[i + 1]:\n\t\tprint(*j)\n", "import sys\nlines = sys.stdin.readlines()\n(n, m) = map(int, lines[0].strip().split(' '))\ncurr = n\ndic = {}\nfor i in range(1, m + 1):\n\tcurr += 1\n\t(a, b) = map(int, lines[i].strip().split(' '))\n\tif a not in dic:\n\t\tdic[a] = []\n\tif b not in dic:\n\t\tdic[b] = []\n\tdic[a].append(curr)\n\tdic[b].append(curr)\nfor i in range(1, n + 1):\n\tif i not in dic:\n\t\tprint(1)\n\telse:\n\t\tprint(1 + len(dic[i]))\n\tprint('{} {}'.format(i, i))\n\tif i in dic:\n\t\tfor val in dic[i]:\n\t\t\tprint('{} {}'.format(i, val))\n", "(n, m) = map(int, input().split())\nharmonies = []\nfor i in range(m):\n\tharmonies.append(list(map(int, input().split())))\nspots = []\nfor i in range(n):\n\tyourspots = []\n\tfor j in range(m):\n\t\tif i + 1 in harmonies[j]:\n\t\t\tyourspots.append((i + 1, j + 1))\n\tyourspots.append((i + 1, 10000 - i))\n\tspots.append(yourspots)\nfor i in range(n):\n\tprint(len(spots[i]))\n\tfor j in range(len(spots[i])):\n\t\tprint(str(spots[i][j][0]), str(spots[i][j][1]))\n", "(n, m) = map(int, input().split())\no = [[] for _ in range(n)]\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\to[a - 1].append('%i %i' % (a, i + 1))\n\to[b - 1].append('%i %i' % (b, i + 1))\nm += 1\nfor i in range(n):\n\tif len(o[i]) == 0:\n\t\tprint(1)\n\t\tprint('%i %i' % (i + 1, m))\n\t\tm += 1\n\telse:\n\t\tprint(len(o[i]))\n\t\tprint('\\n'.join(o[i]))\n", "(n, m) = list(map(int, input().split()))\nG = [[] for _ in range(n + 1)]\nfinal = [[] for _ in range(n + 1)]\nseen = {}\nfor _ in range(m):\n\t(a, b) = list(map(int, input().split()))\n\tif a > b:\n\t\t(a, b) = (b, a)\n\tseen[a] = True\n\tseen[b] = True\n\tG[a].append(b)\nstep = 1\nfor i in range(1, n + 1):\n\thrmny = G[i]\n\tif i not in seen:\n\t\tfinal[i].append((step, i))\n\t\tstep += 1\n\tfor h in hrmny:\n\t\tfinal[i].append((step, i))\n\t\tfinal[h].append((step, h))\n\t\tstep += 1\nfor i in range(1, n + 1):\n\tf = final[i]\n\tprint(len(f))\n\tprint('\\n'.join(map(lambda a: '{} {}'.format(*a), f)))\n", "(n, m) = map(int, input().split())\ncolor = [[] for i in range(n)]\nnotPut = {i for i in range(n)}\nc = 1\nncopy = n\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\tif a - 1 in notPut:\n\t\tnotPut.remove(a - 1)\n\tif b - 1 in notPut:\n\t\tnotPut.remove(b - 1)\n\tcolor[a - 1].append((c, a))\n\tcolor[b - 1].append((c, b))\n\tc += 1\n\tn -= 2\nfor x in notPut:\n\tcolor[x].append((c, x + 1))\n\tc += 1\n\tn -= 1\nfor i in range(n):\n\tcolor[0].append((c, 0))\nfor i in range(ncopy):\n\tprint(len(color[i]))\n\tfor coord in color[i]:\n\t\tprint(*coord)\n", "(n, m) = map(int, input().split())\ntable = []\nfor i in range(0, n + 1):\n\ttable.append([])\nfor i in range(0, n + 1):\n\ttable[i].append([])\nt = [0] * (n + 1)\ni = m\nwhile i != 0:\n\t(n1, n2) = map(int, input().split())\n\tif n1 > n2:\n\t\t(n1, n2) = (n2, n1)\n\tt[n1] += 1\n\tt[n2] += 1\n\ttable[n1].append((n1 - 1) * n + n2)\n\ttable[n2].append((n1 - 1) * n + n2)\n\ti -= 1\ni = 1\nwhile i != n + 1:\n\tt[i] += 1\n\ttable[i].append((i - 1) * n + i)\n\tprint(t[i])\n\tj = 1\n\twhile j != t[i] + 1:\n\t\tprint(i, table[i][j])\n\t\tj += 1\n\ti += 1\n", "(n, m) = list(map(int, input().strip().split()))\ngraph = [set({}) for i in range(n + 1)]\nfor i in range(m):\n\t(a, b) = list(map(int, input().strip().split()))\n\tgraph[min(a, b)].add(max(a, b))\npoints = [set({}) for i in range(n + 1)]\npoints_start = [-1 for i in range(n + 2)]\ns = 1\nfor j in range(1, n + 1):\n\ti = graph[j]\n\tpoints_start[j] = s\n\ts += len(i) + 1\npoints_start[-1] = s\nfor i in range(1, n + 1):\n\tfor d in range(points_start[i + 1] - points_start[i]):\n\t\tpoints[i].add((points_start[i] + d, i))\nfor (coord, edges) in enumerate(graph):\n\tif coord != 0:\n\t\tfor (i, edge) in enumerate(edges):\n\t\t\tpoints[edge].add((points_start[coord] + i, edge))\nfor (coord, p) in enumerate(points):\n\tif coord != 0:\n\t\tprint(len(p))\n\t\tfor j in p:\n\t\t\tprint(j[0], j[1])\n", "(n, m) = map(int, input().split())\na = [[] for i in range(105)]\nfor i in range(1, m + 1):\n\t(u, v) = map(int, input().split())\n\ta[u].append([u, i])\n\ta[v].append([v, i])\nt = m + 1\nfor i in range(1, n + 1):\n\tif len(a[i]) == 0:\n\t\ta[i].append([i, t])\n\t\tt += 1\nfor i in range(1, n + 1):\n\tprint(len(a[i]))\n\tfor j in a[i]:\n\t\tprint(j[0], j[1])\n", "(n, m) = [int(s) for s in input().split()]\nnear = [[] for i in range(101)]\npos = [[] for i in range(101)]\nfor i in range(m):\n\t(a, b) = [int(s) for s in input().split()]\n\tnear[a].append(b)\n\tnear[b].append(a)\ncnt = 0\nvis = [0] * (n + 1)\ncolor = [0] * (n + 1)\ncolor0 = 1\nc = 1\nfor i in range(1, n + 1):\n\tif len(near[i]) == 0:\n\t\tpos[i].append(c)\n\t\tc += 1\n\t\tcontinue\n\tfor s in near[i]:\n\t\tif s > i:\n\t\t\tpos[s].append(c)\n\t\t\tpos[i].append(c)\n\t\t\tc += 1\nfor i in range(1, n + 1):\n\tprint(len(pos[i]))\n\tfor s in pos[i]:\n\t\tprint(i, s)\n", "import sys\nfrom math import *\n\ndef minp():\n\treturn sys.stdin.readline().strip()\n\ndef mint():\n\treturn int(minp())\n\ndef mints():\n\treturn map(int, minp().split())\n(n, m) = mints()\na = []\np = [None] * n\nfor i in range(n):\n\tp[i] = []\nfor i in range(m):\n\t(x, y) = mints()\n\tp[x - 1].append((i + 1, x))\n\tp[y - 1].append((i + 1, y))\nfor i in range(n):\n\tp[i].append((m + 1 + i, i + 1))\nfor i in range(n):\n\tprint(len(p[i]))\n\tfor j in p[i]:\n\t\tprint(*j)\n", "(n, m) = map(int, input().split())\nd = {i: set() for i in range(1, n + 1)}\nfor _ in range(m):\n\t(a, b) = map(int, input().split())\n\td[a].add(b)\n\td[b].add(a)\nx = 1\nc = {i: set() for i in range(1, n + 1)}\nfor i in range(1, n + 1):\n\tc[i].add((x, i))\n\tx += 1\n\tfor j in c:\n\t\tif j < i and j in d[i]:\n\t\t\tc[j].add((x, j))\n\t\t\tc[i].add((x, i))\n\t\t\tx += 1\nfor i in c:\n\tprint(len(c[i]))\n\tfor j in c[i]:\n\t\tprint(j[0], j[1])\n", "(n, m) = map(int, input().split())\nclr = [[] for i in range(n)]\nfor i in range(m):\n\t(a, b) = sorted(map(int, input().split()))\n\ta -= 1\n\tb -= 1\n\tclr[a].append(b)\nys = [-1 for i in range(n)]\nresult = [[] for i in range(n)]\nglobal y, x\nx = 1\ny = 1\n\ndef visit(cur):\n\tglobal y, x\n\ty += 1\n\tresult[cur].append((x, y))\n\tx += 1\n\tys[cur] = y\n\tfor adj in clr[cur]:\n\t\tif ys[adj] == -1:\n\t\t\tvisit(adj)\n\t\tresult[cur].append((x, ys[cur]))\n\t\tresult[adj].append((x, ys[adj]))\n\t\tx += 1\nfor i in range(n):\n\tif ys[i] == -1:\n\t\tvisit(i)\nfor i in range(n):\n\tprint(len(result[i]))\n\tfor j in result[i]:\n\t\tprint(*j)\n", "def print_return(func):\n\n\tdef wrapper(*args, **kwargs):\n\t\tretval = func(*args, **kwargs)\n\t\tprint(retval)\n\t\treturn retval\n\treturn wrapper\n\nclass Solve:\n\n\t@print_return\n\tdef solve_a(lines=None):\n\t\tif lines is None:\n\t\t\t(n, m, k, l) = (int(x) for x in input().split())\n\t\telse:\n\t\t\t(n, m, k, l) = (int(x) for x in lines[0].split())\n\t\tx = k + l + m - 1\n\t\tx //= m\n\t\tif x * m > n:\n\t\t\treturn -1\n\t\treturn x\n\n\t@print_return\n\tdef solve_b(lines=None):\n\t\tif lines is None:\n\t\t\tb = int(input())\n\t\telse:\n\t\t\tb = int(lines[0])\n\t\tdivisors = set()\n\t\tfor x in range(1, int(b ** 0.5) + 5):\n\t\t\tif b % x == 0:\n\t\t\t\tdivisors.add(x)\n\t\t\t\tdivisors.add(b // x)\n\t\treturn len(divisors)\n\n\t@print_return\n\tdef solve_c(lines=None):\n\t\tif lines is None:\n\t\t\t(n, m) = (int(x) for x in input().split())\n\t\t\tgood_pairs = [tuple((int(x) for x in input().split())) for _ in range(m)]\n\t\telse:\n\t\t\t(n, m) = (int(x) for x in lines[0].split())\n\t\t\tgood_pairs = [tuple((int(x) for x in lines[j + 1].split())) for j in range(m)]\n\t\tcolor___coors = [[]] + [[(x + 1, x + 1)] for x in range(n)]\n\t\tfor col in range(n + 1, n + m + 1):\n\t\t\t(c1, c2) = good_pairs.pop()\n\t\t\tcolor___coors[c1].append((c1, col))\n\t\t\tcolor___coors[c2].append((c2, col))\n\t\tans = ''\n\t\tfor (color, coors) in enumerate(color___coors):\n\t\t\tif color == 0:\n\t\t\t\tcontinue\n\t\t\tcurr_ans = str(len(coors)) + '\\n'\n\t\t\tfor coor in coors:\n\t\t\t\tcurr_ans += '{} {}\\n'.format(*coor)\n\t\t\tans += curr_ans\n\t\treturn ans\n\n\t@print_return\n\tdef solve_d(lines=None):\n\t\tif lines is None:\n\t\t\tn = int(input())\n\t\t\tidx___val = [int(x) for x in input().split()]\n\t\telse:\n\t\t\tn = int(lines[0])\n\t\t\tidx___val = [int(x) for x in lines[1].split()]\nSolve.solve_c()\n", "import os\nfrom io import BytesIO\ninput = BytesIO(os.read(0, os.fstat(0).st_size)).readline\n\ndef lii():\n\treturn list(map(int, input().split()))\n\ndef ii():\n\treturn int(input())\n(n, m) = lii()\npairs = []\nfor i in range(m):\n\tpairs.append(lii())\nrooks = {i: [(i, i)] for i in range(n)}\n(x, y) = (n, n)\nfor each in pairs:\n\t(p, q) = each\n\tp -= 1\n\tq -= 1\n\trooks[p].append([x, y])\n\trooks[q].append([x + 1, y])\n\trooks[p].append([p, y])\n\trooks[q].append([q, y])\n\tx += 2\n\ty += 1\nfor (k, v) in rooks.items():\n\tprint(len(v))\n\tfor rook in v:\n\t\tprint(rook[0] + 1, rook[1] + 1)\n", "(n, m) = map(int, input().split())\nres = [[(i + 1, 5001 + i)] for i in range(n)]\nfor i in range(m):\n\t(a, b) = map(int, input().split())\n\tres[a - 1].append((a, i + 1))\n\tres[b - 1].append((b, i + 1))\nfor i in range(n):\n\tprint(len(res[i]))\n\tfor p in res[i]:\n\t\tprint(*p)\n"]

source: codeforces

raw_problem:
C. Colored Rooks

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

Ivan is a novice painter. He has $$$n$$$ dyes of different colors. He also knows exactly $$$m$$$ pairs of colors which harmonize with each other.

Ivan also enjoy playing chess. He has $$$5000$$$ rooks. He wants to take $$$k$$$ rooks, paint each of them in one of $$$n$$$ colors and then place this $$$k$$$ rooks on a chessboard of size $$$10^{9} \times 10^{9}$$$.

Let's call the set of rooks on the board connected if from any rook we can get to any other rook in this set moving only through cells with rooks from this set. Assume that rooks can jump over other rooks, in other words a rook can go to any cell which shares vertical and to any cell which shares horizontal.

Ivan wants his arrangement of rooks to have following properties:

 For any color there is a rook of this color on a board;

 For any color the set of rooks of this color is connected;

 For any two different colors $$$a$$$ $$$b$$$ union of set of rooks of color $$$a$$$ and set of rooks of color $$$b$$$ is connected if and only if this two colors harmonize with each other.

Please help Ivan find such an arrangement.

Input

The first line of input contains $$$2$$$ integers $$$n$$$, $$$m$$$ ($$$1 \le n \le 100$$$, $$$0 \le m \le min(1000, \,\, \frac{n(n-1)}{2})$$$) — number of colors and number of pairs of colors which harmonize with each other.

In next $$$m$$$ lines pairs of colors which harmonize with each other are listed. Colors are numbered from $$$1$$$ to $$$n$$$. It is guaranteed that no pair occurs twice in this list.

Output

Print $$$n$$$ blocks, $$$i$$$-th of them describes rooks of $$$i$$$-th color.

In the first line of block print one number $$$a_{i}$$$ ($$$1 \le a_{i} \le 5000$$$) — number of rooks of color $$$i$$$. In each of next $$$a_{i}$$$ lines print two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, \,\, y \le 10^{9}$$$) — coordinates of the next rook.

All rooks must be on different cells.

Total number of rooks must not exceed $$$5000$$$.

It is guaranteed that the solution exists.

Examples

Input

3 2
1 2
2 3

Output

2
3 4
1 4
4
1 2
2 2
2 4
5 4
1
5 1

Input

3 3
1 2
2 3
3 1

Output

1
1 1
1
1 2
1
1 3

Input

3 1
1 3

Output

1
1 1
1
2 2
1
3 1

Note

Rooks arrangements for all three examples (red is color $$$1$$$, green is color $$$2$$$ and blue is color $$$3$$$).

question:
Ivan is a novice painter. He has $$$n$$$ dyes of different colors. He also knows exactly $$$m$$$ pairs of colors which harmonize with each other.
Ivan also enjoy playing chess. He has $$$5000$$$ rooks. He wants to take $$$k$$$ rooks, paint each of them in one of $$$n$$$ colors and then place this $$$k$$$ rooks on a chessboard of size $$$10^{9} \times 10^{9}$$$.
Let's call the set of rooks on the board connected if from any rook we can get to any other rook in this set moving only through cells with rooks from this set. Assume that rooks can jump over other rooks, in other words a rook can go to any cell which shares vertical and to any cell which shares horizontal.
Ivan wants his arrangement of rooks to have following properties:
-  For any color there is a rook of this color on a board;-  For any color the set of rooks of this color is connected;-  For any two different colors $$$a$$$ $$$b$$$ union of set of rooks of color $$$a$$$ and set of rooks of color $$$b$$$ is connected if and only if this two colors harmonize with each other.Please help Ivan find such an arrangement.

Input
The first line of input contains $$$2$$$ integers $$$n$$$, $$$m$$$ ($$$1 \le n \le 100$$$, $$$0 \le m \le min(1000, \,\, \frac{n(n-1)}{2})$$$) — number of colors and number of pairs of colors which harmonize with each other.
In next $$$m$$$ lines pairs of colors which harmonize with each other are listed. Colors are numbered from $$$1$$$ to $$$n$$$. It is guaranteed that no pair occurs twice in this list.

Output
Print $$$n$$$ blocks, $$$i$$$-th of them describes rooks of $$$i$$$-th color.
In the first line of block print one number $$$a_{i}$$$ ($$$1 \le a_{i} \le 5000$$$) — number of rooks of color $$$i$$$. In each of next $$$a_{i}$$$ lines print two integers $$$x$$$ and $$$y$$$ ($$$1 \le x, \,\, y \le 10^{9}$$$) — coordinates of the next rook.
All rooks must be on different cells.
Total number of rooks must not exceed $$$5000$$$.
It is guaranteed that the solution exists.

Examples
Input
3 2
1 2
2 3

Output
2
3 4
1 4
4
1 2
2 2
2 4
5 4
1
5 1

Input
3 3
1 2
2 3
3 1

Output
1
1 1
1
1 2
1
1 3

Input
3 1
1 3

Output
1
1 1
1
2 2
1
3 1

Note
Rooks arrangements for all three examples (red is color $$$1$$$, green is color $$$2$$$ and blue is color $$$3$$$).
![image](1.png)
![image](2.png)
![image](3.png)

tags: ['Graph algorithms', 'Constructive algorithms']

image_tags: Patterns Patterns Patterns

data_split: test


D. Third Month Insanity

problem_index: D

time_limit: 2 seconds

memory_limit: 256 megabytes

output_spec:
Print the maximum possible expected score over all possible brackets. Your answer must be correct to within an absolute or relative error of 10 - 9.
Formally, let your answer be a, and the jury's answer be b. Your answer will be considered correct, if ![image](images/cf_859_D/1.png).

solutions: ["n = int(input())\nm = 1 << n\np = [list(map(int, input().split())) for i in range(m)]\n(u, x) = ([1] * m, [0] * m)\n(v, y) = (u[:], x[:])\nfor i in range(n):\n\td = 1 << i\n\tfor j in range(m):\n\t\ts = d * (j // d ^ 1)\n\t\tv[j] = u[j] * sum((u[k] * p[j][k] for k in range(s, s + d))) / 100\n\t\ty[j] = max(x[s:s + d]) + x[j] + v[j] * d\n\t(u, v, x, y) = (v, u, y, x)\nprint(max(x))\n", "import functools\nn = int(input())\nprops = []\n\ndef preproc(a):\n\treturn float(a) / 100.0\nfor i in range(pow(2, n)):\n\tprops.append(list(map(preproc, input().split())))\nwining_props = []\nwining_props_first_round = []\nfor i in range(0, 2 ** n, 2):\n\twining_prop_for_i = props[i][i + 1]\n\twining_props_first_round.append(wining_prop_for_i)\n\twining_props_first_round.append(1.0 - wining_prop_for_i)\nwining_props.append(wining_props_first_round)\nassert len(wining_props_first_round) == len(props)\nfor round_num in range(2, n + 1):\n\tthis_round_wining_props = []\n\tfor team_num in range(2 ** n):\n\t\tt = team_num // 2 ** round_num * 2 ** round_num\n\t\tteams_we_meet_this_round = [t + x for x in range(2 ** round_num)]\n\t\tt = team_num // 2 ** (round_num - 1) * 2 ** (round_num - 1)\n\t\tteams_we_meet_prev_round = [t + x for x in range(2 ** (round_num - 1))]\n\t\tfor tt in teams_we_meet_prev_round:\n\t\t\tteams_we_meet_this_round.remove(tt)\n\t\tthis_team_wining_props = wining_props[round_num - 2][team_num]\n\t\tchances_win_i_team = []\n\t\tfor tm in teams_we_meet_this_round:\n\t\t\tchances_win_i_team.append(wining_props[round_num - 2][tm] * props[team_num][tm])\n\t\tmo_win_this_round = sum(chances_win_i_team)\n\t\tthis_team_wining_props *= mo_win_this_round\n\t\tthis_round_wining_props.append(this_team_wining_props)\n\twining_props.append(this_round_wining_props)\n\n@functools.lru_cache(maxsize=None)\ndef revenue(round_num, teams_left, teams_right, winner=-1):\n\tsplit = (teams_left + teams_right) // 2\n\tif round_num == 1:\n\t\treturn wining_props[0][winner] if winner != -1 else max(wining_props[0][teams_left:teams_right])\n\tif winner == -1:\n\t\tresults = []\n\t\tfor winner in range(teams_left, teams_right):\n\t\t\twinner_prop = wining_props[round_num - 1][winner]\n\t\t\tif winner >= split:\n\t\t\t\tres = sum([revenue(round_num - 1, teams_left, split), revenue(round_num - 1, split, teams_right, winner), winner_prop * 2 ** (round_num - 1)])\n\t\t\telse:\n\t\t\t\tres = sum([revenue(round_num - 1, teams_left, split, winner), revenue(round_num - 1, split, teams_right), winner_prop * 2 ** (round_num - 1)])\n\t\t\tresults.append(res)\n\t\treturn max(results)\n\telse:\n\t\twinner_prop = wining_props[round_num - 1][winner]\n\t\tif winner >= split:\n\t\t\tres = sum([revenue(round_num - 1, teams_left, split), revenue(round_num - 1, split, teams_right, winner), winner_prop * 2 ** (round_num - 1)])\n\t\telse:\n\t\t\tres = sum([revenue(round_num - 1, teams_left, split, winner), revenue(round_num - 1, split, teams_right), winner_prop * 2 ** (round_num - 1)])\n\t\treturn res\nprint(revenue(n, 0, 2 ** n))\n", "n = int(input())\nm = 2 ** n\npoints = [0] * (2 * m)\npoints[1] = 2 ** (n - 1)\nfor i in range(1, m):\n\tx = points[i] // 2\n\tpoints[2 * i] = x\n\tpoints[2 * i + 1] = x\nP = [[int(x) / 100.0 for x in input().split()] for _ in range(m)]\nstate = [[0.0] * 64 for _ in range(2 * m)]\nfor i in range(m):\n\tstate[m + i][i] = 1.0\nfor i in reversed(range(1, m)):\n\tfor j in range(m):\n\t\tfor k in range(j + 1, m):\n\t\t\tx = state[2 * i][j] * state[2 * i + 1][k]\n\t\t\tstate[i][j] += P[j][k] * x\n\t\t\tstate[i][k] += P[k][j] * x\nscore = [[0] * 64 for _ in range(2 * m)]\nfor i in reversed(range(1, m)):\n\tfor j in range(m):\n\t\tfor k in range(m):\n\t\t\tscore[i][j] = max(score[i][j], score[2 * i][j] + state[i][j] * points[i] + score[2 * i + 1][k])\n\t\t\tscore[i][j] = max(score[i][j], score[2 * i + 1][j] + state[i][j] * points[i] + score[2 * i][k])\nprint(repr(max(score[1])))\n"]

question:
The annual college sports-ball tournament is approaching, which for trademark reasons we'll refer to as Third Month Insanity. There are a total of 2^{N} teams participating in the tournament, numbered from 1 to 2^{N}. The tournament lasts N rounds, with each round eliminating half the teams. The first round consists of 2^{N - 1} games, numbered starting from 1. In game i, team 2·i - 1 will play against team 2·i. The loser is eliminated and the winner advances to the next round (there are no ties). Each subsequent round has half as many games as the previous round, and in game i the winner of the previous round's game 2·i - 1 will play against the winner of the previous round's game 2·i.
Every year the office has a pool to see who can create the best bracket. A bracket is a set of winner predictions for every game. For games in the first round you may predict either team to win, but for games in later rounds the winner you predict must also be predicted as a winner in the previous round. Note that the bracket is fully constructed before any games are actually played. Correct predictions in the first round are worth 1 point, and correct predictions in each subsequent round are worth twice as many points as the previous, so correct predictions in the final game are worth 2^{N - 1} points.
For every pair of teams in the league, you have estimated the probability of each team winning if they play against each other. Now you want to construct a bracket with the maximum possible expected score.

Input
Input will begin with a line containing N (2 ≤ N ≤ 6).
2^{N} lines follow, each with 2^{N} integers. The j-th column of the i-th row indicates the percentage chance that team i will defeat team j, unless i = j, in which case the value will be 0. It is guaranteed that the i-th column of the j-th row plus the j-th column of the i-th row will add to exactly 100.

Output
Print the maximum possible expected score over all possible brackets. Your answer must be correct to within an absolute or relative error of 10^{ - 9}.
Formally, let your answer be a, and the jury's answer be b. Your answer will be considered correct, if ![image](1.png).

Examples
Input
2
0 40 100 100
60 0 40 40
0 60 0 45
0 60 55 0

Output
1.75

Input
3
0 0 100 0 100 0 0 0
100 0 100 0 0 0 100 100
0 0 0 100 100 0 0 0
100 100 0 0 0 0 100 100
0 100 0 100 0 0 100 0
100 100 100 100 100 0 0 0
100 0 100 0 0 100 0 0
100 0 100 0 100 100 100 0

Output
12

Input
2
0 21 41 26
79 0 97 33
59 3 0 91
74 67 9 0

Output
3.141592

Note
In the first example, you should predict teams 1 and 4 to win in round 1, and team 1 to win in round 2. Recall that the winner you predict in round 2 must also be predicted as a winner in round 1.

difficulty: HARD

source: codeforces

raw_problem:
D. Third Month Insanity

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

The annual college sports-ball tournament is approaching, which for trademark reasons we'll refer to as Third Month Insanity. There are a total of 2N teams participating in the tournament, numbered from 1 to 2N. The tournament lasts N rounds, with each round eliminating half the teams. The first round consists of 2N - 1 games, numbered starting from 1. In game i, team 2·i - 1 will play against team 2·i. The loser is eliminated and the winner advances to the next round (there are no ties). Each subsequent round has half as many games as the previous round, and in game i the winner of the previous round's game 2·i - 1 will play against the winner of the previous round's game 2·i.

Every year the office has a pool to see who can create the best bracket. A bracket is a set of winner predictions for every game. For games in the first round you may predict either team to win, but for games in later rounds the winner you predict must also be predicted as a winner in the previous round. Note that the bracket is fully constructed before any games are actually played. Correct predictions in the first round are worth 1 point, and correct predictions in each subsequent round are worth twice as many points as the previous, so correct predictions in the final game are worth 2N - 1 points.

For every pair of teams in the league, you have estimated the probability of each team winning if they play against each other. Now you want to construct a bracket with the maximum possible expected score.

Input

Input will begin with a line containing N (2 ≤ N ≤ 6).

2N lines follow, each with 2N integers. The j-th column of the i-th row indicates the percentage chance that team i will defeat team j, unless i = j, in which case the value will be 0. It is guaranteed that the i-th column of the j-th row plus the j-th column of the i-th row will add to exactly 100.

Output

Print the maximum possible expected score over all possible brackets. Your answer must be correct to within an absolute or relative error of 10 - 9.

Formally, let your answer be a, and the jury's answer be b. Your answer will be considered correct, if .

Examples

Input

2
0 40 100 100
60 0 40 40
0 60 0 45
0 60 55 0

Output

1.75

Input

3
0 0 100 0 100 0 0 0
100 0 100 0 0 0 100 100
0 0 0 100 100 0 0 0
100 100 0 0 0 0 100 100
0 100 0 100 0 0 100 0
100 100 100 100 100 0 0 0
100 0 100 0 0 100 0 0
100 0 100 0 100 100 100 0

Output

12

Input

2
0 21 41 26
79 0 97 33
59 3 0 91
74 67 9 0

Output

3.141592

Note

In the first example, you should predict teams 1 and 4 to win in round 1, and team 1 to win in round 2. Recall that the winner you predict in round 2 must also be predicted as a winner in round 1.

tags: ['Tree algorithms', 'Dynamic programming', 'Probability']

skill_types: ['Dynamic programming']

data_split: test