F. Removing Leaves

problem_index: F

time_limit: 2 seconds

memory_limit: 256 megabytes

note:
The picture corresponding to the first test case of the example:
![image](images/cf_1385_F/1.png)
There you can remove vertices $$$2$$$, $$$5$$$ and $$$3$$$ during the first move and vertices $$$1$$$, $$$7$$$ and $$$4$$$ during the second move.
The picture corresponding to the second test case of the example:
![image](images/cf_1385_F/2.png)
There you can remove vertices $$$7$$$, $$$8$$$ and $$$9$$$ during the first move, then vertices $$$5$$$, $$$6$$$ and $$$10$$$ during the second move and vertices $$$1$$$, $$$3$$$ and $$$4$$$ during the third move.
The picture corresponding to the third test case of the example:
![image](images/cf_1385_F/3.png)
There you can remove vertices $$$5$$$ and $$$7$$$ during the first move, then vertices $$$2$$$ and $$$4$$$ during the second move and vertices $$$1$$$ and $$$6$$$ during the third move.

solutions: ["import sys\ninput = sys.stdin.readline\nfor f in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tneig = [0] * n\n\tfor i in range(n):\n\t\tneig[i] = [0]\n\tfor i in range(n - 1):\n\t\t(a, b) = map(int, input().split())\n\t\ta -= 1\n\t\tb -= 1\n\t\tneig[a][0] += 1\n\t\tneig[b][0] += 1\n\t\tneig[a].append(b)\n\t\tneig[b].append(a)\n\tconleaves = [0] * n\n\tfor i in range(n):\n\t\tconleaves[i] = [0]\n\tgoodvertices = []\n\tmx = 0\n\tfor i in range(n):\n\t\tif neig[i][0] == 1:\n\t\t\tif neig[neig[i][1]][0] > 0:\n\t\t\t\tconleaves[neig[i][1]][0] += 1\n\t\t\t\tconleaves[neig[i][1]].append(i)\n\t\t\t\tneig[i][0] = 0\n\t\t\t\tif conleaves[neig[i][1]][0] == k:\n\t\t\t\t\tgoodvertices.append(neig[i][1])\n\twhile len(goodvertices) > 0:\n\t\tv = goodvertices.pop()\n\t\trem = conleaves[v][0] // k\n\t\tmx += rem\n\t\trest = conleaves[v][0] % k\n\t\tconleaves[v] = conleaves[v][0:rest + 1]\n\t\tconleaves[v][0] = rest\n\t\tneig[v][0] -= rem * k\n\t\tif neig[v][0] == 1:\n\t\t\tfor i in range(1, len(neig[v])):\n\t\t\t\tif neig[neig[v][i]][0] > 0:\n\t\t\t\t\tneig[v][0] = 0\n\t\t\t\t\tconleaves[neig[v][i]][0] += 1\n\t\t\t\t\tconleaves[neig[v][i]].append(v)\n\t\t\t\t\tif conleaves[neig[v][i]][0] == k:\n\t\t\t\t\t\tgoodvertices.append(neig[v][i])\n\tprint(mx)\n", "from sys import stdin, gettrace\nif gettrace():\n\tinputi = input\nelse:\n\n\tdef input():\n\t\treturn next(stdin)[:-1]\n\n\tdef inputi():\n\t\treturn stdin.buffer.readline()\n\ndef readGraph(n, m):\n\tadj = [set() for _ in range(n)]\n\tfor _ in range(m):\n\t\t(u, v) = map(int, input().split())\n\t\tadj[u - 1].add(v - 1)\n\t\tadj[v - 1].add(u - 1)\n\treturn adj\n\ndef readTree(n):\n\treturn readGraph(n, n - 1)\n\ndef solve():\n\t(n, k) = map(int, input().split())\n\tadj = readTree(n)\n\tif k == 1:\n\t\treturn (n - 1, n, k)\n\tleaves = {}\n\tlc = [0] * n\n\tfor i in range(n):\n\t\tif len(adj[i]) == 1:\n\t\t\tlc[adj[i].pop()] += 1\n\t\t\tlc[i] = -1\n\tst = [i for i in range(n) if lc[i] >= k]\n\tres = 0\n\twhile st:\n\t\ti = st.pop()\n\t\tres += lc[i] // k\n\t\tif len(adj[i]) == lc[i] + 1 and lc[i] % k == 0:\n\t\t\tfor a in adj[i]:\n\t\t\t\tif lc[a] != -1:\n\t\t\t\t\tlc[a] += 1\n\t\t\t\t\tif lc[a] == k:\n\t\t\t\t\t\tst.append(a)\n\t\t\tlc[i] = -1\n\t\telse:\n\t\t\tlc[i] %= k\n\treturn (res, n, k)\n\ndef main():\n\tprintproblem = False\n\tt = int(input())\n\tfor i in range(t):\n\t\t(res, _, _) = solve()\n\t\tprint(res)\nmain()\n", "from collections import defaultdict\nimport sys, math\nf = None\ntry:\n\tf = open('q1.input', 'r')\nexcept IOError:\n\tf = sys.stdin\nif 'xrange' in dir(__builtins__):\n\trange = xrange\nsys.setrecursionlimit(10 ** 6)\n\ndef print_case_iterable(case_num, iterable):\n\tprint('Case #{}: {}'.format(case_num, ' '.join(map(str, iterable))))\n\ndef print_case_number(case_num, iterable):\n\tprint('Case #{}: {}'.format(case_num, iterable))\n\ndef print_iterable(A):\n\tprint(' '.join(A))\n\ndef read_int():\n\treturn int(f.readline().strip())\n\ndef read_int_array():\n\treturn [int(x) for x in f.readline().strip().split(' ')]\n\ndef rns():\n\ta = [x for x in f.readline().split(' ')]\n\treturn (int(a[0]), a[1].strip())\n\ndef read_string():\n\treturn list(f.readline().strip())\n\ndef ri():\n\treturn int(f.readline().strip())\n\ndef ria():\n\treturn [int(x) for x in f.readline().strip().split(' ')]\n\ndef rns():\n\ta = [x for x in f.readline().split(' ')]\n\treturn (int(a[0]), a[1].strip())\n\ndef rs():\n\treturn list(f.readline().strip())\n\ndef bi(x):\n\treturn bin(x)[2:]\nfrom collections import deque\nimport math\nNUMBER = 10 ** 9 + 7\n\ndef factorial(n):\n\tM = NUMBER\n\tf = 1\n\tfor i in range(1, n + 1):\n\t\tf = f * i % M\n\treturn f\n\ndef mult(a, b):\n\treturn a * b % NUMBER\n\ndef minus(a, b):\n\treturn (a - b) % NUMBER\n\ndef plus(a, b):\n\treturn (a + b) % NUMBER\n\ndef egcd(a, b):\n\tif a == 0:\n\t\treturn (b, 0, 1)\n\telse:\n\t\t(g, y, x) = egcd(b % a, a)\n\t\treturn (g, x - b // a * y, y)\n\ndef modinv(a):\n\tm = NUMBER\n\t(g, x, y) = egcd(a, m)\n\tif g != 1:\n\t\traise Exception('modular inverse does not exist')\n\telse:\n\t\treturn x % m\n\ndef choose(n, k):\n\tif n < k:\n\t\tassert false\n\treturn mult(factorial(n), modinv(mult(factorial(k), factorial(n - k)))) % NUMBER\nfrom collections import deque, defaultdict\nimport heapq\nfrom types import GeneratorType\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\telse:\n\t\t\tto = f(*args, **kwargs)\n\t\t\twhile True:\n\t\t\t\tif type(to) is GeneratorType:\n\t\t\t\t\tstack.append(to)\n\t\t\t\t\tto = next(to)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\t\t\tif not stack:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tto = stack[-1].send(to)\n\t\t\treturn to\n\treturn wrappedfunc\n\ndef dfs(g, timeIn, timeOut, depths, parents):\n\tcnt = 0\n\tstack = [[1, 0, 0, 0]]\n\twhile stack:\n\t\t(v, neig_i, parent, depth) = stack[-1]\n\t\tparents[v] = parent\n\t\tdepths[v] = depth\n\t\tif neig_i == 0:\n\t\t\ttimeIn[v] = cnt\n\t\t\tcnt += 1\n\t\twhile neig_i < len(g[v]):\n\t\t\tu = g[v][neig_i]\n\t\t\tif u == parent:\n\t\t\t\tneig_i += 1\n\t\t\t\tcontinue\n\t\t\tstack[-1][1] = neig_i + 1\n\t\t\tstack.append([u, 0, v, depth + 1])\n\t\t\tbreak\n\t\tif neig_i == len(g[v]):\n\t\t\tstack.pop()\n\t\t\ttimeOut[v] = cnt\n\t\t\tcnt += 1\ncnt = 0\n\n@bootstrap\ndef dfs(v, adj, timeIn, timeOut, depths, parents, parent=0, depth=0):\n\tglobal cnt\n\tparents[v] = parent\n\tdepths[v] = depth\n\ttimeIn[v] = cnt\n\tcnt += 1\n\tfor u in adj[v]:\n\t\tif u == parent:\n\t\t\tcontinue\n\t\tyield dfs(u, adj, timeIn, timeOut, depths, parents, v, depth + 1)\n\ttimeOut[v] = cnt\n\tcnt += 1\n\tyield\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)\n\ndef get_num_2_5(n):\n\ttwos = 0\n\tfives = 0\n\twhile n > 0 and n % 2 == 0:\n\t\tn //= 2\n\t\ttwos += 1\n\twhile n > 0 and n % 5 == 0:\n\t\tn //= 5\n\t\tfives += 1\n\treturn (twos, fives)\n\ndef shift(a, i, num):\n\tfor _ in range(num):\n\t\t(a[i], a[i + 1], a[i + 2]) = (a[i + 2], a[i], a[i + 1])\n\ndef equal(x, y):\n\treturn abs(x - y) <= 1e-09\n\ndef getAngle(a, b, c):\n\tang = math.degrees(math.atan2(c[1] - b[1], c[0] - b[0]) - math.atan2(a[1] - b[1], a[0] - b[0]))\n\treturn ang + 360 if ang < 0 else ang\n\ndef getLength(a, b):\n\treturn math.sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)\nfrom heapq import heapify, heappush, heappop\n\ndef bfs(adj):\n\ts = set()\n\td = defaultdict(set)\n\tq = deque([])\n\ts.add(0)\n\td[0].add(0)\n\tq.append((0, 0))\n\twhile len(q) > 0:\n\t\t(v, depth) = q.popleft()\n\t\tfor u in adj[v]:\n\t\t\tif u not in s:\n\t\t\t\ts.add(u)\n\t\t\t\td[depth + 1].add(u)\n\t\t\t\tq.append((u, depth + 1))\n\treturn d\n\ndef solution(adj, n, k):\n\tif k == 1:\n\t\treturn n - 1\n\tif n == 2:\n\t\treturn 0\n\tleaves = [set() for i in range(n)]\n\tstack = []\n\tfor v in range(n):\n\t\tif len(adj[v]) == 1:\n\t\t\tleaves[adj[v].pop()].add(v)\n\tfor v in range(n):\n\t\tif len(leaves[v]) >= k:\n\t\t\tstack.append(v)\n\tcnt = 0\n\twhile len(stack) > 0:\n\t\tcnt += 1\n\t\tv = stack.pop()\n\t\tls = set()\n\t\ttry:\n\t\t\tfor i in range(k):\n\t\t\t\tls.add(leaves[v].pop())\n\t\texcept:\n\t\t\treturn f'{cnt}000{n}000{k}'\n\t\tadj[v] -= ls\n\t\tif len(adj[v]) == 0:\n\t\t\tcontinue\n\t\telif len(adj[v]) == 1:\n\t\t\tu = adj[v].pop()\n\t\t\tleaves[u].add(v)\n\t\t\tif len(leaves[u]) == k:\n\t\t\t\tstack.append(u)\n\t\telif len(leaves[v]) >= k:\n\t\t\tstack.append(v)\n\treturn cnt\n\ndef main():\n\tT = 1\n\tT = ri()\n\tfor i in range(T):\n\t\t(n, k) = ria()\n\t\tadj = [set() for _ in range(n)]\n\t\tfor _ in range(n - 1):\n\t\t\t(a, b) = ria()\n\t\t\ta -= 1\n\t\t\tb -= 1\n\t\t\tadj[a].add(b)\n\t\t\tadj[b].add(a)\n\t\tx = solution(adj, n, k)\n\t\tif 'xrange' not in dir(__builtins__):\n\t\t\tprint(x)\n\t\telse:\n\t\t\t(print >> output, str(x))\n\tif 'xrange' in dir(__builtins__):\n\t\tprint(output.getvalue())\n\t\toutput.close()\nif 'xrange' in dir(__builtins__):\n\timport cStringIO\n\toutput = cStringIO.StringIO()\nmain()\n", "import sys\n\ndef rs():\n\treturn sys.stdin.readline().rstrip()\n\ndef ri():\n\treturn int(sys.stdin.readline())\n\ndef ria():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef ws(s):\n\tsys.stdout.write(s)\n\tsys.stdout.write('\\n')\n\ndef wi(n):\n\tsys.stdout.write(str(n))\n\tsys.stdout.write('\\n')\n\ndef wia(a, sep=' '):\n\tsys.stdout.write(sep.join([str(x) for x in a]))\n\tsys.stdout.write('\\n')\n\ndef solve(n, k, ee):\n\tg = [[] for _ in range(n)]\n\tfor e in ee:\n\t\tg[e[0]].append(e[1])\n\t\tg[e[1]].append(e[0])\n\tleafs = [[] for _ in range(n)]\n\tfor i in range(n):\n\t\tif len(g[i]) == 1:\n\t\t\tleafs[g[i][0]].append(i)\n\tdeg = [len(g[i]) for i in range(n)]\n\tdeleted = set()\n\tans = 0\n\tq = [i for i in range(n) if len(leafs[i]) >= k]\n\twhile q:\n\t\tv = q.pop()\n\t\tif v in deleted:\n\t\t\tcontinue\n\t\tx = len(leafs[v]) // k\n\t\tcnt = x * k\n\t\tans += x\n\t\twhile cnt > 0:\n\t\t\tw = leafs[v].pop()\n\t\t\tdeleted.add(w)\n\t\t\tcnt -= 1\n\t\tdeg[v] -= x * k\n\t\tif deg[v] == 1:\n\t\t\tfor w in g[v]:\n\t\t\t\tif w not in deleted:\n\t\t\t\t\tleafs[w].append(v)\n\t\t\t\t\tif len(leafs[w]) == k:\n\t\t\t\t\t\tq.append(w)\n\treturn ans\n\ndef main():\n\tfor _ in range(ri()):\n\t\t(n, k) = ria()\n\t\te = []\n\t\tfor i in range(n - 1):\n\t\t\t(xi, yi) = ria()\n\t\t\txi -= 1\n\t\t\tyi -= 1\n\t\t\te.append([xi, yi])\n\t\twi(solve(n, k, e))\nmain()\n", "import sys\n\ndef input():\n\treturn sys.stdin.readline().rstrip()\n\ndef input_split():\n\treturn [int(i) for i in input().split()]\ntestCases = int(input())\nanswers = []\nfor _ in range(testCases):\n\t(n, k) = input_split()\n\tpresent = [True for i in range(n)]\n\tedges = [set() for _ in range(n)]\n\tfor _ in range(n - 1):\n\t\t(x, y) = input_split()\n\t\tx -= 1\n\t\ty -= 1\n\t\tedges[x].add(y)\n\t\tedges[y].add(x)\n\tdeletions = 0\n\tdeleted_till_now = set()\n\tleaves = [0 for i in range(n)]\n\tfor i in range(n):\n\t\tfor node in edges[i]:\n\t\t\tif len(edges[node]) == 1:\n\t\t\t\tleaves[i] += 1\n\tpending = []\n\tfor i in range(n):\n\t\tif leaves[i] >= k:\n\t\t\tpending.append(i)\n\twhile len(pending) != 0:\n\t\tlast = pending.pop()\n\t\tnum = leaves[last]\n\t\tif num < k or not present[last]:\n\t\t\tpass\n\t\telse:\n\t\t\tleaves_removed = num - num % k\n\t\t\tdels = num // k\n\t\t\tdeletions += dels\n\t\t\tto_remove = set()\n\t\t\tfor node in edges[last]:\n\t\t\t\tif len(edges[node]) == 1:\n\t\t\t\t\tto_remove.add(node)\n\t\t\t\t\tpresent[node] = False\n\t\t\t\t\tif len(to_remove) == leaves_removed:\n\t\t\t\t\t\tbreak\n\t\t\tedges[last] = edges[last].difference(to_remove)\n\t\t\tleaves[last] = num % k\n\t\t\tif len(edges[last]) == 1:\n\t\t\t\tparent = list(edges[last])[0]\n\t\t\t\tleaves[parent] += 1\n\t\t\t\tif leaves[parent] >= k:\n\t\t\t\t\tpending.append(parent)\n\tanswers.append(deletions)\nprint(*answers, sep='\\n')\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tadj = [[] for _ in range(n)]\n\tfor _ in range(n - 1):\n\t\t(a, b) = map(lambda s: int(s) - 1, input().split())\n\t\tadj[a].append(b)\n\t\tadj[b].append(a)\n\tif k == 1:\n\t\tprint(n - 1)\n\t\tcontinue\n\tV = [False] * n\n\tC = [0] * n\n\tQ = []\n\n\tdef is_leaf(i):\n\t\treturn len(adj[i]) == 1\n\n\tdef enq(i):\n\t\tif V[i] or sum((is_leaf(j) for j in adj[i])) < k:\n\t\t\treturn\n\t\tV[i] = True\n\t\tQ.append(i)\n\tfor (i, a) in enumerate(adj):\n\t\tif len(a) == 1:\n\t\t\tj = a[0]\n\t\t\tC[j] += 1\n\t\t\tif C[j] >= k and (not V[j]):\n\t\t\t\tV[j] = True\n\t\t\t\tQ.append(j)\n\tres = 0\n\tfor i in Q:\n\t\tV[i] = False\n\t\tnadj = []\n\t\tleafc = []\n\t\tfor j in adj[i]:\n\t\t\tif is_leaf(j):\n\t\t\t\tleafc.append(j)\n\t\t\telse:\n\t\t\t\tnadj.append(j)\n\t\twhile len(leafc) >= k:\n\t\t\tres += 1\n\t\t\tfor _ in range(k):\n\t\t\t\tleafc.pop()\n\t\tnadj.extend(leafc)\n\t\tadj[i] = nadj\n\t\tif is_leaf(i):\n\t\t\tenq(nadj[0])\n\tprint(res)\n", "import sys\nimport heapq\ninpy = [int(x) for x in sys.stdin.read().split()]\nt = inpy[0]\nindex = 1\nfor _ in range(t):\n\t(n, k) = (inpy[index], inpy[index + 1])\n\tindex += 2\n\tedges = [set() for _ in range(n + 1)]\n\tmemo = [0] * (n + 1)\n\tfor i in range(n - 1):\n\t\t(a, b) = (inpy[index], inpy[index + 1])\n\t\tindex += 2\n\t\tedges[a].add(b)\n\t\tedges[b].add(a)\n\t(que, no) = (set(), set())\n\tfor i in range(1, n + 1):\n\t\tif i not in no and len(edges[i]) == 1:\n\t\t\tx = edges[i].pop()\n\t\t\tmemo[x] += 1\n\t\t\tedges[x].remove(i)\n\t\t\tno.add(x)\n\tfor i in range(1, n + 1):\n\t\tif memo[i] >= k:\n\t\t\tque.add(i)\n\tres = 0\n\twhile que:\n\t\tx = que.pop()\n\t\tres += memo[x] // k\n\t\tmemo[x] = memo[x] % k\n\t\tif len(edges[x]) == 1 and memo[x] == 0:\n\t\t\ty = edges[x].pop()\n\t\t\tmemo[y] += 1\n\t\t\tif memo[y] >= k:\n\t\t\t\tque.add(y)\n\t\t\tedges[y].remove(x)\n\tprint(res)\n", "import collections\nt = int(input())\nfor i in range(t):\n\t(n, k) = map(int, input().split())\n\tg = collections.defaultdict(list)\n\tfor j in range(n - 1):\n\t\t(x, y) = map(int, input().split())\n\t\tg[x].append(y)\n\t\tg[y].append(x)\n\tif k == 1:\n\t\tprint(n - 1)\n\telse:\n\t\tleaf = {}\n\t\ta = set()\n\t\tb = {}\n\t\tl = {}\n\t\tfor v in g:\n\t\t\tp = 0\n\t\t\tq = 0\n\t\t\tfor u in g[v]:\n\t\t\t\tq = q + 1\n\t\t\t\tif len(g[u]) == 1:\n\t\t\t\t\tp = p + 1\n\t\t\t\t\tleaf[u] = 1\n\t\t\tif p >= k:\n\t\t\t\ta.add(v)\n\t\t\tb[v] = p\n\t\t\tl[v] = q\n\t\tc = 0\n\t\twhile a != set():\n\t\t\tp = a.pop()\n\t\t\tte = b[p] // k\n\t\t\tc = c + te\n\t\t\tif b[p] % k == 0 and l[p] - te * k == 1:\n\t\t\t\tleaf[p] = 1\n\t\t\t\tb[p] = 0\n\t\t\t\tl[p] = 1\n\t\t\t\tfor v in g[p]:\n\t\t\t\t\tif v not in leaf:\n\t\t\t\t\t\tb[v] = b[v] + 1\n\t\t\t\t\t\tif b[v] >= k:\n\t\t\t\t\t\t\ta.add(v)\n\t\t\t\t\t\tbreak\n\t\t\telse:\n\t\t\t\tb[p] = b[p] - te * k\n\t\t\t\tl[p] = l[p] - te * k\n\t\tprint(c)\n", "from sys import stdin\nfrom collections import deque\ninput = stdin.readline\nt = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\tadj = [[] for _ in range(n)]\n\tfrd = [set() for _ in range(n)]\n\tcnt = [0] * n\n\tis_leaf = [False] * n\n\tfor _ in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tu -= 1\n\t\tv -= 1\n\t\tadj[u].append(v)\n\t\tadj[v].append(u)\n\tif k == 1:\n\t\tprint(n - 1)\n\t\tcontinue\n\tfor i in range(n):\n\t\tif len(adj[i]) == 1:\n\t\t\tis_leaf[i] = True\n\t\t\tcnt[adj[i][0]] += 1\n\tq = deque()\n\tfor u in range(n):\n\t\tif cnt[u] >= k:\n\t\t\tq.append(u)\n\t\tfor v in adj[u]:\n\t\t\tif not is_leaf[v]:\n\t\t\t\tfrd[u].add(v)\n\tans = 0\n\twhile len(q) > 0:\n\t\tu = q.popleft()\n\t\tans += cnt[u] // k\n\t\tcnt[u] %= k\n\t\tif cnt[u] == 0 and len(frd[u]) == 1:\n\t\t\tp = frd[u].pop()\n\t\t\tfrd[p].remove(u)\n\t\t\tcnt[p] += 1\n\t\t\tif cnt[p] >= k:\n\t\t\t\tq.append(p)\n\tprint(ans)\n", "def crop_set(s, n):\n\tnew = set()\n\tit = iter(s)\n\tfor i in range(n):\n\t\tnew.add(next(it))\n\treturn new\n\nclass Vertex:\n\t__slots__ = ('vertexes', 'leaves', 'graph')\n\n\tdef __init__(self, graph):\n\t\tself.vertexes = set()\n\t\tself.leaves = 0\n\t\tself.graph = graph\n\n\tdef try_to_leave(self):\n\t\tif len(self.vertexes) + self.leaves == 1:\n\t\t\tif self.vertexes:\n\t\t\t\tparent = self.vertexes.pop()\n\t\t\t\tparent.vertexes.remove(self)\n\t\t\t\tparent.leaves += 1\n\t\t\t\tparent.update()\n\t\t\t\tself.vertexes.add(parent)\n\n\tdef update(self):\n\t\tself.graph[self] = self.leaves\n\nclass Tree:\n\n\tdef __init__(self, n, k):\n\t\tself.k = k\n\t\tself.lc = [set() for _ in range(n // k + 1)]\n\t\tself.dlc = dict()\n\t\tself.max = 0\n\n\tdef add_vertex(self, v):\n\t\tself.dlc[v] = 0\n\t\tself.lc[0].add(v)\n\t\tv.update()\n\n\tdef __setitem__(self, key, value):\n\t\tvalue = value // self.k\n\t\tif self.max == self.dlc[key] > value:\n\t\t\tself.lc[self.max].discard(key)\n\t\t\twhile not self.lc[self.max]:\n\t\t\t\tself.max -= 1\n\t\telse:\n\t\t\tself.lc[self.dlc[key]].discard(key)\n\t\tif value > self.max:\n\t\t\tself.max = value\n\t\tself.dlc[key] = value\n\t\tself.lc[value].add(key)\n\ndef to_int_decrement(s):\n\treturn int(s) - 1\n\ndef solve():\n\t(n, k) = list(map(int, input().split()))\n\ttree = Tree(n, k)\n\tgraph = [Vertex(tree) for _ in range(n)]\n\tfor _ in range(n - 1):\n\t\t(a, b) = list(map(to_int_decrement, input().split()))\n\t\tgraph[a].vertexes.add(graph[b])\n\t\tgraph[b].vertexes.add(graph[a])\n\tif k == 1:\n\t\tprint(n - 1)\n\t\treturn\n\tfor v in graph:\n\t\ttree.add_vertex(v)\n\tfor v in graph:\n\t\tv.try_to_leave()\n\tc = 0\n\twhile tree.max > 0:\n\t\tv = tree.lc[tree.max].pop()\n\t\tc += v.leaves // k\n\t\tv.leaves -= v.leaves // k * k\n\t\tv.try_to_leave()\n\t\tv.update()\n\tprint(c)\nfor _ in range(int(input())):\n\tsolve()\n", "from bisect import *\nfrom collections import *\nfrom math import gcd, ceil, sqrt, floor, inf\nfrom heapq import *\nfrom itertools import *\nfrom operator import add, mul, sub, xor, truediv, floordiv\nfrom functools import *\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\ndef RL():\n\treturn map(int, sys.stdin.readline().rstrip().split())\n\ndef RLL():\n\treturn list(map(int, sys.stdin.readline().rstrip().split()))\n\ndef N():\n\treturn int(input())\nfrom types import GeneratorType\n\ndef bootstrap(f, stack=[]):\n\n\tdef wrappedfunc(*args, **kwargs):\n\t\tif stack:\n\t\t\treturn f(*args, **kwargs)\n\t\telse:\n\t\t\tto = f(*args, **kwargs)\n\t\t\twhile True:\n\t\t\t\tif type(to) is GeneratorType:\n\t\t\t\t\tstack.append(to)\n\t\t\t\t\tto = next(to)\n\t\t\t\telse:\n\t\t\t\t\tstack.pop()\n\t\t\t\t\tif not stack:\n\t\t\t\t\t\tbreak\n\t\t\t\t\tto = stack[-1].send(to)\n\t\t\treturn to\n\treturn wrappedfunc\nfarr = [1]\nifa = []\n\ndef fact(x, mod=0):\n\tif mod:\n\t\twhile x >= len(farr):\n\t\t\tfarr.append(farr[-1] * len(farr) % mod)\n\telse:\n\t\twhile x >= len(farr):\n\t\t\tfarr.append(farr[-1] * len(farr))\n\treturn farr[x]\n\ndef ifact(x, mod):\n\tglobal ifa\n\tifa.append(pow(farr[-1], mod - 2, mod))\n\tfor i in range(x, 0, -1):\n\t\tifa.append(ifa[-1] * i % mod)\n\tifa = ifa[::-1]\n\ndef per(i, j, mod=0):\n\tif i < j:\n\t\treturn 0\n\tif not mod:\n\t\treturn fact(i) // fact(i - j)\n\treturn farr[i] * ifa[i - j] % mod\n\ndef com(i, j, mod=0):\n\tif i < j:\n\t\treturn 0\n\tif not mod:\n\t\treturn per(i, j) // fact(j)\n\treturn per(i, j, mod) * ifa[j] % mod\n\ndef catalan(n):\n\treturn com(2 * n, n) // (n + 1)\n\ndef linc(f, t, l, r):\n\twhile l < r:\n\t\tmid = (l + r) // 2\n\t\tif t > f(mid):\n\t\t\tl = mid + 1\n\t\telse:\n\t\t\tr = mid\n\treturn l\n\ndef rinc(f, t, l, r):\n\twhile l < r:\n\t\tmid = (l + r + 1) // 2\n\t\tif t < f(mid):\n\t\t\tr = mid - 1\n\t\telse:\n\t\t\tl = mid\n\treturn l\n\ndef ldec(f, t, l, r):\n\twhile l < r:\n\t\tmid = (l + r) // 2\n\t\tif t < f(mid):\n\t\t\tl = mid + 1\n\t\telse:\n\t\t\tr = mid\n\treturn l\n\ndef rdec(f, t, l, r):\n\twhile l < r:\n\t\tmid = (l + r + 1) // 2\n\t\tif t > f(mid):\n\t\t\tr = mid - 1\n\t\telse:\n\t\t\tl = mid\n\treturn l\n\ndef isprime(n):\n\tfor i in range(2, int(n ** 0.5) + 1):\n\t\tif n % i == 0:\n\t\t\treturn False\n\treturn True\n\ndef binfun(x):\n\tc = 0\n\tfor w in arr:\n\t\tc += ceil(w / x)\n\treturn c\n\ndef lowbit(n):\n\treturn n & -n\n\ndef inverse(a, m):\n\ta %= m\n\tif a <= 1:\n\t\treturn a\n\treturn (1 - inverse(m, a) * m) // a % m\n\nclass BIT:\n\n\tdef __init__(self, arr):\n\t\tself.arr = arr\n\t\tself.n = len(arr) - 1\n\n\tdef update(self, x, v):\n\t\twhile x <= self.n:\n\t\t\tself.arr[x] += v\n\t\t\tx += x & -x\n\n\tdef query(self, x):\n\t\tans = 0\n\t\twhile x:\n\t\t\tans += self.arr[x]\n\t\t\tx &= x - 1\n\t\treturn ans\n\nclass DSU:\n\n\tdef __init__(self, n):\n\t\tself.c = [-1] * n\n\n\tdef same(self, x, y):\n\t\treturn self.find(x) == self.find(y)\n\n\tdef find(self, x):\n\t\tif self.c[x] < 0:\n\t\t\treturn x\n\t\tself.c[x] = self.find(self.c[x])\n\t\treturn self.c[x]\n\n\tdef union(self, u, v):\n\t\t(u, v) = (self.find(u), self.find(v))\n\t\tif u == v:\n\t\t\treturn False\n\t\tif self.c[u] < self.c[v]:\n\t\t\t(u, v) = (v, u)\n\t\tself.c[u] += self.c[v]\n\t\tself.c[v] = u\n\t\treturn True\n\n\tdef size(self, x):\n\t\treturn -self.c[self.find(x)]\n\nclass UFS:\n\n\tdef __init__(self, n):\n\t\tself.parent = [i for i in range(n)]\n\t\tself.ranks = [0] * n\n\n\tdef find(self, x):\n\t\tif x != self.parent[x]:\n\t\t\tself.parent[x] = self.find(self.parent[x])\n\t\treturn self.parent[x]\n\n\tdef union(self, u, v):\n\t\t(pu, pv) = (self.find(u), self.find(v))\n\t\tif pu == pv:\n\t\t\treturn False\n\t\tif self.ranks[pu] >= self.ranks[pv]:\n\t\t\tself.parent[pv] = pu\n\t\t\tif self.ranks[pv] == self.ranks[pu]:\n\t\t\t\tself.ranks[pu] += 1\n\t\telse:\n\t\t\tself.parent[pu] = pv\n\ndef Prime(n):\n\tc = 0\n\tprime = []\n\tflag = [0] * (n + 1)\n\tfor i in range(2, n + 1):\n\t\tif not flag[i]:\n\t\t\tprime.append(i)\n\t\t\tc += 1\n\t\tfor j in range(c):\n\t\t\tif i * prime[j] > n:\n\t\t\t\tbreak\n\t\t\tflag[i * prime[j]] = prime[j]\n\t\t\tif i % prime[j] == 0:\n\t\t\t\tbreak\n\treturn prime\n\ndef dij(s, graph):\n\td = {}\n\td[s] = 0\n\theap = [(0, s)]\n\tseen = set()\n\twhile heap:\n\t\t(dis, u) = heappop(heap)\n\t\tif u in seen:\n\t\t\tcontinue\n\t\tfor v in graph[u]:\n\t\t\tif v not in d or d[v] > d[u] + graph[u][v]:\n\t\t\t\td[v] = d[u] + graph[u][v]\n\t\t\t\theappush(heap, (d[v], v))\n\treturn d\n\ndef GP(it):\n\treturn [[ch, len(list(g))] for (ch, g) in groupby(it)]\n\nclass DLN:\n\n\tdef __init__(self, val):\n\t\tself.val = val\n\t\tself.pre = None\n\t\tself.next = None\n\n@bootstrap\ndef dfs(r, p):\n\tif len(g[r]) == 1 and p != -1:\n\t\tisl[r] = 1\n\t\tyield 1\n\ttmp = 0\n\tfor ch in g[r]:\n\t\tif ch != p:\n\t\t\ttmp += (yield dfs(ch, r))\n\tcnt[r] += tmp\n\tif p == -1 and len(g[r]) == 1:\n\t\tisl[r] = 1\n\t\tcnt[g[r][0]] += 1\n\tyield 0\nt = N()\nfor i in range(t):\n\t(n, k) = RL()\n\tg = [[] for i in range(n + 1)]\n\tfor i in range(n - 1):\n\t\t(u, v) = RL()\n\t\tg[u].append(v)\n\t\tg[v].append(u)\n\tif k == 1:\n\t\tprint(n - 1)\n\t\tcontinue\n\tisl = [0] * (n + 1)\n\tcnt = [0] * (n + 1)\n\tdfs(1, -1)\n\tq = deque()\n\tans = 0\n\tvis = [0] * (n + 1)\n\tfor i in range(1, n + 1):\n\t\tif cnt[i] >= k:\n\t\t\tq.append(i)\n\t\t\tvis[i] = 1\n\tact = cnt.copy()\n\twhile q:\n\t\tu = q.popleft()\n\t\tans += act[u] // k\n\t\tact[u] %= k\n\t\tvis[u] = 0\n\t\tif act[u] == 0 and len(g[u]) - cnt[u] == 1:\n\t\t\tfor v in g[u]:\n\t\t\t\tif not isl[v]:\n\t\t\t\t\tcnt[v] += 1\n\t\t\t\t\tact[v] += 1\n\t\t\t\t\tisl[u] = 1\n\t\t\t\t\tif act[v] >= k and (not vis[v]):\n\t\t\t\t\t\tq.append(v)\n\t\t\t\t\t\tvis[v] = 1\n\t\t\t\t\tbreak\n\tprint(ans)\n", "from collections import defaultdict, deque\nfor _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tg = defaultdict(list)\n\tfor i in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tu -= 1\n\t\tv -= 1\n\t\tg[u].append(v)\n\t\tg[v].append(u)\n\tif k == 1:\n\t\tprint(n - 1)\n\t\tcontinue\n\tindeg = [0] * n\n\trevdeg = [0] * n\n\tdq = deque()\n\tfor i in range(n):\n\t\tindeg[i] = len(g[i])\n\t\tfor j in g[i]:\n\t\t\tif len(g[j]) == 1:\n\t\t\t\trevdeg[i] += 1\n\t\tif revdeg[i] >= k:\n\t\t\tdq.appendleft(i)\n\tans = 0\n\twhile dq:\n\t\tans += 1\n\t\tu = dq.pop()\n\t\tindeg[u] -= k\n\t\trevdeg[u] -= k\n\t\tif revdeg[u] >= k:\n\t\t\tdq.appendleft(u)\n\t\telif indeg[u] == 1 and revdeg[u] == 0:\n\t\t\tfor j in g[u]:\n\t\t\t\trevdeg[j] += 1\n\t\t\t\tif revdeg[j] == k:\n\t\t\t\t\tdq.appendleft(j)\n\tprint(ans)\n", "def main():\n\tfrom heapq import heapify, heappop, heappush\n\timport sys\n\tinput = sys.stdin.readline\n\tfor __ in [0] * int(input()):\n\t\t(N, K) = list(map(int, input().split()))\n\t\tG = [[] for _ in [0] * N]\n\t\tdeg = [0] * N\n\t\tfor _ in [0] * (N - 1):\n\t\t\t(a, b) = list(map(int, input().split()))\n\t\t\ta -= 1\n\t\t\tb -= 1\n\t\t\tG[a].append(b)\n\t\t\tG[b].append(a)\n\t\t\tdeg[a] += 1\n\t\t\tdeg[b] += 1\n\t\tif K == 1:\n\t\t\tprint(N - 1)\n\t\t\tcontinue\n\t\tleaf = [0] * N\n\t\tfor v in range(N):\n\t\t\tif deg[v] == 1:\n\t\t\t\tu = G[v][0]\n\t\t\t\tleaf[u] += 1\n\t\tL = [(-l, v) for (v, l) in enumerate(leaf) if l >= K]\n\t\theapify(L)\n\t\tans = 0\n\t\twhile L:\n\t\t\t(l, v) = heappop(L)\n\t\t\tif -l != leaf[v]:\n\t\t\t\tcontinue\n\t\t\t(q, r) = divmod(-l, K)\n\t\t\tans += q\n\t\t\tleaf[v] = r\n\t\t\tdeg[v] -= K * q\n\t\t\tp = -1\n\t\t\tcnt = 0\n\t\t\tfor u in G[v]:\n\t\t\t\tif deg[u] == 1 and cnt < K * q:\n\t\t\t\t\tcnt += 1\n\t\t\t\t\tdeg[u] = 0\n\t\t\t\telif deg[u]:\n\t\t\t\t\tp = u\n\t\t\t\tif cnt == K * q and (deg[v] != 1 or p != -1):\n\t\t\t\t\tbreak\n\t\t\tif deg[v] == 1:\n\t\t\t\tif p != -1:\n\t\t\t\t\tleaf[p] += 1\n\t\t\t\t\tif leaf[p] >= K:\n\t\t\t\t\t\theappush(L, (-leaf[p], p))\n\t\tprint(ans)\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "from collections import defaultdict, deque\nimport sys\ninput = sys.stdin.readline\nt = int(input())\nfor ii in range(t):\n\tgraph = defaultdict(list)\n\t(n, k) = map(int, input().split())\n\tfor i in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tgraph[u].append(v)\n\t\tgraph[v].append(u)\n\tif k == 1:\n\t\tprint(n - 1)\n\telse:\n\t\tleaves = deque()\n\t\tfor i in graph:\n\t\t\tif len(graph[i]) == 1:\n\t\t\t\tleaves.append(i)\n\t\ttreecount = [0] * (n + 1)\n\t\tfor i in leaves:\n\t\t\ttreecount[i] = -1\n\t\tans = 0\n\t\twhile leaves:\n\t\t\tsize = len(leaves)\n\t\t\tfor j in range(size):\n\t\t\t\tvertex = leaves.popleft()\n\t\t\t\ttreecount[vertex] = 10000000\n\t\t\t\tfor i in graph[vertex]:\n\t\t\t\t\tif treecount[i] != -1 and treecount[i] < 10000000:\n\t\t\t\t\t\ttreecount[i] += 1\n\t\t\t\t\t\tif treecount[i] % k == 0:\n\t\t\t\t\t\t\tans += 1\n\t\t\t\t\t\t\tif treecount[i] == len(graph[i]) - 1:\n\t\t\t\t\t\t\t\ttreecount[i] = -1\n\t\t\t\t\t\t\t\tleaves.append(i)\n\t\telse:\n\t\t\tsys.stdout.write(str(ans) + '\\n')\n", "from collections import defaultdict, deque\nimport heapq\n\nclass Graph:\n\n\tdef __init__(self, vertices):\n\t\tself.graph = [defaultdict() for x in range(vertices + 1)]\n\t\tself.V = vertices\n\n\tdef addEdge(self, u, v, w=1):\n\t\tself.graph[u][v] = w\n\t\tself.graph[v][u] = w\n\n\tdef solve(self, in_degree, k):\n\t\tflag = [0] * (n + 1)\n\t\tleaves = defaultdict(int)\n\t\tfor i in range(1, self.V + 1):\n\t\t\tif in_degree[i] == 1:\n\t\t\t\tleaves[list(self.graph[i].keys())[0]] += 1\n\t\t\t\tflag[i] = 1\n\t\tq = set()\n\t\tfor p in leaves:\n\t\t\tif leaves[p] >= k:\n\t\t\t\tq.add(p)\n\t\tans = 0\n\t\twhile q:\n\t\t\tnow = q.pop()\n\t\t\tans += 1\n\t\t\tleaves[now] -= k\n\t\t\tif leaves[now] >= k:\n\t\t\t\tq.add(now)\n\t\t\telif leaves[now] == 0:\n\t\t\t\t(conn, par) = (0, 0)\n\t\t\t\tfor i in self.graph[now]:\n\t\t\t\t\tif flag[i] == 0:\n\t\t\t\t\t\tconn += 1\n\t\t\t\t\t\tpar = i\n\t\t\t\tif conn == 1:\n\t\t\t\t\tflag[now] = 1\n\t\t\t\t\tleaves[par] += 1\n\t\t\t\t\tif leaves[par] == k:\n\t\t\t\t\t\tq.add(par)\n\t\treturn ans\nfor _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tg = Graph(n)\n\tin_degree = [0] * (n + 1)\n\tfor _ in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tg.addEdge(u, v)\n\t\tin_degree[u] += 1\n\t\tin_degree[v] += 1\n\tif k == 1:\n\t\tprint(n - 1)\n\telse:\n\t\tprint(g.solve(in_degree, k))\n", "t = int(input())\nMaxn = 210000\nwhile t > 0:\n\tt -= 1\n\t(n, k) = map(int, input().split())\n\td = [0] * (n + 1)\n\tbj = [0] * (n + 1)\n\tflag = [0] * (n + 1)\n\tto = [[]]\n\tfor i in range(0, n):\n\t\tto.append([])\n\tfor i in range(1, n):\n\t\t(u, v) = map(int, input().split())\n\t\tto[u].append(v)\n\t\tto[v].append(u)\n\t\td[u] += 1\n\t\td[v] += 1\n\tif k == 1:\n\t\tprint(n - 1)\n\t\tcontinue\n\tque = []\n\tfor i in range(1, n + 1):\n\t\tif d[i] == 1:\n\t\t\tbj[to[i][0]] += 1\n\t\t\tflag[i] = 1\n\tfor i in range(1, n + 1):\n\t\tif bj[i] >= k:\n\t\t\tque.append(i)\n\tans = 0\n\twhile len(que):\n\t\tnow = que.pop()\n\t\tans += 1\n\t\tbj[now] -= k\n\t\tif bj[now] >= k:\n\t\t\tque.append(now)\n\t\t\tcontinue\n\t\tif bj[now]:\n\t\t\tcontinue\n\t\tsxz = 0\n\t\tnh = 0\n\t\tfor i in to[now]:\n\t\t\tif flag[i] == 0:\n\t\t\t\tsxz += 1\n\t\t\t\tnh = i\n\t\tif sxz == 1:\n\t\t\tflag[now] = 1\n\t\t\tbj[nh] += 1\n\t\t\tif bj[nh] == k:\n\t\t\t\tque.append(nh)\n\tprint(ans)\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nfor _ in range(t):\n\t(n, k) = map(int, input().split())\n\tedge = [[] for i in range(n)]\n\tfor i in range(n - 1):\n\t\t(x, y) = map(int, input().split())\n\t\tedge[x - 1].append(y - 1)\n\t\tedge[y - 1].append(x - 1)\n\tLEAF = [[] for i in range(n)]\n\tV = [0] * n\n\tfor i in range(n):\n\t\tif len(edge[i]) == 1:\n\t\t\tLEAF[edge[i][0]].append(i)\n\tQ = [i for i in range(n) if len(LEAF[i]) >= k]\n\tD = [len(edge[i]) for i in range(n)]\n\tN = edge\n\tans = 0\n\twhile Q:\n\t\tv = Q.pop()\n\t\tif V[v] == 1:\n\t\t\tcontinue\n\t\tq = len(LEAF[v]) // k\n\t\tcount = q * k\n\t\tans += q\n\t\twhile count:\n\t\t\tdv = LEAF[v].pop()\n\t\t\tV[dv] = 1\n\t\t\tcount -= 1\n\t\tD[v] -= q * k\n\t\tif D[v] == 1:\n\t\t\tfor nv in N[v]:\n\t\t\t\tif V[nv] == 0:\n\t\t\t\t\tLEAF[nv].append(v)\n\t\t\t\t\tif len(LEAF[nv]) == k:\n\t\t\t\t\t\tQ.append(nv)\n\t\t\t\t\tbreak\n\tif k == 1:\n\t\tprint(n - 1)\n\telse:\n\t\tprint(ans)\n", "from sys import stdin, stdout\nimport functools\nimport sys, os, math\nT = int(input())\nfor _ in range(T):\n\t(N, K) = map(int, input().split())\n\tDS = [0] * (N + 1)\n\tLeafNum = [0] * (N + 1)\n\tg = [[] for _ in range(N + 1)]\n\tfor _ in range(N - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tDS[u] += 1\n\t\tDS[v] += 1\n\t\tg[u].append(v)\n\t\tg[v].append(u)\n\tfor u in range(1, N + 1):\n\t\tif DS[u] == 1:\n\t\t\tfor v in g[u]:\n\t\t\t\tLeafNum[v] += 1\n\tif K == 1:\n\t\tprint(N - 1)\n\t\tcontinue\n\tq = set()\n\tfor u in range(1, N + 1):\n\t\tif LeafNum[u] >= K:\n\t\t\tq.add(u)\n\tans = 0\n\twhile len(q) > 0:\n\t\tu = q.pop()\n\t\tnl = LeafNum[u]\n\t\tans += int(nl / K)\n\t\tLeafNum[u] = nl % K\n\t\tdn = int(nl / K) * K\n\t\tDS[u] -= int(nl / K) * K\n\t\tif DS[u] == 1:\n\t\t\tfor v in g[u]:\n\t\t\t\tif DS[v] == 1 and dn > 0:\n\t\t\t\t\tdn -= 1\n\t\t\t\t\tcontinue\n\t\t\t\tLeafNum[v] += 1\n\t\t\t\tif LeafNum[v] >= K and v not in q:\n\t\t\t\t\tq.add(v)\n\tprint(ans)\n", "import sys\ninput = sys.stdin.readline\nf = lambda : map(int, input().split())\nfor _ in range(int(input())):\n\t(n, k) = f()\n\tg = [[] for i in range(n + 1)]\n\tdeg = [0] * (n + 1)\n\tisLeaf = [0] * (n + 1)\n\tnumLeaves = [0] * (n + 1)\n\tq = []\n\tans = 0\n\tfor __ in range(n - 1):\n\t\t(a, b) = f()\n\t\tg[a].append(b)\n\t\tg[b].append(a)\n\t\tdeg[a] += 1\n\t\tdeg[b] += 1\n\tif k == 1:\n\t\tprint(n - 1)\n\t\tcontinue\n\tfor i in range(1, n + 1):\n\t\tif deg[i] == 1:\n\t\t\tisLeaf[i] = True\n\t\t\tnumLeaves[g[i][0]] += 1\n\tfor i in range(1, n + 1):\n\t\tif numLeaves[i] >= k:\n\t\t\tq.append(i)\n\twhile len(q):\n\t\tu = q.pop()\n\t\tans += 1\n\t\tnumLeaves[u] -= k\n\t\tif numLeaves[u]:\n\t\t\tif numLeaves[u] >= k:\n\t\t\t\tq.append(u)\n\t\t\tcontinue\n\t\t(numP, v) = (0, 0)\n\t\tfor i in g[u]:\n\t\t\tif not isLeaf[i]:\n\t\t\t\tnumP += 1\n\t\t\t\tv = i\n\t\tif numP == 1:\n\t\t\tnumLeaves[v] += 1\n\t\t\tisLeaf[u] = True\n\t\t\tif numLeaves[v] == k:\n\t\t\t\tq.append(v)\n\tprint(ans)\n", "from bisect import bisect_left as bl\nfrom bisect import bisect_right as br\nfrom heapq import heappush, heappop, heapify\nimport math\nfrom collections import *\nfrom functools import reduce, cmp_to_key\nimport sys\ninput = sys.stdin.readline\nM = mod = 998244353\n\ndef factors(n):\n\treturn sorted(set(reduce(list.__add__, ([i, n // i] for i in range(1, int(n ** 0.5) + 1) if n % i == 0))))\n\ndef inv_mod(n):\n\treturn pow(n, mod - 2, mod)\n\ndef li():\n\treturn [int(i) for i in input().rstrip('\\n').split()]\n\ndef st():\n\treturn input().rstrip('\\n')\n\ndef val():\n\treturn int(input().rstrip('\\n'))\n\ndef li2():\n\treturn [i for i in input().rstrip('\\n')]\n\ndef li3():\n\treturn [int(i) for i in input().rstrip('\\n')]\nfor _ in range(val()):\n\t(n, k) = li()\n\td = defaultdict(set)\n\tfor i in range(n - 1):\n\t\t(a, b) = li()\n\t\td[a].add(b)\n\t\td[b].add(a)\n\tthistime = 1\n\the = deque()\n\tvisited = {}\n\tfor i in d:\n\t\tif len(d[i]) == 1:\n\t\t\tvisited[i] = 1\n\t\t\the.append(i)\n\tans = 0\n\tcounts = defaultdict(int)\n\twhile he:\n\t\ti = he.popleft()\n\t\tfor j in list(d[i]):\n\t\t\tcounts[j] += 1\n\t\t\td[i].remove(j)\n\t\t\td[j].remove(i)\n\t\t\tif counts[j] == k:\n\t\t\t\tthistime = 1\n\t\t\t\tans += 1\n\t\t\t\tcounts[j] = 0\n\t\t\t\tif len(d[j]) == 1:\n\t\t\t\t\tif j not in visited:\n\t\t\t\t\t\the.append(j)\n\t\t\t\t\tvisited[j] = 1\n\tprint(ans)\n", "for i in range(int(input())):\n\t(n, k) = list(map(int, input().split()))\n\ta = [[] for i in range(n)]\n\tb = [0] * n\n\tc = [0] * n\n\td = [0] * n\n\te = []\n\tfor i in range(n - 1):\n\t\t(u, v) = list(map(int, input().split()))\n\t\ta[u - 1].append(v)\n\t\ta[v - 1].append(u)\n\t\tb[u - 1] += 1\n\t\tb[v - 1] += 1\n\tif k == 1:\n\t\tprint(n - 1)\n\telse:\n\t\tfor i in range(n):\n\t\t\tif b[i] == 1:\n\t\t\t\td[i] = 1\n\t\t\t\tfor j in a[i]:\n\t\t\t\t\tc[j - 1] += 1\n\t\tz = 0\n\t\tf = 0\n\t\tfor i in range(n):\n\t\t\tif c[i] >= k:\n\t\t\t\te.append(i + 1)\n\t\t\t\tf += 1\n\t\ti = 0\n\t\twhile i < f:\n\t\t\tz += c[e[i] - 1] // k\n\t\t\ty = c[e[i] - 1] // k * k\n\t\t\tfor j in a[e[i] - 1]:\n\t\t\t\tif b[j - 1] == 1:\n\t\t\t\t\tif y == 0:\n\t\t\t\t\t\tbreak\n\t\t\t\t\ty -= 1\n\t\t\t\t\td[j - 1] = 2\n\t\t\t\t\tc[e[i] - 1] -= 1\n\t\t\t\t\tb[e[i] - 1] -= 1\n\t\t\tif b[e[i] - 1] == 1:\n\t\t\t\td[e[i] - 1] = 1\n\t\t\t\tfor j in a[e[i] - 1]:\n\t\t\t\t\tif d[j - 1] != 2:\n\t\t\t\t\t\tc[j - 1] += 1\n\t\t\t\t\t\tif c[j - 1] == k:\n\t\t\t\t\t\t\te.append(j)\n\t\t\t\t\t\t\tf += 1\n\t\t\ti += 1\n\t\tprint(z)\n", "from sys import stdin\ninput = lambda : stdin.readline().strip()\nfrom math import ceil, sqrt, factorial, gcd, log\nfrom collections import deque\nfrom bisect import bisect_left, bisect_right\nfor _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tz = [0 for i in range(n + 1)]\n\tgraph = {i: set() for i in range(1, n + 1)}\n\tfor i in range(n - 1):\n\t\t(a, b) = map(int, input().split())\n\t\tgraph[a].add(b)\n\t\tgraph[b].add(a)\n\tcount = 0\n\tif k == 1:\n\t\tcount = n - 1\n\telse:\n\t\tfreind = [set() for i in range(n + 1)]\n\t\tleaf = [False] * (n + 1)\n\t\tfor i in graph:\n\t\t\tif len(graph[i]) == 1:\n\t\t\t\tleaf[i] = True\n\t\t\t\tfor j in graph[i]:\n\t\t\t\t\tz[j] += 1\n\t\t\t\t\tbreak\n\t\tstack = []\n\t\tfor i in range(1, n + 1):\n\t\t\tif z[i] >= k:\n\t\t\t\tstack.append(i)\n\t\t\tfor j in graph[i]:\n\t\t\t\tif not leaf[j]:\n\t\t\t\t\tfreind[i].add(j)\n\t\twhile stack:\n\t\t\tx = stack.pop()\n\t\t\tcount += z[x] // k\n\t\t\tz[x] = z[x] % k\n\t\t\tif z[x] == 0 and len(freind[x]) == 1:\n\t\t\t\ta = freind[x].pop()\n\t\t\t\tfreind[a].remove(x)\n\t\t\t\tz[a] += 1\n\t\t\t\tif z[a] >= k:\n\t\t\t\t\tstack.append(a)\n\tprint(count)\n", "from sys import stdin\n\ndef inp():\n\treturn stdin.buffer.readline().rstrip().decode('utf8')\n\ndef itg():\n\treturn int(stdin.buffer.readline())\n\ndef mpint():\n\treturn map(int, stdin.buffer.readline().split())\n\nclass SegmentTreeIndex:\n\n\tdef __init__(self, data, default=0, func=max):\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.real_data = data\n\t\tself.data = [-1] * (2 * _size)\n\t\tself.data[_size:_size + self._len] = range(self._len)\n\t\tfor i in reversed(range(_size)):\n\t\t\tself.data[i] = self._index_cmp(self.data[i * 2], self.data[i * 2 + 1])\n\n\tdef _index_cmp(self, idx1, idx2):\n\t\tif idx2 == -1:\n\t\t\treturn idx1\n\t\tif idx1 == -1:\n\t\t\treturn idx2\n\t\tif self._func(self[idx1], self[idx2]) == self[idx1]:\n\t\t\treturn idx1\n\t\treturn idx2\n\n\tdef query(self, start, stop):\n\t\tstart += self._size\n\t\tstop += self._size\n\t\tres_left = res_right = -1\n\t\twhile start < stop:\n\t\t\tif start & 1:\n\t\t\t\tres_left = self._index_cmp(res_left, 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_right = self._index_cmp(self.data[stop], res_right)\n\t\t\tstart >>= 1\n\t\t\tstop >>= 1\n\t\treturn self._index_cmp(res_left, res_right)\n\n\tdef __delitem__(self, idx):\n\t\tself[idx] = self._default\n\n\tdef __getitem__(self, idx):\n\t\treturn self.real_data[idx]\n\n\tdef __setitem__(self, idx, value):\n\t\tself.real_data[idx] = value\n\t\tidx = idx + self._size >> 1\n\t\twhile idx:\n\t\t\tself.data[idx] = self._index_cmp(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 __repr__(self):\n\t\treturn 'SegmentTreeIndex({0})'.format(self.real_data)\nfrom copy import deepcopy\nfor case in range(1, itg() + 1):\n\t(n, k) = mpint()\n\tgraph = [set() for _ in range(n)]\n\tfor _ in range(n - 1):\n\t\t(u, v) = mpint()\n\t\tu -= 1\n\t\tv -= 1\n\t\tgraph[u].add(v)\n\t\tgraph[v].add(u)\n\tif k == 1:\n\t\tprint(n - 1)\n\t\tcontinue\n\tnew_graph = deepcopy(graph)\n\ttree = SegmentTreeIndex([0] * n)\n\tfor i in range(n):\n\t\tif len(graph[i]) == 1:\n\t\t\tancestor = next(iter(graph[i]))\n\t\t\ttree[ancestor] = tree[ancestor] + 1\n\t\t\tnew_graph[ancestor].remove(i)\n\tans = 0\n\twhile True:\n\t\tidx = tree.query(0, n)\n\t\tif tree[idx] < k:\n\t\t\tbreak\n\t\tans += 1\n\t\ttree[idx] = tree[idx] - k\n\t\tif tree[idx] == 0:\n\t\t\tif len(new_graph[idx]) == 1:\n\t\t\t\tancestor = new_graph[idx].pop()\n\t\t\t\tnew_graph[ancestor].remove(idx)\n\t\t\t\ttree[ancestor] = tree[ancestor] + 1\n\t\t\telif len(new_graph[idx]) >= 2:\n\t\t\t\tpass\n\tprint(ans)\n", "from collections import deque, defaultdict\nit = lambda : list(map(int, input().strip().split()))\n\ndef solve():\n\t(n, k) = it()\n\tedges = defaultdict(set)\n\tvis = set()\n\tqueue = deque()\n\tcount = [[] for _ in range(n + 1)]\n\tfor _ in range(n - 1):\n\t\t(x, y) = it()\n\t\tedges[x].add(y)\n\t\tedges[y].add(x)\n\tif k == 1:\n\t\treturn n - 1\n\tfor x in range(1, n + 1):\n\t\tif len(edges[x]) == 1:\n\t\t\tvis.add(x)\n\t\t\tqueue.append(x)\n\tans = 0\n\twhile queue:\n\t\tx = queue.popleft()\n\t\tif edges[x]:\n\t\t\tfor y in edges[x]:\n\t\t\t\tcount[y].append(x)\n\t\t\t\tif len(count[y]) == k:\n\t\t\t\t\tans += 1\n\t\t\t\t\twhile count[y]:\n\t\t\t\t\t\tedges[y].discard(count[y].pop())\n\t\t\t\tif len(edges[y]) == 1 and (not y in vis):\n\t\t\t\t\tvis.add(y)\n\t\t\t\t\tqueue.append(y)\n\treturn ans\nT = int(input())\nans = []\nfor _ in range(T):\n\tans.append(solve())\nfor a in ans:\n\tprint(a)\n", "import os\nimport sys\nfrom io import BytesIO, IOBase\n\nclass HeapNode:\n\n\tdef __init__(self, key, count):\n\t\tself.key = key\n\t\tself.count = count\n\ndef heapKey(a, b):\n\treturn a.count > b.count\nsetattr(HeapNode, '__lt__', lambda self, other: heapKey(self, other))\n\nclass Heap:\n\n\tdef __init__(self):\n\t\tself.heap = list()\n\t\tself.mapping = dict()\n\n\tdef pop(self):\n\t\tif len(self.heap) == 0:\n\t\t\treturn None\n\t\tlastelt = self.heap.pop()\n\t\tif self.heap:\n\t\t\treturnitem = self.heap[0]\n\t\t\tself.heap[0] = lastelt\n\t\t\tself.mapping[lastelt.key] = 0\n\t\t\tself._siftup(0)\n\t\t\tself.mapping.pop(returnitem.key)\n\t\t\treturn returnitem\n\t\tself.mapping.pop(lastelt.key)\n\t\treturn lastelt\n\n\tdef _siftup(self, pos):\n\t\tendpos = len(self.heap)\n\t\tstartpos = pos\n\t\tnewitem = self.heap[pos]\n\t\tchildpos = 2 * pos + 1\n\t\twhile childpos < endpos:\n\t\t\trightpos = childpos + 1\n\t\t\tif rightpos < endpos and (not self.heap[childpos] < self.heap[rightpos]):\n\t\t\t\tchildpos = rightpos\n\t\t\tself.heap[pos] = self.heap[childpos]\n\t\t\tself.mapping[self.heap[pos].key] = pos\n\t\t\tpos = childpos\n\t\t\tchildpos = 2 * pos + 1\n\t\tself.heap[pos] = newitem\n\t\tself.mapping[self.heap[pos].key] = pos\n\t\tself._siftdown(startpos, pos)\n\n\tdef _siftdown(self, startpos, pos):\n\t\tnewitem = self.heap[pos]\n\t\twhile pos > startpos:\n\t\t\tparentpos = pos - 1 >> 1\n\t\t\tparent = self.heap[parentpos]\n\t\t\tif newitem < parent:\n\t\t\t\tself.heap[pos] = parent\n\t\t\t\tself.mapping[parent.key] = pos\n\t\t\t\tpos = parentpos\n\t\t\t\tcontinue\n\t\t\tbreak\n\t\tself.heap[pos] = newitem\n\t\tself.mapping[newitem.key] = pos\n\n\tdef push(self, item):\n\t\tself.heap.append(item)\n\t\tself.mapping[item.key] = len(self.heap) - 1\n\t\tself._siftdown(0, len(self.heap) - 1)\n\n\tdef remove(self, key):\n\t\tpos = self.mapping[key]\n\t\tself.heap[pos].count = -1\n\t\tself._siftup(pos)\n\n\tdef increment(self, key):\n\t\tpos = self.mapping[key]\n\t\tself.heap[pos].count += 1\n\t\tself._siftdown(0, pos)\n\ndef main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\t(n, k) = map(int, input().split())\n\t\tG = dict()\n\t\tfor _ in range(n - 1):\n\t\t\t(u, v) = map(int, input().split())\n\t\t\tif u not in G:\n\t\t\t\tG.setdefault(u, set())\n\t\t\tif v not in G:\n\t\t\t\tG.setdefault(v, set())\n\t\t\tG[u].add(v)\n\t\t\tG[v].add(u)\n\t\theap = Heap()\n\t\tfor i in range(1, n + 1):\n\t\t\tcount = 0\n\t\t\tfor v in G[i]:\n\t\t\t\tif len(G[v]) == 1:\n\t\t\t\t\tcount += 1\n\t\t\theap.push(HeapNode(i, count))\n\t\tans = 0\n\t\twhile heap.heap[0].count >= k:\n\t\t\tpopped = heap.pop()\n\t\t\tnode = popped.key\n\t\t\tinitCount = popped.count\n\t\t\tleaves = list()\n\t\t\tleafCount = 0\n\t\t\tfor v in G[node]:\n\t\t\t\tif len(G[v]) == 1:\n\t\t\t\t\tleafCount += 1\n\t\t\tsize = leafCount // k * k\n\t\t\tfor v in G[node]:\n\t\t\t\tif len(leaves) >= size:\n\t\t\t\t\tbreak\n\t\t\t\tif len(G[v]) == 1:\n\t\t\t\t\tleaves.append(v)\n\t\t\tfor v in leaves:\n\t\t\t\theap.remove(v)\n\t\t\t\tG[node].discard(v)\n\t\t\t\tG.pop(v)\n\t\t\tif len(G[node]) == 1:\n\t\t\t\tfor v in G[node]:\n\t\t\t\t\theap.increment(v)\n\t\t\theap.push(HeapNode(node, initCount - size))\n\t\t\tans += leafCount // k\n\t\tprint(ans)\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 = lambda s: self.buffer.write(s.encode()) if self.writable else None\n\n\tdef read(self):\n\t\tif self.buffer.tell():\n\t\t\treturn self.buffer.read().decode('ascii')\n\t\treturn os.read(self._fd, os.fstat(self._fd).st_size).decode('ascii')\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().decode('ascii')\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\ndef print(*args, sep=' ', end='\\n', file=sys.stdout, flush=False):\n\tat_start = True\n\tfor x in args:\n\t\tif not at_start:\n\t\t\tfile.write(sep)\n\t\tfile.write(str(x))\n\t\tat_start = False\n\tfile.write(end)\n\tif flush:\n\t\tfile.flush()\n(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nsys.setrecursionlimit(10000)\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().rstrip('\\r\\n')\n\ndef RL():\n\treturn map(int, sys.stdin.readline().rstrip().split())\n\ndef RLL():\n\treturn list(map(int, sys.stdin.readline().rstrip().split()))\n\ndef N():\n\treturn int(input())\n\ndef comb(n, m):\n\treturn factorial(n) / (factorial(m) * factorial(n - m)) if n >= m else 0\n\ndef perm(n, m):\n\treturn factorial(n) // factorial(n - m) if n >= m else 0\n\ndef mdis(x1, y1, x2, y2):\n\treturn abs(x1 - x2) + abs(y1 - y2)\nmod = 998244353\nINF = float('inf')\nfrom math import factorial\nfrom collections import Counter, defaultdict, deque\nfrom heapq import heapify, heappop, heappush\n\ndef main():\n\tfor _ in range(N()):\n\t\t(n, k) = RL()\n\t\tgp = [[] for _ in range(n + 1)]\n\t\tind = [0] * (n + 1)\n\t\tfor _ in range(n - 1):\n\t\t\t(a, b) = RL()\n\t\t\tgp[a].append(b)\n\t\t\tgp[b].append(a)\n\t\t\tind[a] += 1\n\t\t\tind[b] += 1\n\t\tif k == 1:\n\t\t\tprint(n - 1)\n\t\t\tcontinue\n\t\tq = []\n\t\tvis = [0] * (n + 1)\n\t\tfor i in range(1, n + 1):\n\t\t\tif ind[i] == 1:\n\t\t\t\tq.append(i)\n\t\t\t\tvis[i] = 1\n\t\tnum = [0] * (n + 1)\n\t\tres = 0\n\t\twhile q:\n\t\t\tnd = q.pop()\n\t\t\tind[nd] -= 1\n\t\t\tfor nex in gp[nd]:\n\t\t\t\tif vis[nex] == 1:\n\t\t\t\t\tcontinue\n\t\t\t\tind[nex] -= 1\n\t\t\t\tnum[nex] += 1\n\t\t\t\tif num[nex] % k == 0:\n\t\t\t\t\tres += 1\n\t\t\t\t\tif ind[nex] == 1:\n\t\t\t\t\t\tq.append(nex)\n\t\t\t\t\t\tvis[nex] = 1\n\t\tprint(res)\nmain()\n", "from collections import deque\nfor t in range(int(input())):\n\t(n, k) = map(int, input().split())\n\ttree = [[] for i in range(n)]\n\tfor i in range(n - 1):\n\t\t(x, y) = map(int, input().split())\n\t\ttree[x - 1].append(y - 1)\n\t\ttree[y - 1].append(x - 1)\n\tnumLeaves = [0 for i in range(n)]\n\tisLeaf = [False for i in range(n)]\n\tfor i in range(n):\n\t\tif len(tree[i]) == 1:\n\t\t\tnumLeaves[tree[i][0]] += 1\n\t\t\tisLeaf[i] = True\n\tif k == 1:\n\t\tprint(n - 1)\n\t\tcontinue\n\tq = []\n\tfor i in range(n):\n\t\tif numLeaves[i] >= k:\n\t\t\tq.append(i)\n\tq = deque(q)\n\tans = 0\n\twhile len(q) > 0:\n\t\tcurr = q.popleft()\n\t\tans += numLeaves[curr] // k\n\t\tif numLeaves[curr] % k == 0:\n\t\t\tnumLeaves[curr] = 0\n\t\t\tcnt = 0\n\t\t\tnonLeafNeib = -1\n\t\t\tfor neib in tree[curr]:\n\t\t\t\tif not isLeaf[neib]:\n\t\t\t\t\tcnt += 1\n\t\t\t\t\tnonLeafNeib = neib\n\t\t\t\t\tif cnt == 2:\n\t\t\t\t\t\tbreak\n\t\t\tif cnt == 1:\n\t\t\t\tisLeaf[curr] = True\n\t\t\t\tnumLeaves[nonLeafNeib] += 1\n\t\t\t\tif numLeaves[nonLeafNeib] == k:\n\t\t\t\t\tq.append(nonLeafNeib)\n\t\telse:\n\t\t\tnumLeaves[curr] = numLeaves[curr] % k\n\tprint(ans)\n", "import sys\ninput = sys.stdin.readline\n\ndef read_list():\n\treturn map(int, input().split())\n\ndef print_list(l):\n\tprint(' '.join(map(str, l)))\nfrom collections import defaultdict\nN = int(input())\nfor _ in range(N):\n\t(n, k) = read_list()\n\tif k == 1:\n\t\tfor _ in range(n - 1):\n\t\t\tinput()\n\t\tprint(n - 1)\n\telse:\n\t\tdic = defaultdict(int)\n\t\tde = defaultdict(set)\n\t\tfor _ in range(n - 1):\n\t\t\t(a, b) = read_list()\n\t\t\tde[a].add(b)\n\t\t\tde[b].add(a)\n\t\tfor i in range(1, n + 1):\n\t\t\tdic[i] = len(de[i])\n\t\tdd = defaultdict(int)\n\t\tfor v in range(1, n + 1):\n\t\t\tif dic[v] >= k:\n\t\t\t\tfor u in de[v]:\n\t\t\t\t\tif dic[u] == 1:\n\t\t\t\t\t\tdd[v] += 1\n\t\ts = set((i for i in range(1, n + 1) if dd[i] >= k))\n\t\tres = 0\n\t\twhile s:\n\t\t\tv = s.pop()\n\t\t\twhile dd[v] >= k:\n\t\t\t\tres += 1\n\t\t\t\tdic[v] -= k\n\t\t\t\tdd[v] -= k\n\t\t\t\tif dic[v] == 1:\n\t\t\t\t\tfor t in de[v]:\n\t\t\t\t\t\tif dic[t] >= k:\n\t\t\t\t\t\t\tdd[t] += 1\n\t\t\t\t\t\t\tif dd[t] >= k:\n\t\t\t\t\t\t\t\ts.add(t)\n\t\tprint(res)\n", "import sys\nimport math\nfrom _collections import deque\ninput = sys.stdin.readline\nI = lambda : list(map(int, input().split()))\nma = int(10000000000000000)\nmod = 1000000007\ntc = int(input())\nfor p in range(tc):\n\t(n, k) = map(int, input().split())\n\tadj = [[] for i in range(n + 2)]\n\tdeg = [0] * (n + 2)\n\tb = [0] * (n + 2)\n\tfor i in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tdeg[u] += 1\n\t\tdeg[v] += 1\n\t\tadj[u].append(v)\n\t\tadj[v].append(u)\n\tif k == 1:\n\t\tprint(n - 1)\n\t\tcontinue\n\tfor i in range(1, n + 1):\n\t\tif deg[i] == 1:\n\t\t\tx = adj[i][0]\n\t\t\tb[x] += 1\n\tq = []\n\tfor i in range(1, n + 1):\n\t\tif b[i] >= k:\n\t\t\tq.append(i)\n\tans = int(0)\n\twhile len(q) > 0:\n\t\tu = int(q[0])\n\t\tq.pop(0)\n\t\tcn = int(b[u] / k)\n\t\tans += cn\n\t\tdeg[u] = deg[u] - cn * k\n\t\tb[u] %= k\n\t\tif deg[u] == 1:\n\t\t\tpar = int(-1)\n\t\t\tfor j in adj[u]:\n\t\t\t\tif deg[j] > 1:\n\t\t\t\t\tpar = j\n\t\t\tif par == -1:\n\t\t\t\tcontinue\n\t\t\tb[par] += 1\n\t\t\tif b[par] == k:\n\t\t\t\tq.append(par)\n\tprint(ans)\n", "from sys import stdin\ninput = stdin.readline\n\ndef solve():\n\t(n, k) = map(int, input().split())\n\tadj = [[] for _ in range(n)]\n\tfrd = [set() for _ in range(n)]\n\tcnt = [0] * n\n\tis_leaf = [False] * n\n\tfor _ in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tu -= 1\n\t\tv -= 1\n\t\tadj[u].append(v)\n\t\tadj[v].append(u)\n\tif k == 1:\n\t\tprint(n - 1)\n\t\treturn\n\tfor i in range(n):\n\t\tif len(adj[i]) == 1:\n\t\t\tis_leaf[i] = True\n\t\t\tcnt[adj[i][0]] += 1\n\tq = []\n\tfor u in range(n):\n\t\tif cnt[u] >= k:\n\t\t\tq.append(u)\n\t\tfor v in adj[u]:\n\t\t\tif not is_leaf[v]:\n\t\t\t\tfrd[u].add(v)\n\tans = 0\n\twhile len(q) > 0:\n\t\tu = q.pop()\n\t\tans += cnt[u] // k\n\t\tcnt[u] %= k\n\t\tif cnt[u] == 0 and len(frd[u]) == 1:\n\t\t\tp = frd[u].pop()\n\t\t\tfrd[p].remove(u)\n\t\t\tcnt[p] += 1\n\t\t\tif cnt[p] >= k:\n\t\t\t\tq.append(p)\n\tprint(ans)\n\ndef main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\tsolve()\nmain()\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\t(n, k) = map(int, input().split())\n\tedge = [[] for i in range(n)]\n\tfor i in range(n - 1):\n\t\t(x, y) = map(int, input().split())\n\t\tedge[x - 1].append(y - 1)\n\t\tedge[y - 1].append(x - 1)\n\tleaf = [[] for i in range(n)]\n\tfor i in range(n):\n\t\tif len(edge[i]) == 1:\n\t\t\tleaf[edge[i][0]].append(i)\n\tque = [i for i in range(n) if len(leaf[i]) >= k]\n\tdeg = [len(edge[i]) for i in range(n)]\n\tdelete = set([])\n\tans = 0\n\twhile que:\n\t\tv = que.pop()\n\t\tif v in delete:\n\t\t\tcontinue\n\t\tq = len(leaf[v]) // k\n\t\tcount = q * k\n\t\tans += q\n\t\twhile count:\n\t\t\tdv = leaf[v].pop()\n\t\t\tdelete.add(dv)\n\t\t\tcount -= 1\n\t\tdeg[v] -= q * k\n\t\tif deg[v] == 1:\n\t\t\tfor nv in edge[v]:\n\t\t\t\tif nv not in delete:\n\t\t\t\t\tleaf[nv].append(v)\n\t\t\t\t\tif len(leaf[nv]) == k:\n\t\t\t\t\t\tque.append(nv)\n\t\t\t\t\tbreak\n\tprint(ans)\n", "import sys\nsys.setrecursionlimit(10 ** 5)\nint1 = lambda x: int(x) - 1\np2D = lambda x: print(*x, sep='\\n')\n\ndef II():\n\treturn int(sys.stdin.readline())\n\ndef MI():\n\treturn map(int, sys.stdin.readline().split())\n\ndef MI1():\n\treturn map(int1, sys.stdin.readline().split())\n\ndef LI():\n\treturn list(map(int, sys.stdin.readline().split()))\n\ndef LLI(rows_number):\n\treturn [LI() for _ in range(rows_number)]\n\ndef SI():\n\treturn sys.stdin.readline()[:-1]\nfor _ in range(II()):\n\t(n, k) = MI()\n\tto = [[] for _ in range(n)]\n\tfor _ in range(n - 1):\n\t\t(u, v) = MI1()\n\t\tto[u].append(v)\n\t\tto[v].append(u)\n\tif k == 1:\n\t\tprint(n - 1)\n\t\tcontinue\n\tdp = [0] * n\n\tbeleaf = [False] * n\n\tleaves = [0] * n\n\tstack = [(0, -1)]\n\tfirst = [True] * n\n\twhile stack:\n\t\t(u, pu) = stack.pop()\n\t\tif first[u]:\n\t\t\tfirst[u] = False\n\t\t\tstack.append((u, pu))\n\t\t\tfor v in to[u]:\n\t\t\t\tif v == pu:\n\t\t\t\t\tcontinue\n\t\t\t\tstack.append((v, u))\n\t\telse:\n\t\t\tdp[u] = leaves[u] // k\n\t\t\tif pu != -1 and dp[u] * k + 1 == len(to[u]):\n\t\t\t\tleaves[pu] += 1\n\t\t\t\tbeleaf[u] = True\n\t\t\tfor v in to[u]:\n\t\t\t\tif v == pu:\n\t\t\t\t\tcontinue\n\t\t\t\tdp[u] += dp[v]\n\tstack = [(0, -1)]\n\twhile stack:\n\t\t(u, pu) = stack.pop()\n\t\tfor v in to[u]:\n\t\t\tif v == pu:\n\t\t\t\tcontinue\n\t\t\tdp[v] = dp[u]\n\t\t\tif (leaves[u] - beleaf[v]) % k == 0 and leaves[u] - beleaf[v] + 1 == len(to[u]):\n\t\t\t\tleaves[v] += 1\n\t\t\t\tif leaves[v] % k == 0:\n\t\t\t\t\tdp[v] += 1\n\t\t\tstack.append((v, u))\n\tprint(max(dp))\n", "import io\nimport os\nfrom collections import Counter, defaultdict, deque\n\ndef solve(N, K, edges):\n\tif K == 1:\n\t\treturn len(edges)\n\tgraph = [[] for i in range(N)]\n\tfor (u, v) in edges:\n\t\tgraph[u].append(v)\n\t\tgraph[v].append(u)\n\tq = set()\n\tleaves = set()\n\tfor u in range(N):\n\t\tif len(graph[u]) == 1:\n\t\t\t(v,) = graph[u]\n\t\t\tq.add(v)\n\t\t\tleaves.add(u)\n\tremoved = set()\n\tq = deque(q)\n\twhile q:\n\t\tparent = q.popleft()\n\t\tif parent in removed or parent in leaves:\n\t\t\tcontinue\n\t\tchildren = [v for v in graph[parent] if v in leaves and v not in removed]\n\t\tfor i in range(len(children) // K * K):\n\t\t\tremoved.add(children[i])\n\t\tif len(children) % K == 0:\n\t\t\tnbrs = [v for v in graph[parent] if v not in removed]\n\t\t\tif len(nbrs) == 1:\n\t\t\t\tleaves.add(parent)\n\t\t\t\tq.append(nbrs[0])\n\treturn len(removed) // K\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nT = int(input())\nfor t in range(T):\n\t(N, K) = [int(x) for x in input().split()]\n\tedges = [[int(x) - 1 for x in input().split()] for i in range(N - 1)]\n\tans = solve(N, K, edges)\n\tprint(ans)\n", "from sys import stdin, stdout\nfrom collections import deque\nt = int(stdin.readline())\nfor x in range(t):\n\t(n, k) = map(int, stdin.readline().split())\n\tdic = {}\n\tfor i in range(n - 1):\n\t\t(x, y) = map(int, stdin.readline().split())\n\t\tx -= 1\n\t\ty -= 1\n\t\tif x not in dic:\n\t\t\tdic[x] = set()\n\t\tif y not in dic:\n\t\t\tdic[y] = set()\n\t\tdic[x].add(y)\n\t\tdic[y].add(x)\n\tif k == 1:\n\t\tprint(n - 1)\n\t\tcontinue\n\tisleaf = set()\n\tleaves = [0 for _ in range(n)]\n\tfor i in range(n):\n\t\tif len(dic[i]) == 1:\n\t\t\tisleaf.add(i)\n\t\t\tp = next(iter(dic[i]))\n\t\t\tleaves[p] += 1\n\tq = deque()\n\tfrd = [set() for _ in range(n)]\n\tfor l in range(n):\n\t\tif leaves[l] >= k:\n\t\t\tq.append(l)\n\t\tfor v in dic[l]:\n\t\t\tif v not in isleaf:\n\t\t\t\tfrd[l].add(v)\n\tans = 0\n\twhile len(q) > 0:\n\t\tu = q.popleft()\n\t\tans += leaves[u] // k\n\t\tleaves[u] %= k\n\t\tif leaves[u] == 0 and len(frd[u]) == 1:\n\t\t\tp = frd[u].pop()\n\t\t\tfrd[p].remove(u)\n\t\t\tleaves[p] += 1\n\t\t\tif leaves[p] >= k:\n\t\t\t\tq.append(p)\n\tprint(ans)\n"]

difficulty: HARD

source: codeforces

raw_problem:
F. Removing Leaves

time limit per test
2 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

You are given a tree (connected graph without cycles) consisting of $$$n$$$ vertices. The tree is unrooted — it is just a connected undirected graph without cycles.

In one move, you can choose exactly $$$k$$$ leaves (leaf is such a vertex that is connected to only one another vertex) connected to the same vertex and remove them with edges incident to them. I.e. you choose such leaves $$$u_1, u_2, \dots, u_k$$$ that there are edges $$$(u_1, v)$$$, $$$(u_2, v)$$$, $$$\dots$$$, $$$(u_k, v)$$$ and remove these leaves and these edges.

Your task is to find the maximum number of moves you can perform if you remove leaves optimally.

You have to answer $$$t$$$ independent test cases.

Input

The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.

The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k < n$$$) — the number of vertices in the tree and the number of leaves you remove in one move, respectively. The next $$$n-1$$$ lines describe edges. The $$$i$$$-th edge is represented as two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$), where $$$x_i$$$ and $$$y_i$$$ are vertices the $$$i$$$-th edge connects. It is guaranteed that the given set of edges forms a tree.

It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output

For each test case, print the answer — the maximum number of moves you can perform if you remove leaves optimally.

Example

Input

4
8 3
1 2
1 5
7 6
6 8
3 1
6 4
6 1
10 3
1 2
1 10
2 3
1 5
1 6
2 4
7 10
10 9
8 10
7 2
3 1
4 5
3 6
7 4
1 2
1 4
5 1
1 2
2 3
4 3
5 3

Output

2
3
3
4

Note

The picture corresponding to the first test case of the example:

There you can remove vertices $$$2$$$, $$$5$$$ and $$$3$$$ during the first move and vertices $$$1$$$, $$$7$$$ and $$$4$$$ during the second move.

The picture corresponding to the second test case of the example:

There you can remove vertices $$$7$$$, $$$8$$$ and $$$9$$$ during the first move, then vertices $$$5$$$, $$$6$$$ and $$$10$$$ during the second move and vertices $$$1$$$, $$$3$$$ and $$$4$$$ during the third move.

The picture corresponding to the third test case of the example:

There you can remove vertices $$$5$$$ and $$$7$$$ during the first move, then vertices $$$2$$$ and $$$4$$$ during the second move and vertices $$$1$$$ and $$$6$$$ during the third move.

question:
You are given a tree (connected graph without cycles) consisting of $$$n$$$ vertices. The tree is unrooted — it is just a connected undirected graph without cycles.
In one move, you can choose exactly $$$k$$$ leaves (leaf is such a vertex that is connected to only one another vertex) connected to the same vertex and remove them with edges incident to them. I.e. you choose such leaves $$$u_1, u_2, \dots, u_k$$$ that there are edges $$$(u_1, v)$$$, $$$(u_2, v)$$$, $$$\dots$$$, $$$(u_k, v)$$$ and remove these leaves and these edges.
Your task is to find the maximum number of moves you can perform if you remove leaves optimally.
You have to answer $$$t$$$ independent test cases.

Input
The first line of the input contains one integer $$$t$$$ ($$$1 \le t \le 2 \cdot 10^4$$$) — the number of test cases. Then $$$t$$$ test cases follow.
The first line of the test case contains two integers $$$n$$$ and $$$k$$$ ($$$2 \le n \le 2 \cdot 10^5$$$; $$$1 \le k < n$$$) — the number of vertices in the tree and the number of leaves you remove in one move, respectively. The next $$$n-1$$$ lines describe edges. The $$$i$$$-th edge is represented as two integers $$$x_i$$$ and $$$y_i$$$ ($$$1 \le x_i, y_i \le n$$$), where $$$x_i$$$ and $$$y_i$$$ are vertices the $$$i$$$-th edge connects. It is guaranteed that the given set of edges forms a tree.
It is guaranteed that the sum of $$$n$$$ does not exceed $$$2 \cdot 10^5$$$ ($$$\sum n \le 2 \cdot 10^5$$$).

Output
For each test case, print the answer — the maximum number of moves you can perform if you remove leaves optimally.

Example
Input
4
8 3
1 2
1 5
7 6
6 8
3 1
6 4
6 1
10 3
1 2
1 10
2 3
1 5
1 6
2 4
7 10
10 9
8 10
7 2
3 1
4 5
3 6
7 4
1 2
1 4
5 1
1 2
2 3
4 3
5 3

Output
2
3
3
4

Note
The picture corresponding to the first test case of the example:
![image](1.png)
There you can remove vertices $$$2$$$, $$$5$$$ and $$$3$$$ during the first move and vertices $$$1$$$, $$$7$$$ and $$$4$$$ during the second move.
The picture corresponding to the second test case of the example:
![image](2.png)
There you can remove vertices $$$7$$$, $$$8$$$ and $$$9$$$ during the first move, then vertices $$$5$$$, $$$6$$$ and $$$10$$$ during the second move and vertices $$$1$$$, $$$3$$$ and $$$4$$$ during the third move.
The picture corresponding to the third test case of the example:
![image](3.png)
There you can remove vertices $$$5$$$ and $$$7$$$ during the first move, then vertices $$$2$$$ and $$$4$$$ during the second move and vertices $$$1$$$ and $$$6$$$ during the third move.

tags: ['Tree algorithms', 'Data structures', 'Implementation', 'Greedy algorithms']

skill_types: ['Data structures', 'Greedy algorithms']

raw_tags: ['trees', 'data structures', 'greedy', 'implementation']

image_tags: Tree Tree Tree

data_split: test


Perfect

source: Hokkaido University Programming Contest 2019, Aizu Competitive Programming Camp 2019

raw_problem:
B: テトリス

問題

縦 4 マス x 横 10 マスの長方形からなる盤面を考えます。
縦 1 マス x 横 1 マスぶんの正方形をブロックと呼びます。

ブロックを 4 つ繋げたものをテトロミノと呼び、以下の 7 種類（およびこれらに対して 90 度回転を任意回行ったもの）があります。

さて、盤面のうち 28 個のマスにブロックが置かれた状態を考えます。

左の図のように、各ブロック（赤色で表される）はマスに合うように置かれます。右の図のように半端な位置に置かれることはありません。

4 つのテトロミノ <var>t_1</var>, <var>t_2</var>, <var>t_3</var>, <var>t_4</var> が与えられるので、このうちちょうど 3 つを選んですきな位置に置くことで、盤面全体にブロックが置かれた状態にできるか判定してください。

ただし、テトロミノを配置するにあたり、以下の条件をすべて満たさなければなりません。

ブロック同士が重なってはいけない。

与えられたテトロミノを回転させてはいけない。

各 <var>i</var> (<var>1 \leq i \leq 4</var>) について、テトロミノ <var>t_i</var> を 2 回以上使ってはいけない。

テトロミノの各ブロックは盤面の外に出てはいけない。

盤面が <var>n</var> 個与えられるので、各盤面についてこの判定を行い、盤面全体にブロックを置けるならば Yes、不可能ならば No を出力してください。

入力形式

<var>t_1</var>
<var>t_2</var>
<var>t_3</var>
<var>t_4</var>
<var>n</var>
<var>B_1</var>
…
<var>B_n</var>

はじめに、使えるテトロミノ <var>t_1</var>, <var>t_2</var>, <var>t_3</var>, <var>t_4</var> が与えられます。
各 <var>t_i</var> (<var>1 \leq i \leq 4</var>) は以下の形式で与えられます。

<var>h</var> <var>w</var>
<var>s_1</var>
…
<var>s_h</var>

これはテトロミノを含む縦 <var>h</var> x 横 <var>w</var> マスの長方形であり、テトロミノの形状は <var>s_1 … s_h</var> で表されます。長方形のうち、テトロミノを表す部分は #、それ以外の部分は . で表されます。各長方形に # はちょうど 4 つ含まれます。. のみからなる行または列は存在しません。

次に、盤面の個数 <var>n</var> が与えられます。
その後、<var>4\times 10</var> マスで表される盤面 <var>B</var> が <var>n</var> 個与えられます。
ブロックがある位置が #、ない位置が . で示されます。

制約

<var>1\leq n\leq 10^5</var>

与えられる各テトロミノは上で述べた条件に違反しない

各盤面について、# はちょうど 28 個存在する

たとえば、以下のようなテトロミノは与えられない。

3 3
..#
.#.
##.

（連結でないブロックがあり、これは上で述べたテトロミノの条件を満たさない）

3 3
...
.#.
###

（一番上の行が . のみからなる）

出力形式

<var>n</var> 行にわたって出力してください。<var>i</var> 行目には盤面 <var>B_i</var> に対する判定結果を Yes または No で出力してください。

入力例1

2 3
##.
.##
2 3
#..
###
1 4
####
2 3
###
.#.
2
####....##
####...###
####..####
####...###
###..#####
###...####
###...####
###....###

出力例1

Yes
Yes

<var>t_1</var>, <var>t_2</var>, <var>t_3</var>, <var>t_4</var> に相当するテトロミノが置かれる場所をそれぞれ 1, 2, 3, 4 で示すと、各盤面は次のように敷き詰められます。

####3333##
####444###
####24####
####222###

###11#####
###211####
###222####
###3333###

各盤面について、別々のテトロミノを選んで構いません。

入力例2

1 4
####
1 4
####
2 2
##
##
2 2
##
##
4
######....
....######
#######..#
#######..#
....######
######....
....######
##########
######.#.#
######.#.#
##..##.#.#
##..##.#.#
##.###.#.#
#.#.###.##
#.#.###.##
##.###.#.#

出力例2

Yes
No
No
No

#### が足りないため、2 つ目の盤面をブロックで敷き詰めることはできません。

また、テトロミノを回転させることはできないので、3 つ目の盤面を敷き詰めることもできません。

また、4 つ目の盤面のようなブロックの配置の仕方もありえることに注意してください。すなわち、入力で与えられる盤面はテトロミノを組み合わせて作られる盤面とは限りません。

solutions: ["import sys\nfrom collections import defaultdict\nfrom copy import deepcopy\nsys.setrecursionlimit(10**6)\n\nD = defaultdict(int)\ndef dfs(F, jj, num):\n    if num == 3:\n        A = tuple([tuple(F[i]) for i in range(4)])\n        D[A] = 1\n        return\n    Fc = [[F[i][j] for j in range(10)] for i in range(4)]\n    h, w = L[jj]\n    TT = T[jj]\n    for i in range(4 - h + 1):\n        for j in range(10 - w + 1):\n            flag = True\n            for i_ in range(h):\n                for j_ in range(w):\n                    if TT[i_][j_] == '#':\n                        if Fc[i + i_][j + j_] == '#':\n                            flag = False\n                            break\n                        Fc[i + i_][j + j_] = '#'\n                if not flag:\n                    break\n            if flag:\n                nj = jj + 1\n                if nj == ii:\n                    nj += 1\n                dfs(Fc, nj, num + 1)\n            Fc = [[F[i][j] for j in range(10)] for i in range(4)]\n\nL = []\nT = []\nfor _ in range(4):\n    h, w = map(int, input().split())\n    TT = [list(input()) for _ in range(h)]\n    L.append((h, w))\n    T.append(TT)\nfor ii in range(4):\n    F = [['.' for _ in range(10)] for _ in range(4)]\n    if ii > 0:\n        j = 0\n    else:\n        j = 1\n    dfs(F, j, 0)\nn = int(input())\nfor _ in range(n):\n    F = [list(input()) for _ in range(4)]\n    for i in range(4):\n        for j in range(10):\n            F[i][j] = '#' if F[i][j] == '.' else '.'\n    F = tuple([tuple(F[i]) for i in range(4)])\n    if D[F]:\n        print(\"Yes\")\n    else:\n        print(\"No\")\n\n", "#!usr/bin/env python3\nfrom collections import defaultdict,deque\nfrom heapq import heappush, heappop\nimport sys\nimport math\nimport bisect\nimport random\ndef LI(): return [int(x) for x in sys.stdin.readline().split()]\ndef I(): return int(sys.stdin.readline())\ndef LS():return [list(x) for x in sys.stdin.readline().split()]\ndef S():\n    res = list(sys.stdin.readline())\n    if res[-1] == \"\\n\":\n        return res[:-1]\n    return res\ndef IR(n):\n    return [I() for i in range(n)]\ndef LIR(n):\n    return [LI() for i in range(n)]\ndef SR(n):\n    return [S() for i in range(n)]\ndef LSR(n):\n    return [LS() for i in range(n)]\n\nsys.setrecursionlimit(1000000)\nmod = 1000000007\n\n\ndef solve():\n    def dfs(t,j,num):\n        if num == 3:\n            tt = tuple([tuple(t[k]) for k in range(H)])\n            d[tt] = 1\n        else:\n            nt = [[t[y][x] for x in range(W)] for y in range(H)]\n            for y in range(H-len(s[j])+1):\n                for x in range(W-len(s[j][0])+1):\n                    f = 0\n                    for y_ in range(len(s[j])):\n                        for x_ in range(len(s[j][0])):\n                            if s[j][y_][x_]:\n                                Y,X = y+y_,x+x_\n                                if nt[Y][X]:\n                                    f = 1\n                                    break\n                                nt[Y][X] = 1\n                        if f:\n                            break\n                    if f:\n                        nt = [[t[y][x] for x in range(W)] for y in range(H)]\n                    else:\n                        nj = j+1\n                        if nj == i:\n                            nj += 1\n                        dfs(nt,nj,num+1)\n                        nt = [[t[y][x] for x in range(W)] for y in range(H)]\n\n    s = []\n    for i in range(4):\n        h,w = LI()\n        b = SR(h)\n        s.append([[1 if b[i][j] == \"#\" else 0 for j in range(w)] for i in range(h)])\n    H,W = 4,10\n    d = defaultdict(lambda : 0)\n    for i in range(4):\n        t = [[0]*W for i in range(H)]\n        j = 0 if i > 0 else 1\n        dfs(t,j,0)\n    n = I()\n    for i in range(n):\n        b = SR(H)\n        t = tuple([tuple([0 if b[i][j] == \"#\" else 1 for j in range(W)]) for i in range(H)])\n        if d[t]:\n            print(\"Yes\")\n        else:\n            print(\"No\")\n    return\n\n\nif __name__ == \"__main__\":\n    solve()\n\n"]

source: aizu

question:
B: Tetris
Problem

Consider a game board that consists of a rectangle with 4 vertical squares by 10 horizontal squares.
A block is called a square that covers 1 vertical square by 1 horizontal square.

A tetromino is an object made of 4 connected blocks, and there are the following 7 types (and any of these after being rotated by 90 degrees any number of times).

![image](1.png)
Now, consider a situation where 28 squares of the game board are occupied by blocks.

![image](2.png)
As shown in the left figure, each block (represented in red) is placed so that it fits in the squares. Blocks will not be placed in half positions as seen in the right figure.
Given 4 tetrominoes $t_1$, $t_2$, $t_3$, $t_4$, determine whether it is possible to choose exactly 3 of them and place them in any position to fully occupy the game board with blocks.
However, when placing the tetrominoes, all of the following conditions must be satisfied:

- Blocks must not overlap each other.
- The given tetrominoes must not be rotated.
- For each $i$ ($1 \leq i \leq 4$), the tetromino $t_i$ must not be used more than once.
- Each block of a tetromino must not extend outside of the game board.

As $n$ game boards are given, perform this determination for each board and output Yes if the entire board can be filled with blocks, otherwise No.
Input format

$t_1$

$t_2$

$t_3$

$t_4$

$n$

$B_1$
…

$B_n$

First, the usable tetrominoes $t_1$, $t_2$, $t_3$, $t_4$ are given.
Each $t_i$ ($1 \leq i \leq 4$) is given in the following format:

$h$ $w$

$s_1$
…

$s_h$

This is a rectangle consisting of $h$ vertical by $w$ horizontal squares that contains the tetromino, and the shape of the tetromino is expressed by $s_1 … s_h$. The parts representing the tetromino within the rectangle are indicated by #, and the rest by . There are exactly 4 #s in each rectangle, and there are no rows or columns that consist only of dots.

Next, the number of game boards $n$ is given.
After that, $n$ game boards $B$ represented by $4\times 10$ squares are given.
Positions with a block are indicated by #, and positions without by .

Constraints

- $1\leq n\leq 10^5$
- Each given tetromino does not violate the conditions mentioned above
- For each given game board, there are exactly 28 #s

For example, the following tetromino will not be given:

3 3
..#
.#.
##.

(There is a disconnected block, which does not meet the conditions for a tetromino mentioned above)

3 3
...
.#.
###

(The topmost row consists only of dots)
Output format

Please output over $n$ lines. For the $i$-th line, output the determination result for the game board $B_i$ as Yes or No.
Example of input 1

2 3
##.
.##
2 3
#..
###
1 4
####
2 3
###
.#.
2
####....##
####...###
####..####
####...###
###..#####
###...####
###...####
###....###

Example of output 1

Yes
Yes

If the locations of the tetrominoes corresponding to $t_1$, $t_2$, $t_3$, $t_4$ are indicated by 1, 2, 3, 4 respectively, each game board can be tiled as follows:

####3333##
####444###
####24####
####222###

###11#####
###211####
###222####
###3333###

For each game board, it is permissible to choose different tetrominoes separately.
Example of input 2

1 4
####
1 4
####
2 2
##
##
2 2
##
##
4
######....
....######
#######..#
#######..#
....######
######....
....######
##########
######.#.#
######.#.#
##..##.#.#
##..##.#.#
##.###.#.#
#.#.###.##
#.#.###.##
##.###.#.#

Example of output 2

Yes
No
No
No

Since #### is not enough, it is not possible to tile the second game board with blocks.
Also, as tetrominoes cannot be rotated, it is also not possible to tile the third game board.
Please note that block arrangements like the fourth game board can occur as well. This means that the presented game boards do not necessarily have to be made by combining tetrominoes.

image_tags: Patterns Patterns

data_split: test


Cube of Two

source: Osaka University Programming Contest 2013

raw_problem:
Cube of Two

Problem Statement

日本で販売されているルービックキューブの各面の配色が，
世界で標準的に採用されているものに合わせられたのはつい最近のことだ．

これに慣れるため，まずは簡単な2x2x2のキューブをスクランブルして遊ぼう．

初期状態のルービックキューブは，各色が1つの面に集まるように揃えられており，
上面に赤色，正面に黄色，右側面に青色が見える．

また，下面は橙色，背面は白色，左側面は緑色である．
展開図を用いると次のように表せる．

各面に対し，向かって時計回りに90°回転させる操作を，それぞれの頭文字をとってU,F,R,D,B,Lと表す．

ルービックキューブのスクランブルは，各文字が1つの回転操作に対応する文字列<var>S</var>として表される．

初期状態から入力に従ってスクランブルしたときの，ルービックキューブの各面の色を展開図として出力せよ．

Input

入力は以下の形式に従う．

<var>S</var>

Constraints

<var>1≦|S|≦100</var>（<var>|S|</var>は文字列の長さ）

<var>S</var>はU,F,R,D,B,Lのみを含む．

Output

初期状態のルービックキューブに対し，各回転操作を順に適用した後の各面の状態を展開図として出力せよ．

各面の色はr(赤),o(橙),y(黄),g(緑),b(青),w(白)の6種類の英小文字で表す．
また，空白部はピリオド(.)で表す．

Sample Input 1

R

Output for the Sample Input 1

..ry....
..ry....
ggyobbrw
ggyobbrw
..ow....
..ow....

右側面を時計回りに90°回転させると次のようになる．

Sample Input 2

UFRDBL

Output for the Sample Input 2

..go....
..yb....
rbrwrwby
wogoygwo
..yb....
..gr....

各回転操作に対する状態の遷移は次のようになる．

source: aizu

question:
Cube of Two
Problem Statement
It was only recently that the color arrangement of each face of Rubik's Cubes sold in Japan has been aligned with the standard used worldwide.
To get used to this, let's first scramble an easy 2x2x2 cube and have fun.
The initial state of the Rubik's Cube is arranged so that each color is gathered on one face,
with red on the top face, yellow on the front face, and blue visible on the right face.
Moreover, the bottom face is orange, the back face is white, and the left side face is green.
Using a net diagram, it can be represented as follows.
![image](1.png)
For each face, the operation of rotating 90° clockwise is represented by the initial letters U,F,R,D,B,L, respectively.
The scramble of the Rubik's Cube is represented as a string $S$ where each character corresponds to one rotation operation.
Output the net diagram of the colors of each face of the Rubik's Cube when scrambled from the initial state following the input.
Input
The input follows the following format.
$S$
Constraints
$1≦|S|≦100$ (where $|S|$ is the length of the string)
$S$ only contains U,F,R,D,B,L.
Output
Output the state of each face as a net diagram after applying each rotation operation in order to the initial state of the Rubik's Cube.
Each face color is represented by one of the six lowercase English letters r(red),o(orange),y(yellow),g(green),b(blue),w(white).
Additionally, blank parts are represented by a period (.).
Sample Input 1
R
Output for the Sample Input 1
..ry....
..ry....
ggyobbrw
ggyobbrw
..ow....
..ow....

Rotating the right side face 90° clockwise results in the following.
![image](2.png)
Sample Input 2
UFRDBL
Output for the Sample Input 2
..go....
..yb....
rbrwrwby
wogoygwo
..yb....
..gr....

The state transitions for each rotation operation are as follows.
![image](3.png)

image_tags:
3D Geometry
3D Geometry
3D Geometry

data_split: test


Estimating the Flood Risk

source: ACM International Collegiate Programming Contest, Asia Regional 2019, Japan

raw_problem:
Estimating the Flood Risk

  Mr. Boat is the owner of a vast extent of land. As many typhoons have struck Japan this year, he became concerned of flood risk of his estate and he wants to know the average altitude of his land. The land is too vast to measure the altitude at many spots. As no steep slopes are in the estate, he thought that it would be enough to measure the altitudes at only a limited number of sites and then approximate the altitudes of the rest based on them.

  Multiple approximations might be possible based on the same measurement results, in which case he wants to know the worst case, that is, one giving the lowest average altitude.

  Mr. Boat’s estate, which has a rectangular shape, is divided into grid-aligned rectangular areas of the same size. Altitude measurements have been carried out in some of these areas, and the measurement results are now at hand. The altitudes of the remaining areas are to be approximated on the assumption that altitudes of two adjoining areas sharing an edge differ at most 1.

  In the first sample given below, the land is divided into 5 × 4 areas. The altitudes of the areas at (1, 1) and (5, 4) are measured 10 and 3, respectively. In this case, the altitudes of all the areas are uniquely determined on the assumption that altitudes of adjoining areas differ at most 1.

  In the second sample, there are multiple possibilities, among which one that gives the lowest average altitude should be considered.

In the third sample, no altitude assignments satisfy the assumption on altitude differences.

  Your job is to write a program that approximates the average altitude of his estate. To be precise, the program should compute the total of approximated and measured altitudes of all the mesh-divided areas. If two or more different approximations are possible, the program should compute the total with the severest approximation, that is, one giving the lowest total of the altitudes.

Input

  The input consists of a single test case of the following format.

$w$ $d$ $n$
$x_1$ $y_1$ $z_1$
.
.
.
$x_n$ $y_n$ $z_n$

Here, $w$, $d$, and $n$ are integers between $1$ and $50$, inclusive. $w$ and $d$ are the numbers of areas in the two sides of the land. $n$ is the number of areas where altitudes are measured. The $i$-th line of the following $n$ lines contains three integers, $x_i$, $y_i$, and $z_i$ satisfying $1 \leq x_i \leq w$, $1 \leq y_i \leq d$, and $−100 \leq  z_i \leq 100$. They mean that the altitude of the area at $(x_i
, y_i)$ was measured to be $z_i$. At most one measurement result is given for the same area, i.e., for $i \ne j$, $(x_i, y_i) \ne (x_j , y_j)$.

Output

  If all the unmeasured areas can be assigned their altitudes without any conflicts with the measured altitudes assuming that two adjoining areas have the altitude difference of at most 1, output an integer that is the total of the measured or approximated altitudes of all the areas. If more than one such altitude assignment is possible, output the minimum altitude total among the possible assignments.

  If no altitude assignments satisfy the altitude difference assumption, output No.

Sample Input 1

5 4 2
1 1 10
5 4 3

Sample Output 1

130

Sample Input 2

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

Sample Output 2

-14

Sample Input 3

3 3 2
1 1 8
3 3 3

Sample Output 3

No

Sample Input 4

2 2 1
1 1 -100

Sample Output 4

-404

solutions: ["from collections import defaultdict\nimport sys\nreadline = sys.stdin.readline\nwrite = sys.stdout.write\ndef solve():\n    W, D, N = map(int, readline().split())\n    INF = 10**18\n    A = [[-INF]*D for i in range(W)]\n    E = []\n    QS = defaultdict(list)\n    dd = ((-1, 0), (0, -1), (1, 0), (0, 1))\n    B = 100\n    mi = B\n    for i in range(N):\n        x, y, z = map(int, readline().split()); x -= 1; y -= 1\n        A[x][y] = z\n        mi = min(mi, z)\n        QS[z].append((x, y))\n        E.append((x, y, z))\n    i = B\n    while mi <= i:\n        if i in QS:\n            for x, y in QS[i]:\n                for dx, dy in dd:\n                    nx = x + dx; ny = y + dy\n                    if not 0 <= nx < W or not 0 <= ny < D or A[nx][ny] != -INF:\n                        continue\n                    A[nx][ny] = i-1\n                    mi = min(mi, i-1)\n                    QS[i-1].append((nx, ny))\n        i -= 1\n    ans = 0\n    ok = 1\n    for x in range(W):\n        for y in range(D):\n            a = A[x][y]\n            for dx, dy in dd:\n                nx = x + dx; ny = y + dy\n                if not 0 <= nx < W or not 0 <= ny < D:\n                    continue\n                if abs(A[nx][ny] - a) > 1:\n                    ok = 0\n            ans += A[x][y]\n    if ok:\n        write(\"%d\\n\" % ans)\n    else:\n        write(\"No\\n\")\nsolve()\n", "from sys import stdin, stdout\nimport math\nimport bisect\nimport queue\n\nw, d, n = map(int, input().strip().split())\n\nmapper = [[-1000 for i in range(55)] for j in range(55)]\nstep = [[0, 1], [0, -1], [1, 0], [-1, 0]]\n\narr = []\n\nfor i in range(n):\n    tmp = tuple(map(int, stdin.readline().strip().split()))\n    arr.append(tmp)\n\nflag = 1\n\nfor i in range(len(arr)):\n    for j in range(i + 1, len(arr)):\n        if abs(arr[i][0] - arr[j][0]) + abs(arr[i][1] - arr[j][1]) < abs(arr[i][2] - arr[j][2]):\n            flag = 0\n            break\n    if flag == 0:\n        break\n\nif flag == 0:\n    stdout.writelines('No\\n')\nelse:\n    for each in arr:\n        mapper[each[0]][each[1]] = each[2]\n        chk = [[0 for i in range(55)] for j in range(55)]\n        chk[each[0]][each[1]] = 1\n        pend = queue.Queue()\n        pend.put(each)\n        while pend.qsize():\n            top = pend.get()\n            for each in step:\n                newpos = [top[0] - each[0], top[1] - each[1]]\n                if newpos[0] > 0 and newpos[0] <= w and newpos[1] > 0 and newpos[1] <= d and chk[newpos[0]][newpos[1]] < 1:\n                    mapper[newpos[0]][newpos[1]] = max(mapper[newpos[0]][newpos[1]], top[2] - 1)\n                    chk[newpos[0]][newpos[1]] += 1\n                    pend.put((newpos[0], newpos[1], mapper[newpos[0]][newpos[1]]))\n    ans = 0\n    for i in range(1, w + 1):\n        for j in range(1, d + 1):\n            ans += mapper[i][j]\n    stdout.writelines(str(ans) + '\\n')\n\n", "w, d, n = map(int, input().split())\nxyz = [list(map(int, input().split())) for _ in range(n)]\ninf = 10 ** 10\nans = 0\nfor i in range(1, w + 1):\n    for j in range(1, d + 1):\n        min_ = -inf\n        max_ = inf\n        for x, y, z in xyz:\n            min_ = max(min_, z - abs(x - i) - abs(y - j))\n            max_ = min(max_, z + abs(x - i) + abs(y - j))\n        if max_ < min_:\n            print(\"No\")\n            exit()\n        ans += min_\nprint(ans)\n", "import math,string,itertools,fractions,heapq,collections,re,array,bisect,sys,copy,functools\nimport time,random\n\nsys.setrecursionlimit(10**7)\ninf = 10**20\neps = 1.0 / 10**10\nmod = 10**9+7\ndd = [(-1,0),(0,1),(1,0),(0,-1)]\nddn = [(-1,0),(-1,1),(0,1),(1,1),(1,0),(1,-1),(0,-1),(-1,-1)]\n\ndef LI(): return list(map(int, sys.stdin.readline().split()))\ndef LLI(): return [list(map(int, l.split())) for l in sys.stdin.readlines()]\ndef LI_(): return [int(x)-1 for x in sys.stdin.readline().split()]\ndef LF(): return [float(x) for x in sys.stdin.readline().split()]\ndef LS(): return sys.stdin.readline().split()\ndef I(): return int(sys.stdin.readline())\ndef F(): return float(sys.stdin.readline())\ndef S(): return input()\ndef pf(s): return print(s, flush=True)\ndef pe(s): return print(str(s), file=sys.stderr)\ndef JA(a, sep): return sep.join(map(str, a))\ndef JAA(a, s, t): return s.join(t.join(map(str, b)) for b in a)\n\n\ndef main():\n    w,h,n = LI()\n    aa = [LI() for _ in range(n)]\n    q = []\n    r = [[None] * w for _ in range(h)]\n    for x,y,z in aa:\n        r[y-1][x-1] = z\n        heapq.heappush(q, (-z, (y-1,x-1)))\n\n    v = collections.defaultdict(bool)\n    while len(q):\n        k, u = heapq.heappop(q)\n        if v[u]:\n            continue\n        v[u] = True\n        y = u[0]\n        x = u[1]\n\n        for dy,dx in dd:\n            uy = y+dy\n            ux = x+dx\n            if uy < 0 or uy >= h or ux < 0 or ux >= w:\n                continue\n            uv = (uy,ux)\n            if v[uv]:\n                continue\n            vd = -k - 1\n            if r[uy][ux] is None:\n                r[uy][ux] = vd\n                heapq.heappush(q, (-vd, uv))\n            else:\n                if abs(r[uy][ux] + k) > 1:\n                    return 'No'\n\n    return sum(sum(_) for _ in r)\n\n\nprint(main())\n\n\n\n", "from heapq import heappop, heappush\n\nw, d, n = map(int, input().split())\npoints = []\ninf = -1 << 20\nheight = [[inf] * d for i in range(w)]\nfor i in range(n):\n    x, y, z = map(int, input().split())\n    x -= 1\n    y -= 1\n    height[x][y] = z\n    heappush(points, (-z, x, y))\n\ndxy = [[1, 0], [-1, 0], [0, 1], [0, -1]]\n\nwhile points:\n    z, x, y = heappop(points)\n    z *= -1\n    for dx, dy in dxy:\n        if 0 <= dx + x < w and 0 <= dy + y < d:\n            if height[dx + x][dy + y] != inf:\n                continue\n            height[dx + x][dy + y] = z - 1\n            heappush(points, (1 - z, x + dx, y + dy))\n\n\nfor x in range(w):\n    for y in range(d):\n        for dx, dy in dxy:\n            if 0 <= dx + x < w and 0 <= dy + y < d:\n                if abs(height[x][y] - height[dx + x][dy + y]) > 1:\n                    print(\"No\")\n                    exit()\n\nprint(sum([sum(i) for i in height]))\n\n", "#!/usr/bin/env python3\n \nimport sys\nimport math\nfrom bisect import bisect_right as br\nfrom bisect import bisect_left as bl\nsys.setrecursionlimit(2147483647)\nfrom heapq import heappush, heappop,heappushpop\nfrom collections import defaultdict\nfrom itertools import accumulate\nfrom collections import Counter\nfrom collections import deque\nfrom operator import itemgetter\nfrom itertools import permutations\nmod = 10**9 + 7\ninf = float('inf')\ndef I(): return int(sys.stdin.readline())\ndef LI(): return list(map(int,sys.stdin.readline().split()))\n\nh, w, n = LI()\nyxz = [LI() for _ in range(n)]\nfor i in range(n-1):\n    y, x, z = yxz[i]\n    for j in range(i+1, n):\n        y_, x_, z_ = yxz[j]\n        d = abs(x - x_) + abs(y - y_)\n        if d < abs(z - z_):\n            print(\"No\")\n            quit()\n\nlb = [[-inf] * w for _ in range(h)]\n\nfor y, x, z in yxz:\n    que = deque([(y-1, x-1, z)])\n    lb[y-1][x-1] = max(lb[y-1][x-1], z)\n    while que:\n        y, x, z = que.popleft()\n        for dx, dy in zip([0, 1, 0, -1], [1, 0, -1, 0]):\n            ny, nx = y + dy, x + dx\n            if 0 <= ny < h and 0 <= nx < w:\n                if lb[ny][nx] < z - 1:\n                    lb[ny][nx] = z - 1\n                    que.append((ny, nx, z - 1))\nans = 0\nfor i in range(h):\n    ans += sum(lb[i])\nprint(ans)\n", "#!/usr/bin/python3\n\nimport os\nimport sys\n\n\ndef main():\n    W, D, N = read_ints()\n    M = [tuple(read_ints()) for _ in range(N)]\n    ans = solve(W, D, N, M)\n    if ans is None:\n        print('No')\n    else:\n        print(ans)\n\n\ndef solve(W, D, N, M):\n    INF = 999\n    H = [[INF] * W for _ in range(D)]\n\n    hmap = {}\n    for h in range(-210, 101):\n        hmap[h] = set()\n\n    for x, y, z in M:\n        x -= 1\n        y -= 1\n        hmap[z].add((x, y))\n        H[y][x] = z\n\n    for h in range(100, -210, -1):\n        for x, y in hmap[h]:\n            if H[y][x] == INF:\n                H[y][x] = h\n            elif H[y][x] > h:\n                continue\n\n            for dx, dy in ((1, 0), (-1, 0), (0, 1), (0, -1)):\n                nx = x + dx\n                ny = y + dy\n                if nx < 0 or nx >= W or ny < 0 or ny >= D:\n                    continue\n                if H[ny][nx] < h - 1:\n                    return None\n                if H[ny][nx] == INF:\n                    hmap[h - 1].add((nx, ny))\n\n    return sum([sum(r) for r in H])\n\n\n###############################################################################\n\nDEBUG = 'DEBUG' in os.environ\n\n\ndef inp():\n    return sys.stdin.readline().rstrip()\n\n\ndef read_int():\n    return int(inp())\n\n\ndef read_ints():\n    return [int(e) for e in inp().split()]\n\n\ndef dprint(*value, sep=' ', end='\\n'):\n    if DEBUG:\n        print(*value, sep=sep, end=end)\n\n\nif __name__ == '__main__':\n    main()\n\n", "def isValid(row, col, ROWS, COLS):\n    return row >= 0 and row < ROWS and col >= 0 and col < COLS\n\ndef isSteep(board, row, col, ROWS, COLS):\n    global adjR, adjC\n\n    h = board[row][col]\n    for i in range(4):\n        rr = row + adjR[i]\n        cc = col + adjC[i]\n        if isValid(rr, cc, ROWS, COLS):\n            diff = abs(h - board[rr][cc])\n            if diff > 1:\n                return True\n    return False\n\ndef update(board, row, col, ROWS, COLS):\n    global adjR, adjC, given\n    arr = []\n\n    h = board[row][col]\n    for i in range(4):\n        rr = row + adjR[i]\n        cc = col + adjC[i]\n        if (rr, cc) in given:\n            continue\n        if isValid(rr, cc, ROWS, COLS):\n            if board[rr][cc] == None or board[rr][cc] < h - 1:\n                board[rr][cc] = h - 1\n                arr.append((rr, cc))\n    return arr\n\nif __name__ == '__main__':\n    COLS, ROWS, N = list(map(int, input().split()))\n\n    board = [ [ None for _ in range(COLS) ] for _ in range(ROWS) ]\n    plist = []\n\n    adjR = [-1, 0, 0, 1]\n    adjC = [0, -1, 1, 0]\n\n    given = set()\n\n    for _ in range(N):\n        c, r, h = list(map(int, input().strip().split()))\n        board[r - 1][c - 1] = h\n        plist.append((r-1, c-1))\n        given.add((r-1, c-1))\n\n    while len(plist) > 0:\n        row, col = plist.pop(0)\n        updated = update(board, row, col, ROWS, COLS)\n        plist.extend(updated)\n\n    isPossible = True\n    total = 0\n    for r in range(ROWS):\n        for c in range(COLS):\n            isPossible = isPossible and not isSteep(board, r, c, ROWS, COLS)\n            if not isPossible:\n                break\n            total += board[r][c]\n        if not isPossible:\n            break\n\n    print(total if isPossible else \"No\")\n", "from collections import deque\n\n\nw,h,n = map(int,input().split())\nQ = []\nfor i in range(n):\n    x,y,z = map(int,input().split())\n    Q.append((x-1,y-1,z))\n\nG = [[-10**9]*w for _ in range(h)]\n\n#\u5f15\u6570\u306f\u30ea\u30b9\u30c8\u3068\u958b\u59cb\u70b9\ndef bfs(H,W,Z):\n    que = deque()\n    que.append((H,W))\n    G_ = [[10**9]*w for _ in range(h)]\n    G_[H][W]=Z\n    while que:\n        v1,v2 = que.popleft()\n        for a,b in ((0,1),(1,0),(0,-1),(-1,0)):\n            if(not(0<=v1+a<h and 0<=v2+b<w)) or G_[v1+a][v2+b]!=10**9:\n                continue\n            G_[v1+a][v2+b]=G_[v1][v2]-1\n            que.append((v1+a,v2+b))\n    return G_\n\nfor i in range(n):\n    x,y,z = Q[i]\n    G_ = bfs(y,x,z)\n    for hh in range(h):\n        for ww in range(w):\n            G[hh][ww]=max(G[hh][ww],G_[hh][ww])\n\nfor i in range(n):\n    x,y,z = Q[i]\n    if(G[y][x]!=z):\n        print(\"No\")\n        exit()\n\n\nans = sum(sum(G[i][j]for j in range(w))for i in range(h))\nprint(ans)\n"]

source: aizu

question:
Estimating the Flood Risk

  Mr. Boat is the owner of a vast extent of land. As many typhoons have struck Japan this year, he became concerned of flood risk of his estate and he wants to know the average altitude of his land. The land is too vast to measure the altitude at many spots. As no steep slopes are in the estate, he thought that it would be enough to measure the altitudes at only a limited number of sites and then approximate the altitudes of the rest based on them.

  Multiple approximations might be possible based on the same measurement results, in which case he wants to know the worst case, that is, one giving the lowest average altitude.

  Mr. Boat’s estate, which has a rectangular shape, is divided into grid-aligned rectangular areas of the same size. Altitude measurements have been carried out in some of these areas, and the measurement results are now at hand. The altitudes of the remaining areas are to be approximated on the assumption that altitudes of two adjoining areas sharing an edge differ at most 1.

  In the first sample given below, the land is divided into 5 × 4 areas. The altitudes of the areas at (1, 1) and (5, 4) are measured 10 and 3, respectively. In this case, the altitudes of all the areas are uniquely determined on the assumption that altitudes of adjoining areas differ at most 1.

  In the second sample, there are multiple possibilities, among which one that gives the lowest average altitude should be considered.

In the third sample, no altitude assignments satisfy the assumption on altitude differences.

![image](1.png)

  Your job is to write a program that approximates the average altitude of his estate. To be precise, the program should compute the total of approximated and measured altitudes of all the mesh-divided areas. If two or more different approximations are possible, the program should compute the total with the severest approximation, that is, one giving the lowest total of the altitudes.

Input

  The input consists of a single test case of the following format.

$w$ $d$ $n$
$x_1$ $y_1$ $z_1$
.
.
.
$x_n$ $y_n$ $z_n$

Here, $w$, $d$, and $n$ are integers between $1$ and $50$, inclusive. $w$ and $d$ are the numbers of areas in the two sides of the land. $n$ is the number of areas where altitudes are measured. The $i$-th line of the following $n$ lines contains three integers, $x_i$, $y_i$, and $z_i$ satisfying $1 \leq x_i \leq w$, $1 \leq y_i \leq d$, and $−100 \leq  z_i \leq 100$. They mean that the altitude of the area at $(x_i
, y_i)$ was measured to be $z_i$. At most one measurement result is given for the same area, i.e., for $i \ne j$, $(x_i, y_i) \ne (x_j , y_j)$.

Output

  If all the unmeasured areas can be assigned their altitudes without any conflicts with the measured altitudes assuming that two adjoining areas have the altitude difference of at most 1, output an integer that is the total of the measured or approximated altitudes of all the areas. If more than one such altitude assignment is possible, output the minimum altitude total among the possible assignments.

  If no altitude assignments satisfy the altitude difference assumption, output No.

Sample Input 1

5 4 2
1 1 10
5 4 3

Sample Output 1

130

Sample Input 2

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

Sample Output 2

-14

Sample Input 3

3 3 2
1 1 8
3 3 3

Sample Output 3

No

Sample Input 4

2 2 1
1 1 -100

Sample Output 4

-404

data_split: test