solutions: ["n = int(input())\nA = [int(input()) for i in range(5)]\nprint(5 + (n - 1) // min(A))\n", "(N, *x) = map(int, open(0))\nprint(5 + (N - 1) // min(x))\n", "import math\n(n, *l) = map(int, open(0))\nprint(math.ceil(n / min(l)) + 4)\n", "import math as mt\nn = int(input())\nlst = [int(input()) for i in range(5)]\nprint(mt.ceil(n / min(lst)) + 4)\n", "n = int(input())\na = int(input())\nb = int(input())\nc = int(input())\nd = int(input())\ne = int(input())\nans = 5 + (n - 1) // min(a, b, c, d, e)\nprint(ans)\n", "(N, *A) = map(int, open(0).read().split())\nprint(5 + (N - 1) // min(A))\n", "import math\nn = int(input())\na = int(input())\nb = int(input())\nc = int(input())\nd = int(input())\ne = int(input())\nans = math.ceil(n / min(a, b, c, d, e)) + 4\nprint(ans)\n", "n = int(input())\na = []\nfor i in range(5):\n\ta.append(int(input()))\nx = min(a)\nt = n // x\nif n % x != 0:\n\tt += 1\nt += 4\nprint(t)\n", "N = int(input())\nl = [int(input()) for _ in range(5)]\nbn = -(-N // min(l))\nprint(4 + bn)\n", "n = int(input())\na = [int(input()) for _ in range(5)]\nprint(-(-n // min(a)) + 4)\n", "n = int(input())\nx = min([int(input()) for i in [0] * 5])\nprint((n + x - 1) // x + 4)\n", "n = int(input())\nx = list((int(input()) for i in range(5)))\nprint(-(-n // min(x)) + 4)\n", "print(-(-int(input()) // min([int(input()) for _ in range(5)])) + 4)\n", "import math\nprint(math.ceil(int(input()) / min([int(input()) for i in range(5)])) + 4)\n", "lst = [int(input()) for _ in range(6)]\nprint(4 + -(-lst[0] // min(lst[1:])))\n", "N = int(input())\nA = [int(input()) for _ in range(5)]\nprint(-(-N // min(A)) - 1 + 5)\n", "n = int(input())\na = [int(input()) for i in range(5)]\nans = 0\nprint(-(-n // min(a)) + 4)\n", "n = int(input())\nl = [int(input()) for i in range(5)]\nprint(-(-n // min(l)) + 4)\n", "import math\nN = int(input())\nlsT = []\nfor i in range(5):\n\tlsT.append(int(input()))\nprint(4 + math.ceil(N / min(lsT)))\n", "n = int(input())\nm = min([int(input()) for x in range(5)])\nprint((m + n - 1) // m + 4)\n", "(n, *l) = map(int, open(0).read().split())\nprint(4 + (n + min(l) - 1) // min(l))\n", "import math\nn = int(input())\ncapa = [int(input()) for _ in range(5)]\nprint(4 + math.ceil(n / min(capa)))\n", "N = int(input())\nABCDE = [int(input()) for _ in range(5)]\nprint(4 + -(-N // min(ABCDE)))\n", "(N, *T) = map(int, open(0).read().split())\nt = min(T)\nprint((N + t - 1) // t + 4)\n", "(n, *x) = [int(input()) for _ in range(6)]\nprint(-(-n // min(x)) + 4)\n", "(n, *a) = map(int, open(0))\nprint(4 - -n // min(a))\n", "N = int(input())\nX = [int(input()) for _ in range(5)]\nv = (N - 1) // min(X)\nprint(v + 5)\n", "import math\npeople_num = int(input(''))\nnum_trans = []\nfor i in range(5):\n\tnum_trans.append(int(input('')))\nprint(math.ceil(people_num / min(num_trans) + 4))\n", "(N, *X) = [int(input()) for _ in range(6)]\nmi = min(X)\nprint(4 + (N + mi - 1) // mi)\n", "n = int(input())\nx = min([int(input()) for _ in range(5)])\nprint(n // x + 5 if x != 1 else n // x + 4)\n", "N = int(input())\nA = [int(input()) for i in range(5)]\nprint(5 + -(-N // min(A)) - 1)\n", "N = int(input())\nT = [0] * 5\nfor i in range(5):\n\tT[i] = int(input())\nfrom math import ceil\nt = min(T)\nprint(ceil(N / t) + 4)\n", "n = int(input())\nC = [int(input()) for i in range(5)]\nprint(4 - -n // min(C))\n", "n = int(input())\nx = [int(input()) for _ in range(5)]\ncap = min(x)\nans = (n + cap - 1) // cap + 4\nprint(ans)\n", "N = int(input())\nT = []\nfor _ in range(5):\n\tT.append(int(input()))\nprint((N + min(T) - 1) // min(T) + 4)\n", "n = int(input())\nlst = [int(input()) for i in range(5)]\nans = -(-n // min(lst)) + 4\nprint(ans)\n", "import math\nn = int(input())\nabc = [int(input()) for i in range(5)]\nans = 4 + math.ceil(n / min(abc))\nprint(ans)\n", "l = [int(input()) for _ in range(6)]\nN = l[0]\nl = l[1:]\nprint(-(-N // min(l)) + 4)\n", "from math import ceil\n(N, *A) = [int(input()) for _ in range(6)]\nprint(ceil(N / min(A)) + 4)\n", "n = int(input())\na = int(input())\nb = int(input())\nc = int(input())\nd = int(input())\ne = int(input())\naa = -(-n // a)\nbb = -(-n // b)\ncc = -(-n // c)\ndd = -(-n // d)\nee = -(-n // e)\nprint(max(aa, bb, cc, dd, ee) + 4)\n", "(N, *I) = [int(input()) for _ in range(6)]\nmn = min(I)\nprint(5 + (N + mn - 1) // mn - 1)\n", "print(~-int(input()) // min(eval('int(input()),' * 5)) + 5)\n", "N = int(input())\nmin_ = min((int(input()) for _ in range(5)))\nprint((N - 1) // min_ + 5)\n", "n = int(input())\nt = [int(input()) for i in range(5)]\nm = min(t)\nprint(-(-n // m) + 4)\n", "import math\nn = int(input())\nA = [int(input()) for _ in range(5)]\nans = math.ceil(n / min(A)) + 4\nprint(ans)\n", "n = int(input())\nx = min([int(input()) for _ in range(5)])\nprint((n - 1) // x + 5)\n", "n = int(input())\na = list((int(input()) for _ in range(5)))\nMin = min(a)\nif n <= Min:\n\tprint(5)\n\treturn\nx = n // Min\nif n % Min != 0:\n\tx += 1\nprint(4 - a.index(Min) + x + a.index(Min))\n", "N = int(input())\nA = [int(input()) for _ in range(5)]\nans = -(-N // min(A)) + 4\nprint(ans)\n", "n = int(input())\na = [int(input()) for i in range(5)]\nprint((n - 1) // min(a) + 5)\n", "(n, *a) = map(int, open(0).read().split())\na = min(a)\nprint(4 + (n + a - 1) // a)\n", "n = int(input())\na = [int(input()) for _ in range(5)]\nif n % min(a) != 0:\n\tn += min(a) - n % min(a)\nif min(a) >= n:\n\tprint(5)\nelse:\n\tprint(int(n / min(a)) + 4)\n", "n = int(input()) - 1\nlst = [int(input()) for i in range(5)]\nm = min(lst)\nprint(n // m + 5)\n", "import math\nn = int(input())\na = []\nfor i in range(5):\n\ta.append(int(input()))\nprint(4 + math.ceil(n / min(a)))\n", "n = int(input())\nlim = [int(input()) for _ in range(5)]\nprint(-(-n // min(lim)) + 4)\n", "n = int(input())\nabcde = [int(input()) for _ in range(5)]\nprint(4 - -n // min(abcde))\n", "n = int(input())\nl = list((int(input()) for _ in range(5)))\nprint(-(-n // min(l)) + 4)\n", "(n, *d) = map(int, open(0))\nbn = min(d)\nprint((n + bn - 1) // bn + 4)\n", "n = int(input())\nl = [int(input()) for _ in range(5)]\nans = 0 - -n // min(l) + 4\nprint(ans)\n", "from math import *\nN = int(input())\nabcde = [int(input()) for _ in range(5)]\nprint(ceil(N / min(abcde)) + 4)\n", "import math\nn = int(input())\nx = []\nfor i in range(5):\n\tx.append(int(input()))\nif n == min(x):\n\tprint(5)\nelse:\n\tprint(4 + math.ceil(n / min(x)))\n", "import math\nn = int(input())\na = int(input())\nb = int(input())\nc = int(input())\nd = int(input())\ne = int(input())\n_min = min([a, b, c, d, e])\n_ans = math.ceil(n / _min)\nprint(_ans + 4)\n", "N = int(input())\nA = [-(-N // int(input())) for _ in range(5)]\nprint(5 + max(A) - 1)\n", "n = int(input())\nnum = [int(input()) for _ in range(5)]\nprint(4 - n // -min(num))\n", "N = int(input())\nM = min((int(input()) for _ in [0] * 5))\nprint(N // M + (5 if N % M else 4))\n", "a = [int(input()) for _ in range(6)]\nb = min(a[1:])\nprint((a[0] + b - 1) // b + 4)\n", "n = int(input())\na = [int(input()) for _ in range(5)]\nprint((n - 1) // min(a) + 5)\n", "n = int(input())\nmb = [int(input()) for i in range(5)]\nprint(-(-n // min(mb)) + 4)\n", "print((int(input()) - 1) // min((int(input()) for i in [0] * 5)) + 5)\n", "print(-(-int(input()) // min([int(input()) for i in range(5)])) + 4)\n", "n = int(input())\nt = [int(input()) for _ in range(5)]\nm = min(t)\nprint((n + m - 1) // m + 4)\n", "import math\nN = int(input())\nV = [int(input()) for _ in range(5)]\nlatest = min(V)\nans = math.ceil(N / latest) + 4\nprint(ans)\n", "N = int(input())\nls = [int(input()) for _ in range(5)]\nX = min(ls)\nprint((N + X - 1) // X + 4)\n", "import sys\nimport math\nfrom collections import defaultdict, deque, Counter\nfrom copy import deepcopy\nfrom bisect import bisect, bisect_right, bisect_left\nfrom heapq import heapify, heappop, heappush\ninput = sys.stdin.readline\n\ndef RD():\n\treturn input().rstrip()\n\ndef F():\n\treturn float(input().rstrip())\n\ndef I():\n\treturn int(input().rstrip())\n\ndef MI():\n\treturn map(int, input().split())\n\ndef MF():\n\treturn map(float, input().split())\n\ndef LI():\n\treturn list(map(int, input().split()))\n\ndef TI():\n\treturn tuple(map(int, input().split()))\n\ndef LF():\n\treturn list(map(float, input().split()))\n\ndef Init(H, W, num):\n\treturn [[num for i in range(W)] for j in range(H)]\n\ndef main():\n\tN = I()\n\tL = [I() for i in range(5)]\n\tprint(math.ceil(N / min(L) + 4))\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "n = int(input())\ntp = []\ntmp = 10 ** 15\nfor _ in range(5):\n\ta = int(input())\n\tif tmp > a:\n\t\ttmp = a\n\ttp.append(a)\nif tmp >= n:\n\tprint(5)\n\treturn\ncnt = n // tmp\nmod = n % tmp\nif mod > 0:\n\tprint(5 + cnt)\nelse:\n\tprint(5 + cnt - 1)\n", "n = int(input())\nnu = min([int(input()) for i in range(5)])\nprint(4 + bool(n % nu) + n // nu)\n", "N = int(input())\nA = int(input())\nB = int(input())\nC = int(input())\nD = int(input())\nE = int(input())\nfrom math import ceil\na = ceil(N / A)\nF = [A, B, C, D, E]\nfor i in range(1, 5):\n\tif F[i - 1] <= F[i]:\n\t\ta += 1\n\telse:\n\t\tb = ceil(N / F[i])\n\t\ta = max(a + 1, b + i)\nprint(a)\n", "from math import ceil\n(n, a, b, c, d, e) = [int(input()) for i in range(6)]\nprint(ceil(n / min(a, b, c, d, e)) + 4)\n", "(N, *C) = [int(input()) for _ in range(6)]\nprint(4 + N // min(C) + (0 != N % min(C)))\n", "a = [int(input()) for i in [0] * 6]\nmini = min(a[1:])\nprint(-(-a[0] // mini) + 4)\n", "print((int(input()) - 1) // min((int(input()) for _ in range(5))) + 5)\n", "n = int(input())\na = []\nimport math\na.append(math.ceil(n / int(input())))\na.append(math.ceil(n / int(input())))\na.append(math.ceil(n / int(input())))\na.append(math.ceil(n / int(input())))\na.append(math.ceil(n / int(input())))\nprint(max(a) + 5 - 1)\n", "n = int(input())\na = [int(input()) for i in range(5)]\namin = min(a)\na1 = (n - 1) // amin + 1 + 4\nprint(a1)\n", "n = int(input())\nl = [int(input()) for i in range(5)]\nif n % min(l) == 0:\n\tprint(n // min(l) + 4)\nelse:\n\tprint(n // min(l) + 5)\n", "a = []\nfor i in range(6):\n\ta.append(int(input()))\nprint((a[0] - 1) // min(a[1:]) + 5)\n", "def solve(N, A, B, C, D, E):\n\ttmp = min(A, B, C, D, E)\n\t(tmp, tmp2) = divmod(N, tmp)\n\ttmp += 0 if tmp2 == 0 else 1\n\tprint(tmp + 4)\n\ndef __starting_point():\n\tN = int(input())\n\tA = int(input())\n\tB = int(input())\n\tC = int(input())\n\tD = int(input())\n\tE = int(input())\n\tsolve(N, A, B, C, D, E)\n__starting_point()\n", "n = int(input())\nx = min([int(input()) for _ in range(5)])\n(a, b) = divmod(n, x)\nif b == 0:\n\tprint(5 + (a - 1))\nelse:\n\tprint(5 + a)\n", "A = [int(input()) for _ in range(6)]\nm = min(A[1:])\nprint((A[0] + m - 1) // m + 4)\n", "N = int(input())\nA = [int(input()) for i in range(5)]\nX = min(A)\nans = (N + X - 1) // X + 4\nprint(ans)\n", "N = int(input())\nA = [0] * 5\nfor i in range(5):\n\tA[i] = int(input())\nprint(-(-N // min(A)) + 4)\n", "(N, A, B, C, D, E) = [int(input()) for _ in range(6)]\nx = min(A, B, C, D, E)\nans = (N - 1) // x + 5\nprint(ans)\n", "from math import ceil\nn = int(input())\na = [int(input()) for _ in range(5)]\nprint(ceil(n / min(a)) + 4)\n", "N = int(input())\nM = min((int(input()) for _ in [0] * 5))\nprint((N + M - 1) // M + 4)\n", "N = int(input())\nM = min([int(input()) for i in range(5)])\nprint((N + M - 1) // M + 4)\n", "(n, *a) = [int(input()) for _ in range(6)]\nprint(max(int(n - 1) // min(a), 0) + 5)\n", "a = [int(input()) for _ in range(6)]\nn = a.pop(0)\nb = min(a)\nprint((n - 1) // b + 5)\n", "(N, *capas) = list(map(int, open(0).read().split()))\nmin_capa = min(capas)\nprint((N + min_capa - 1) // min_capa + 4)\n", "(n, *a) = [int(input()) for i in range(6)]\nm = sorted(a)[0]\nprint(n // m + 5 if n % m > 0 else n // m + 4)\n", "n = int(input())\nl = [int(input()) for i in range(5)]\nprint(5 + -(-n // min(l)) - 1)\n", "(n, *a) = map(int, open(0))\nm = min(a)\nprint((n + m - 1) // m + 4)\n", "N = int(input())\nt = [int(input()) for _ in range(5)]\na = min(t)\nprint(5 + (N - 1) // a)\n", "(n, a, b, c, d, e) = [int(input()) for _ in range(6)]\nprint(4 + (0 - -n // min(a, b, c, d, e)))\n", "(n, *l) = [int(input()) for _ in range(6)]\nm = min(l)\nif m == 1:\n\tprint(n + 4)\nelse:\n\tprint(n // m + 5)\n", "(a, *b) = eval('int(input()),' * 6)\nprint(4 - -a // min(b))\n", "(N, *A) = map(int, open(0).read().split())\nprint((N + min(A) - 1) // min(A) + 4)\n", "import math\nA = [int(input()) for _ in range(6)]\nprint(math.ceil(A[0] / min(A[1:])) + 4)\n", "n = int(input())\ndata = [int(input()) for i in range(5)]\nm = min(data)\nif n % m == 0:\n\tprint(4 + n // m)\nelse:\n\tprint(5 + n // m)\n", "(N, A, B, C, D, E) = [int(input()) for i in range(6)]\nm = min(A, B, C, D, E)\nprint((N - 1) // m + 5)\n", "(n, *ti) = [int(input()) for _ in range(6)]\nimport math\nprint(4 + math.ceil(n / min(ti)))\n", "(N, *A) = map(int, open(0))\nprint(5 + (N - 1) // min(A))\n", "n = int(input())\ntp = [int(input()) for _ in range(5)]\nprint(-(-n // min(tp)) + 4)\n", "print((int(input()) - 1) // sorted([int(input()) for _ in range(5)])[0] + 5)\n", "h = int(input())\nl = min([int(input()) for i in range(5)])\nprint(4 - -h // l)\n", "n = int(input())\np = [int(input()) for _ in range(5)]\nprint((n - 1) // min(p) + 5)\n", "a = [int(input()) for i in range(6)]\nmi = min(a)\nif a[0] == mi:\n\tprint(5)\nelif a[0] % mi == 0:\n\tprint(5 + a[0] // mi - 1)\nelse:\n\tprint(5 + a[0] // mi)\n", "n = int(input())\nm = [int(input()) for _ in range(5)]\ns = min(m)\nprint((n % s > 0) + 4 + n // s)\n", "N = int(input())\nli = [0, 0, 0, 0, 0]\nfor i in range(5):\n\tli[i] = int(input())\nif N % min(li) == 0:\n\ta = N // min(li) - 1\nelse:\n\ta = N // min(li)\nans = 5 + a\nprint(ans)\n", "n = int(input())\na = int(input())\nb = int(input())\nc = int(input())\nd = int(input())\ne = int(input())\nnum_list = [a, b, c, d, e]\nif n % min(num_list) == 0:\n\tprint(4 + n // min(num_list))\nelse:\n\tprint(5 + n // min(num_list))\n", "n = int(input())\nx = [int(input()) for i in range(5)]\nd = n // min(x)\nif n % min(x) == 0:\n\tprint(d + 4)\nelse:\n\tprint(d + 5)\n", "n = int(input())\ngates = [int(input()) for _ in range(5)]\nbn = min(gates)\nprint(int((n + bn - 1) / bn) + 4)\n", "N = int(input())\nnums = [int(input()) for _ in range(5)]\nprint(4 - -N // min(nums))\n", "from math import ceil\nn = int(input())\na = [int(input()) for i in range(5)]\nprint(ceil(n / min(a)) - 1 + 5)\n", "(n, *l) = map(int, open(0).read().split())\nprint((n - 1) // min(l) + 5)\n", "import math\nmembers = 0\nmin_value = 10 ** 16\nfor i in range(6):\n\tif i == 0:\n\t\tmembers = int(input())\n\telse:\n\t\tcurrent = int(input())\n\t\tif current < min_value:\n\t\t\tmin_value = current\ncounter = math.ceil(members / min_value)\ncounter += 4\nprint(counter)\n", "N = int(input())\nts = [int(input()) for i in range(5)]\nprint(int((N - 1) / min(ts)) + 5)\n", "(n, *a) = [int(input()) for _ in range(6)]\nprint((n + min(a) - 1) // min(a) + 4)\n", "(n, *cap) = map(int, open(0).read().split())\nm = min(cap)\nprint(4 + (n + m - 1) // m)\n", "n = int(input())\ntime = [int(input()) for _ in range(5)]\ncount = 0\nif all([i >= n for i in time]):\n\tprint(5)\nelse:\n\tsmallest = min(time)\n\tsmallest_index = time.index(smallest)\n\tcount += n // smallest\n\tif n % smallest != 0:\n\t\tcount += 1\n\tprint(count + 4)\n", "(n, a, b, c, d, e) = [int(input()) for _ in range(6)]\nminVal = min(a, b, c, d, e)\nif n // minVal == n / minVal:\n\tans = n // minVal + 4\nelse:\n\tans = n // minVal + 1 + 4\nprint(ans)\n", "n = int(input())\nt = [int(input()) for _ in range(5)]\nk = (n - 1) // min(t)\nprint(k + 5)\n", "from math import ceil\nN = int(input())\nA = [0] * 5\nfor i in range(5):\n\tA[i] = int(input())\nans = ceil(N / min(A)) + 4\nprint(ans)\n", "import math\n\ndef main():\n\tn = int(input())\n\tcsr = []\n\tfor _ in range(5):\n\t\tcsr.append(int(input()))\n\tprint(4 + math.ceil(n / min(csr)))\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "import math\na = int(input())\nb = []\nfor i in range(5):\n\tb.append(int(input()))\nc = min(b)\nd = math.ceil(a / c)\nprint(d + 4)\n", "import math\nN = int(input())\nA = [int(input()) for _ in range(5)]\nn = min(A)\nfor i in range(5):\n\tif n == A[i]:\n\t\tp = i\n\t\tbreak\nk = math.ceil(N / n)\nprint(k + 4)\n", "n = int(input())\na = int(input())\nb = int(input())\nc = int(input())\nd = int(input())\ne = int(input())\nprint(n // min(a, b, c, d, e) + 4) if n % min(a, b, c, d, e) == 0 else print(n // min(a, b, c, d, e) + 1 + 4)\n", "N = int(input())\nA = int(input())\nB = int(input())\nC = int(input())\nD = int(input())\nE = int(input())\nm = min(A, B, C, D, E)\nif N % m != 0:\n\tprint(N // m + 5)\nelse:\n\tprint(N // m + 4)\n", "n = int(input())\nA = []\nfor i in range(5):\n\tA.append(int(input()))\nminA = min(A)\nimport math\nprint(4 + math.ceil(n / minA))\n", "(N, *x) = map(int, open(0))\nprint(4 - -N // min(x))\n", "from math import *\nn = int(input())\na = [int(input()) for _ in range(5)]\nans = ceil(n / a[0])\nmin = 0\nfor i in range(1, 5):\n\tif a[i] >= a[min]:\n\t\tans += 1\n\telse:\n\t\tans = ceil(n / a[i]) + i\n\t\tmin = i\nprint(ans)\n", "import math\nN = int(input().rstrip())\nA = int(input().rstrip())\nB = int(input().rstrip())\nC = int(input().rstrip())\nD = int(input().rstrip())\nE = int(input().rstrip())\nprint(math.ceil(N / min(A, B, C, D, E)) + 4)\n", "(N, A, B, C, D, E) = [int(input()) for i in range(6)]\nM = min(A, B, C, D, E)\nprint((N + M - 1) // M + 4)\n", "import math\nN = int(input())\nA = [int(input()) for _ in range(5)]\nprint(math.ceil(N / min(A)) + 4)\n", "n = int(input())\nm = 10 ** 15 + 1\na = [int(input()) for _ in range(5)]\nprint((n - 1) // min(a) + 5)\n", "import math\nn = int(input())\nnums = [int(input()) for _ in range(5)]\nmin_n = math.ceil(n / min(nums))\nprint(4 + min_n)\n", "def main():\n\tn = int(input())\n\tdata = [int(input()) for i in range(5)]\n\t(quo, rem) = divmod(n, min(data))\n\tprint(4 + quo + bool(rem))\nmain()\n", "(n, *t) = map(int, open(0).read().split())\nprint(int((n - 0.1) // min(t)) + 5)\n", "n = int(input())\nmv = [int(input()) for i in range(5)]\nprint(-(-n // min(mv)) + 4)\n", "import math\nimport numpy as np\n(N, *T) = list(map(int, open(0).read().split()))\nX = np.array(T).min()\nprint(4 + math.ceil(N / float(X)))\n", "(n, *x) = [int(input()) for i in range(6)]\nprint((n + min(x) - 1) // min(x) + 4)\n", "(n, *city) = [int(input()) for _ in range(6)]\nprint(4 - -n // min(city))\n", "n = int(input())\nr = [int(input()) for _ in range(5)]\nm = min(r)\nprint(-(-n // m) + 4)\n", "N = int(input())\na = [int(input()) for _ in range(5)]\nprint(-(-N // min(a)) + 4)\n", "(n, *a) = map(int, open(0))\np = min(a)\nprint([5, -(-n // p) + 4][n > p])\n", "import math\nN = int(input())\nmobile = [int(input()) for _ in range(5)]\nres = math.ceil(N / min(mobile)) + 4\nprint(res)\n", "import math\nN = int(input())\nmove = []\nfor i in range(5):\n\tmove.append(int(input()))\nmovemin = min(move)\nif movemin >= N:\n\tans = 5\nelse:\n\tans = math.ceil(N / movemin) + 4\nprint(ans)\n", "N = int(input())\ncapa = [int(input()) for _ in range(5)]\nfor i in range(5):\n\tif capa[i] == min(capa):\n\t\ttransmin = i\nif capa[transmin] >= N:\n\tprint(5)\nelif N % capa[transmin] == 0:\n\tprint(transmin + N // capa[transmin] + 4 - transmin)\nelse:\n\tprint(transmin + N // capa[transmin] + 1 + 4 - transmin)\n", "n = int(input())\na = [int(input()) for _ in range(5)]\na.sort()\nprint((n - 1) // a[0] + 5)\n", "import sys\nread = sys.stdin.read\nreadline = sys.stdin.readline\nreadlines = sys.stdin.readlines\nsys.setrecursionlimit(10 ** 9)\nINF = 1 << 60\nMOD = 1000000007\n\ndef main():\n\t(N, *A) = list(map(int, read().split()))\n\tans = 0\n\tfor i in range(5):\n\t\tres = (N + A[i] - 1) // A[i] + 4\n\t\tif ans < res:\n\t\t\tans = res\n\tprint(ans)\n\treturn\n\ndef __starting_point():\n\tmain()\n__starting_point()\n", "(N, A, B, C, D, E) = [int(input()) for _ in range(6)]\nans = -(-N // min(A, B, C, D, E)) + 4\nprint(ans)\n", "import math\nn = int(input())\na = int(input())\nb = int(input())\nc = int(input())\nd = int(input())\ne = int(input())\nmove = [a, b, c, d, e]\nf = min(a, b, c, d, e)\nf_index = move.index(f) + 1\nprint(math.ceil(n / f) + (5 - f_index) + f_index - 1)\n", "def main():\n\timport sys\n\tpin = sys.stdin.readline\n\tpout = sys.stdout.write\n\tperr = sys.stderr.write\n\tN = int(pin())\n\tA = int(pin())\n\tB = int(pin())\n\tC = int(pin())\n\tD = int(pin())\n\tE = int(pin())\n\tt = min(A, B, C, D, E)\n\tif N % t == 0:\n\t\tprint(N // t + 4)\n\telse:\n\t\tprint(N // t + 5)\n\treturn\nmain()\n", "N = int(input())\nhum = [int(input()) for _ in range(5)]\nprint((N + min(hum) - 1) // min(hum) + 4)\n", "N = int(input())\nlst = [int(input()) for _ in range(5)]\nprint(4 + -(-N // min(lst)))\n", "(n, *m) = map(int, open(0))\nprint(-(-n // min(m)) + 4)\n", "import sys\nfrom math import ceil\nn = int(input())\nm = 10 ** 18\nfor i in range(5):\n\tm = min(m, int(input()))\nprint(ceil(n / m) + 4)\n", "import math\nl = [int(input()) for i in range(6)]\nprint(math.ceil(l[0] / min(l) + 4))\n", "(n, *p) = map(int, open(0))\nprint((~-min(p) + n) // min(p) + 4)\n", "n = int(input())\nt = [int(input()) for i in range(5)]\nk = 0\nfor i in range(5):\n\tk = max(k, (n + t[i] - 1) // t[i])\nprint(k + 4)\n", "N = int(input())\np = [int(input()) for _ in range(5)]\nprint(-(-N // min(p)) + 4)\n", "N = int(input())\ntrafic = [int(input()) for i in range(5)]\nprint((N - 1) // min(trafic) + 5)\n", "N = int(input())\nL = [int(input()) for i in range(5)]\nprint((N - 1) // min(L) + 5)\n", "n = [int(input()) for i in range(6)]\nprint(5 + (n[0] - 1) // min(n[1:]))\n", "import math\nN = int(input())\np = [0] * 5\nbn = float('inf')\nfor i in range(5):\n\tp[i] = int(input())\n\tif bn > p[i]:\n\t\tbn = p[i]\nans = 0\nprint(math.ceil(N / bn) + (5 - 1))\n", "(n, a, b, c, d, e) = [int(input()) for i in range(6)]\nm = min(a, b, c, d, e)\nk = 0 - -n // m\nprint(k + 4)\n", "import math\nN = int(input())\nX = [int(input()), int(input()), int(input()), int(input()), int(input())]\nprint(math.ceil(N / min(X)) + 4)\n", "i = [int(input()) for _ in range(6)]\nm = min(i[1:])\nprint((i[0] - 1) // m + 5)\n", "N = int(input())\nL = [int(input()) for _ in range(5)]\nm = min(L)\nprint(4 + (N + m - 1) // m)\n", "N = int(input())\ndata = [int(input()) for _ in range(5)]\nprint(4 - -N // min(data))\n", "N = int(input())\ncost = [int(input()) for _ in range(5)]\ncost.sort()\nif N % cost[0] == 0:\n\tans = 4 + N // cost[0]\nelse:\n\tans = 4 + N // cost[0] + 1\nprint(ans)\n", "n = int(input())\np_lis = [int(input()) for _ in range(5)]\nprint(-(-n // min(p_lis)) + 4)\n", "def main():\n\tn = int(input())\n\tdata = [int(input()) for i in range(5)]\n\t(quo, rem) = divmod(n, min(data))\n\tquo = 5 + quo\n\tif rem:\n\t\tprint(quo)\n\telse:\n\t\tprint(quo - 1)\nmain()\n", "N = int(input())\nlis = [int(input()) for _ in range(5)]\nmini = min(lis)\ngroup = (N + mini - 1) // mini\nans = 5 + group - 1\nprint(ans)\n", "data = [int(input()) for i in range(6)]\nprint(-(-data[0] // min(data[1:])) + 4)\n", "(a, *b) = eval('int(input()),' * 6)\nprint(~-a // min(b) + 5)\n", "(n, a, b, c, d, e) = [int(input()) for i in range(6)]\nprint(-(-n // min(a, b, c, d, e)) + 4)\n", "import math\n(N, *C) = [int(input()) for i in range(6)]\nprint(math.ceil(N / min(C)) + 4)\n", "f = lambda : int(input())\nN = f()\nD = [0] * 5\nfor i in range(5):\n\tD[i] = f()\nm = min(D)\ng = -(-(N - m) // m)\nprint(5 + g)\n", "N = int(input())\nmove = []\nfor _ in range(5):\n\tmove.append(int(input()))\nmin_value = min(move)\ngroup_count = -(-N // min_value)\nprint(group_count - 1 + 5)\n", "n = int(input())\nx = float('inf')\nfor _ in range(5):\n\ta = int(input())\n\tx = min(x, a)\nprint((n - 1) // x + 5)\n", "N = int(input())\nA = [int(input()) for i in range(5)]\nB = [0] * 6\ncnt = 0\nP = [0] * 9\nB[0] = 10 ** 15\nfor m in range(9):\n\tfor i in range(5, 0, -1):\n\t\tB[i] += min(A[i - 1], B[i - 1])\n\t\tB[i - 1] -= min(A[i - 1], B[i - 1])\n\tP[m] = B[5]\n\tcnt += 1\nx = N // P[-1]\ny = N % P[-1]\nif y == 0:\n\tprint(5 * x + 4)\n\treturn\nfor j in range(7, 2, -1):\n\tif P[j] < y:\n\t\ttime = 5 * x + j + 2\n\t\tprint(time)\n\t\treturn\n", "n = int(input())\nfrom math import ceil\n(a, b, c, d, e) = [int(input()) for i in range(5)]\nprint(max(ceil(n / a), ceil(n / b), ceil(n / c), ceil(n / d), ceil(n / e)) + 4)\n", "(n, *a) = eval('int(input()),' * 6)\nprint(4 - -n // min(a))\n", "N = int(input())\nH = []\nfor i in range(5):\n\tH += [int(input())]\nprint(-(-N // min(H)) + 4)\n", "n = int(input())\ncapa = [int(input()) for _ in range(5)]\nmin_capa = min(capa)\nif min_capa >= n:\n\tprint(5)\nelif n % min_capa == 0:\n\tprint(5 + n // min_capa - 1)\nelse:\n\tprint(5 + n // min_capa)\n", "n = int(input())\nx = [int(input()) for _ in range(5)]\np = min(x)\nq = n // p\nif n % p == 0:\n\tprint(q + 4)\nelse:\n\tprint(q + 5)\n", "(N, *A) = [int(input()) for _ in range(6)]\nprint(4 + (N + min(A) - 1) // min(A))\n", "a = [int(input()) for _ in [0] * 6]\nprint(~-a[0] // min(a[1:]) + 5)\n", "(n, *l) = (int(input()) for _ in range(6))\nprint((n - 1) // min(l) + 5)\n", "n = int(input())\nns = [int(input()) for _ in range(5)]\nprint((n - 1) // min(ns) + 5)\n"]

difficulty: EASY

name: AtCoder Beginner Contest 123 - Five Transportations

source: atcoder

time_limit: 2.0 seconds

memory_limit: 1024.0 megabytes

raw_problem:
配点: <var>300</var> 点

問題文

AtCoder 社は成長し、2028 年になってついに <var>6</var> つの都市 (都市 <var>1, 2, 3, 4, 5, 6</var>) からなる AtCoder 帝国を作りました！

AtCoder 帝国には <var>5</var> つの交通機関があります。

電車：都市 <var>1</var> から <var>2</var> まで <var>1</var> 分で移動する。<var>1</var> つの電車には <var>A</var> 人まで乗ることができる。

バス：都市 <var>2</var> から <var>3</var> まで <var>1</var> 分で移動する。<var>1</var> つのバスには <var>B</var> 人まで乗ることができる。

タクシー：都市 <var>3</var> から <var>4</var> まで <var>1</var> 分で移動する。<var>1</var> つのタクシーには <var>C</var> 人まで乗ることができる。

飛行機：都市 <var>4</var> から <var>5</var> まで <var>1</var> 分で移動する。<var>1</var> つの飛行機には <var>D</var> 人まで乗ることができる。

船：都市 <var>5</var> から <var>6</var> までを <var>1</var> 分で移動する。<var>1</var> つの船には <var>E</var> 人まで乗ることができる。

それぞれの交通機関は、各整数時刻 (<var>0, 1, 2, 3, ...</var>) に、都市から出発します。

いま、<var>N</var> 人のグループが都市 <var>1</var> におり、全員都市 <var>6</var> まで移動したいです。全員が都市 <var>6</var> に到着するまでに最短で何分かかるでしょうか？

なお、乗り継ぎにかかる時間を考える必要はありません。

制約

<var>1 \leq N, A, B, C, D, E \leq 10^{15}</var>

入力中の値はすべて整数である。

入力

入力は以下の形式で標準入力から与えられる。

<var>N</var>
<var>A</var>
<var>B</var>
<var>C</var>
<var>D</var>
<var>E</var>

出力

全員が都市 <var>6</var> に移動するのに必要な最小の時間を分単位で出力せよ。

入力例 1

5
3
2
4
3
5

出力例 1

7

例えば、次のような移動方法が考えられます。

はじめ、次の画像のように、<var>N = 5</var> 人が都市 <var>1</var> にいます。

<var>1</var> 分後までに、<var>3</var> 人が都市 <var>1</var> から都市 <var>2</var> に電車で移動します。ここで、電車は一度に <var>3</var> 人までしか運べないことに注意してください。

<var>2</var> 分後までに、残り <var>2</var> 人が都市 <var>1</var> から都市 <var>2</var> に電車で移動し、都市 <var>2</var> にいた <var>3</var> 人のうち <var>2</var> 人がバスで都市 <var>3</var> に移動します。ここで、バスは一度に <var>2</var> 人までしか運べないことに注意してください。

<var>3</var> 分後までに、<var>2</var> 人が都市 <var>2</var> から都市 <var>3</var> にバスで移動し、<var>2</var> 人が都市 <var>3</var> から都市 <var>4</var> にタクシーで移動します。

それ以降は、まだ都市 <var>6</var> に到着していない人が止まらずに移動し続けると、全員が <var>7</var> 分で都市 <var>6</var> に着くことができます。

また、<var>6</var> 分以内で全員が都市 <var>6</var> に着く方法はありません。

入力例 2

10
123
123
123
123
123

出力例 2

5

どの交通機関も <var>N = 10</var> 人を <var>1</var> 回で運ぶことができます。

したがって、全員が止まらずに移動し続ければ <var>5</var> 分で都市 <var>6</var> に着くことができます。

入力例 3

10000000007
2
3
5
7
11

出力例 3

5000000008

入力・出力が <var>32</var> ビット整数型に収まらない可能性があることに注意してください。

Score: <var>300</var> points

Problem Statement

In 2028 and after a continuous growth, AtCoder Inc. finally built an empire with six cities (City <var>1, 2, 3, 4, 5, 6</var>)!

There are five means of transport in this empire:

Train: travels from City <var>1</var> to <var>2</var> in one minute. A train can occupy at most <var>A</var> people.

Bus: travels from City <var>2</var> to <var>3</var> in one minute. A bus can occupy at most <var>B</var> people.

Taxi: travels from City <var>3</var> to <var>4</var> in one minute. A taxi can occupy at most <var>C</var> people.

Airplane: travels from City <var>4</var> to <var>5</var> in one minute. An airplane can occupy at most <var>D</var> people.

Ship: travels from City <var>5</var> to <var>6</var> in one minute. A ship can occupy at most <var>E</var> people.

For each of them, one vehicle leaves the city at each integer time (time <var>0</var>, <var>1</var>, <var>2</var>, <var>...</var>).

There is a group of <var>N</var> people at City <var>1</var>, and they all want to go to City <var>6</var>.

At least how long does it take for all of them to reach there?
You can ignore the time needed to transfer.

Constraints

<var>1 \leq N, A, B, C, D, E \leq 10^{15}</var>

All values in input are integers.

Input

Input is given from Standard Input in the following format:

<var>N</var>
<var>A</var>
<var>B</var>
<var>C</var>
<var>D</var>
<var>E</var>

Output

Print the minimum time required for all of the people to reach City <var>6</var>, in minutes.

Sample Input 1

5
3
2
4
3
5

Sample Output 1

7

One possible way to travel is as follows.
First, there are <var>N = 5</var> people at City <var>1</var>, as shown in the following image:

In the first minute, three people travels from City <var>1</var> to City <var>2</var> by train. Note that a train can only occupy at most three people.

In the second minute, the remaining two people travels from City <var>1</var> to City <var>2</var> by train, and two of the three people who were already at City <var>2</var> travels to City <var>3</var> by bus. Note that a bus can only occupy at most two people.

In the third minute, two people travels from City <var>2</var> to City <var>3</var> by train, and another two people travels from City <var>3</var> to City <var>4</var> by taxi.

From then on, if they continue traveling without stopping until they reach City <var>6</var>, all of them can reach there in seven minutes.

There is no way for them to reach City <var>6</var> in <var>6</var> minutes or less.

Sample Input 2

10
123
123
123
123
123

Sample Output 2

5

All kinds of vehicles can occupy <var>N = 10</var> people at a time.
Thus, if they continue traveling without stopping until they reach City <var>6</var>, all of them can reach there in five minutes.

Sample Input 3

10000000007
2
3
5
7
11

Sample Output 3

5000000008

Note that the input or output may not fit into a <var>32</var>-bit integer type.

question:
In 2028 and after a continuous growth, AtCoder Inc. finally built an empire with six cities (City $1, 2, 3, 4, 5, 6$)!
There are five means of transport in this empire:

- Train: travels from City $1$ to $2$ in one minute. A train can occupy at most $A$ people.
- Bus: travels from City $2$ to $3$ in one minute. A bus can occupy at most $B$ people.
- Taxi: travels from City $3$ to $4$ in one minute. A taxi can occupy at most $C$ people.
- Airplane: travels from City $4$ to $5$ in one minute. An airplane can occupy at most $D$ people.
- Ship: travels from City $5$ to $6$ in one minute. A ship can occupy at most $E$ people.

For each of them, one vehicle leaves the city at each integer time (time $0$, $1$, $2$, $...$).
There is a group of $N$ people at City $1$, and they all want to go to City $6$.
At least how long does it take for all of them to reach there?
You can ignore the time needed to transfer.

Constraints

- $1 \leq N, A, B, C, D, E \leq 10^{15}$
- All values in input are integers.

Input

Input is given from Standard Input in the following format:
$N$

$A$

$B$

$C$

$D$

$E$

Output

Print the minimum time required for all of the people to reach City $6$, in minutes.

Sample Input 1
5
3
2
4
3
5

Sample Output 1
7

One possible way to travel is as follows.
First, there are $N = 5$ people at City $1$, as shown in the following image:
![image](1.png)
In the first minute, three people travels from City $1$ to City $2$ by train. Note that a train can only occupy at most three people.
![image](2.png)
In the second minute, the remaining two people travels from City $1$ to City $2$ by train, and two of the three people who were already at City $2$ travels to City $3$ by bus. Note that a bus can only occupy at most two people.
![image](3.png)
In the third minute, two people travels from City $2$ to City $3$ by train, and another two people travels from City $3$ to City $4$ by taxi.
![image](4.png)
From then on, if they continue traveling without stopping until they reach City $6$, all of them can reach there in seven minutes.
There is no way for them to reach City $6$ in $6$ minutes or less.

Sample Input 2
10
123
123
123
123
123

Sample Output 2
5

All kinds of vehicles can occupy $N = 10$ people at a time.
Thus, if they continue traveling without stopping until they reach City $6$, all of them can reach there in five minutes.

Sample Input 3
10000000007
2
3
5
7
11

Sample Output 3
5000000008

Note that the input or output may not fit into a $32$-bit integer type.

image_tags: Others Others Others Others

data_split: test


E. Buds Re-hanging

problem_index: E

time_limit: 1 second

memory_limit: 256 megabytes

note:
In the first test case the tree looks as follows:
![image](images/cf_1566_E/1.png)
Firstly you can choose a bud vertex $$$4$$$ and re-hang it to vertex $$$3$$$. After that you can choose a bud vertex $$$2$$$ and re-hang it to vertex $$$7$$$. As a result, you will have the following tree with $$$2$$$ leaves:
![image](images/cf_1566_E/2.png)
It can be proved that it is the minimal number of leaves possible to get.
In the second test case the tree looks as follows:
![image](images/cf_1566_E/3.png)
You can choose a bud vertex $$$3$$$ and re-hang it to vertex $$$5$$$. As a result, you will have the following tree with $$$2$$$ leaves:
![image](images/cf_1566_E/4.png)
It can be proved that it is the minimal number of leaves possible to get.

solutions: ["def naiveSolve():\n\treturn\n\ndef solve():\n\treturn\n\ndef main():\n\tt = int(input())\n\tallans = []\n\tfor _ in range(t):\n\t\tn = int(input())\n\t\tadj = [[] for _ in range(n + 1)]\n\t\tfor __ in range(n - 1):\n\t\t\t(u, v) = readIntArr()\n\t\t\tadj[u].append(v)\n\t\t\tadj[v].append(u)\n\t\tpar = [-1 for __ in range(n + 1)]\n\t\tchildCnts = [0 for __ in range(n + 1)]\n\t\tdepth = [-1 for __ in range(n + 1)]\n\t\tdepth[1] = 0\n\t\tstack = [(1, -1)]\n\t\twhile stack:\n\t\t\t(node, p) = stack.pop()\n\t\t\tpar[node] = p\n\t\t\tfor nex in adj[node]:\n\t\t\t\tif nex != p:\n\t\t\t\t\tchildCnts[node] += 1\n\t\t\t\t\tstack.append((nex, node))\n\t\t\t\t\tdepth[nex] = depth[node] + 1\n\t\tnodeDepths = [(depth[node], node) for node in range(1, n + 1)]\n\t\tnodeDepths.sort(reverse=True)\n\t\tpruned = [False] * (n + 1)\n\t\tbudCnts = 0\n\t\tfor (depth, node) in nodeDepths:\n\t\t\tif depth >= 2 and pruned[node] == False and (pruned[par[node]] == False):\n\t\t\t\tbudCnts += 1\n\t\t\t\ttwoUp = par[par[node]]\n\t\t\t\tchildCnts[twoUp] -= 1\n\t\t\t\tpruned[par[node]] = True\n\t\tdirectLeaves = childCnts[1]\n\t\tbudContribution = n - 1 - directLeaves - budCnts * 2\n\t\tleavesWithoutBud = max(1, directLeaves)\n\t\tans = leavesWithoutBud + budContribution\n\t\tallans.append(ans)\n\tmultiLineArrayPrint(allans)\n\treturn\nimport sys\ninput = sys.stdin.buffer.readline\n\ndef oneLineArrayPrint(arr):\n\tprint(' '.join([str(x) for x in arr]))\n\ndef multiLineArrayPrint(arr):\n\tprint('\\n'.join([str(x) for x in arr]))\n\ndef multiLineArrayOfArraysPrint(arr):\n\tprint('\\n'.join([' '.join([str(x) for x in y]) for y in arr]))\n\ndef readIntArr():\n\treturn [int(x) for x in input().split()]\n\ndef makeArr(defaultValFactory, dimensionArr):\n\tdv = defaultValFactory\n\tda = dimensionArr\n\tif len(da) == 1:\n\t\treturn [dv() for _ in range(da[0])]\n\telse:\n\t\treturn [makeArr(dv, da[1:]) for _ in range(da[0])]\n\ndef queryInteractive(x):\n\tprint('{}'.format(x))\n\tsys.stdout.flush()\n\treturn int(input())\n\ndef answerInteractive(ans):\n\tprint('! {}'.format(ans))\n\tsys.stdout.flush()\ninf = float('inf')\nfrom math import gcd, floor, ceil\nfor _abc in range(1):\n\tmain()\n", "import sys\ninput = sys.stdin.readline\nfor i in range(int(input())):\n\tn = int(input())\n\tg = [[] for i in range(n + 1)]\n\tfor i in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tg[u].append(v)\n\t\tg[v].append(u)\n\ti = 0\n\tq = [1]\n\tp = [None] * (n + 1)\n\tw = [True] * (n + 1)\n\tr = 0\n\twhile i < len(q):\n\t\tx = q[i]\n\t\tP = p[x]\n\t\ti += 1\n\t\tfor v in g[x]:\n\t\t\tif v != P:\n\t\t\t\tq.append(v)\n\t\t\t\tp[v] = x\n\tfor i in range(len(q) - 1, 0, -1):\n\t\tx = q[i]\n\t\tP = p[x]\n\t\tc = len([1 for v in g[x] if v != P and w[v]])\n\t\tif c != 0:\n\t\t\tr += c - 1\n\t\t\tw[x] = False\n\tc = len([v for v in g[1] if w[v]])\n\tprint(r + 1) if c == 0 else print(r + c)\n", "from collections import deque\nimport sys\nimport io, os\ninput = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline\nsys.setrecursionlimit(200010)\n\ndef judgebuds(children, buds, seq):\n\tfor index in seq:\n\t\tif not children[index]:\n\t\t\tcontinue\n\t\tfor nextindex in children[index]:\n\t\t\tif not buds[nextindex]:\n\t\t\t\tbuds[index] = True\n\t\t\t\tbreak\n\ndef main(t):\n\tn = int(input())\n\tneigh = [[] for i in range(n)]\n\tfor i in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tneigh[u - 1].append(v - 1)\n\t\tneigh[v - 1].append(u - 1)\n\tchildren = [[] for i in range(n)]\n\tqueue = deque()\n\tqueue.append(0)\n\tvisited = [False] * n\n\tvisited[0] = True\n\tseq = []\n\twhile queue:\n\t\tindex = queue.popleft()\n\t\tseq.append(index)\n\t\tfor nextindex in neigh[index]:\n\t\t\tif visited[nextindex]:\n\t\t\t\tcontinue\n\t\t\tvisited[nextindex] = True\n\t\t\tchildren[index].append(nextindex)\n\t\t\tqueue.append(nextindex)\n\tseq = seq[::-1]\n\tbuds = [False] * n\n\tjudgebuds(children, buds, seq)\n\tans = n\n\tfor i in range(1, n):\n\t\tif buds[i]:\n\t\t\tans -= 2\n\tif buds[0]:\n\t\tans -= 1\n\tprint(ans)\nT = int(input())\nt = 1\nwhile t <= T:\n\tmain(t)\n\tt += 1\n", "import sys\nfrom collections import defaultdict\ninput = sys.stdin.readline\nM9 = 10 ** 9 + 7\n(yes, no) = ('YES', 'NO')\nMAXINT = sys.maxsize\nOFFLINE_TEST = False\n\ndef log(*args):\n\tif OFFLINE_TEST:\n\t\tprint('\\x1b[36m', *args, '\\x1b[0m', file=sys.stderr)\n\ndef solve(*args):\n\tif OFFLINE_TEST:\n\t\tlog('----- solving ------')\n\t\tlog(*args)\n\t\tlog('----- ------- ------')\n\treturn solve_(*args)\n\ndef read_matrix(rows):\n\treturn [list(map(int, input().split())) for _ in range(rows)]\n\ndef read_strings(rows):\n\treturn [input().strip() for _ in range(rows)]\n\ndef minus_one(arr):\n\treturn [x - 1 for x in arr]\n\ndef minus_one_matrix(mrr):\n\treturn [[x - 1 for x in row] for row in mrr]\nBUFSIZE = 8192\nimport os\nfrom io import BytesIO, IOBase\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')\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\tif stack:\n\t\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 solve_():\n\tk = int(input())\n\tmrr = read_matrix(k - 1)\n\tg = defaultdict(set)\n\tfor (a, b) in mrr:\n\t\tg[a].add(b)\n\t\tg[b].add(a)\n\tvisited = set()\n\n\t@bootstrap\n\tdef is_bud(cur):\n\t\ttotal_count_buds = 0\n\t\ttotal_children_not_a_bud = 0\n\t\tnum_children = 0\n\t\tnum_children_is_bud = 0\n\t\tfor nex in g[cur]:\n\t\t\tif nex in visited:\n\t\t\t\tcontinue\n\t\t\tvisited.add(nex)\n\t\t\t(child_is_bud, count_buds, children_not_a_bud) = (yield is_bud(nex))\n\t\t\tnum_children += 1\n\t\t\ttotal_count_buds += count_buds\n\t\t\ttotal_children_not_a_bud += children_not_a_bud\n\t\t\tif child_is_bud:\n\t\t\t\tnum_children_is_bud += 1\n\t\tif num_children == 0 or num_children == num_children_is_bud:\n\t\t\tyield (False, total_count_buds, total_children_not_a_bud + (num_children - num_children_is_bud))\n\t\tyield (True, total_count_buds + 1, total_children_not_a_bud + (num_children - num_children_is_bud))\n\tvisited.add(1)\n\t(_, total_count_buds, total_children_not_a_bud) = is_bud(1)\n\treturn total_children_not_a_bud - total_count_buds + 1\nfor case_num in range(int(input())):\n\tres = solve()\n\tprint(res)\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tadj = [[] for _ in range(n)]\n\tfor _ in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tadj[u - 1].append(v - 1)\n\t\tadj[v - 1].append(u - 1)\n\tleaf = 0\n\tbud = 0\n\tbelow = [0] * n\n\tstack = [0]\n\tvis = [False] * n\n\tvis[0] = True\n\tpar = [-1] * n\n\twhile stack:\n\t\tcur = stack[-1]\n\t\tif adj[cur]:\n\t\t\tnex = adj[cur].pop()\n\t\t\tif not vis[nex]:\n\t\t\t\tvis[nex] = True\n\t\t\t\tpar[nex] = cur\n\t\t\t\tstack.append(nex)\n\t\telse:\n\t\t\tif below[cur] == 0:\n\t\t\t\tleaf += 1\n\t\t\t\tif cur:\n\t\t\t\t\tbelow[par[cur]] += 1\n\t\t\telif cur:\n\t\t\t\tbud += 1\n\t\t\tstack.pop()\n\tprint(leaf - bud)\n", "import sys\nBUFSIZE = 8192\nimport os\nfrom io import BytesIO, IOBase\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 read_matrix(rows):\n\treturn [list(map(int, input().split())) for _ in range(rows)]\nall_res = []\ncases = []\nfor case_num in range(int(input())):\n\tk = int(input())\n\tmrr = read_matrix(k - 1)\n\tg = [[] for i in range(k + 2)]\n\tfor (a, b) in mrr:\n\t\tg[a].append(b)\n\t\tg[b].append(a)\n\tvisited = set()\n\ttotal_children_not_a_bud = 0\n\ttotal_count_buds = 0\n\thas_children = [False for _ in range(k + 2)]\n\thas_children_who_are_not_buds = [False for _ in range(k + 2)]\n\tstart = 1\n\tentered = set([start])\n\texiting = set()\n\tstack = [start]\n\tprevs = {start: 0}\n\twhile stack:\n\t\tcur = stack[-1]\n\t\tif cur in exiting:\n\t\t\tstack.pop()\n\t\t\tif cur in prevs:\n\t\t\t\tprev = prevs[cur]\n\t\t\t\tif has_children[cur] and has_children_who_are_not_buds[cur]:\n\t\t\t\t\ttotal_count_buds += 1\n\t\t\t\telse:\n\t\t\t\t\thas_children_who_are_not_buds[prev] = True\n\t\t\t\t\tif cur != 1:\n\t\t\t\t\t\ttotal_children_not_a_bud += 1\n\t\t\t\thas_children[prev] = True\n\t\t\tcontinue\n\t\tfor nex in g[cur]:\n\t\t\tif nex in entered:\n\t\t\t\tcontinue\n\t\t\tentered.add(nex)\n\t\t\tstack.append(nex)\n\t\t\tprevs[nex] = cur\n\t\texiting.add(cur)\n\tres = total_children_not_a_bud - total_count_buds + 1\n\tall_res.append(res)\nall_res = '\\n'.join((str(x) for x in all_res))\nprint(all_res)\n", "import sys\ninput = sys.stdin.readline\nfor _ in range(int(input())):\n\tn = int(input())\n\tedges = [[] for _ in range(n)]\n\tfor _ in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tedges[u - 1].append(v - 1)\n\t\tedges[v - 1].append(u - 1)\n\t(pare, fills, pendent, nivells) = ({0: None}, [set() for _ in range(n)], [0], [])\n\twhile pendent:\n\t\tnou_pendent = []\n\t\tfor p in pendent:\n\t\t\tfor f in edges[p]:\n\t\t\t\tif f != pare[p]:\n\t\t\t\t\tpare[f] = p\n\t\t\t\t\tfills[p].add(f)\n\t\t\t\t\tnou_pendent.append(f)\n\t\tpendent = nou_pendent\n\t\tnivells.append(pendent)\n\tbuds = []\n\tfor nivell in reversed(nivells):\n\t\tfor b in nivell:\n\t\t\tif len(fills[b]) > 0 and all((len(fills[f]) == 0 for f in fills[b])):\n\t\t\t\tbuds.append(len(fills[b]))\n\t\t\t\tp = pare[b]\n\t\t\t\tfills[p].remove(b)\n\tans = max(len(fills[0]), 1)\n\tfor b in buds:\n\t\tans += b - 1\n\tprint(ans)\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nfor _ in range(t):\n\tn = int(input())\n\tadj = [[] for _ in range(n)]\n\tparent = [0] * n\n\tifBuds = [False] * n\n\tvisited = [False] * n\n\tvisited[0] = True\n\tnumBuds = 0\n\tfor _ in range(n - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tadj[u - 1].append(v - 1)\n\t\tadj[v - 1].append(u - 1)\n\tstack = [0]\n\twhile stack:\n\t\tvertice = stack[-1]\n\t\tif adj[vertice]:\n\t\t\tnextVertice = adj[vertice].pop()\n\t\t\tif not visited[nextVertice]:\n\t\t\t\tvisited[nextVertice] = True\n\t\t\t\tparent[nextVertice] = vertice\n\t\t\t\tstack.append(nextVertice)\n\t\telse:\n\t\t\tif ifBuds[vertice]:\n\t\t\t\tif vertice:\n\t\t\t\t\tnumBuds += 1\n\t\t\telif vertice:\n\t\t\t\tifBuds[parent[vertice]] = True\n\t\t\tstack.pop()\n\tprint(n - 2 * numBuds - (1 if ifBuds[0] else 0))\n", "from sys import stdin, setrecursionlimit\ninput = stdin.readline\nsetrecursionlimit(3 * 10 ** 5)\nimport threading\ninp = lambda : list(map(int, input().split()))\n\ndef dfs(p, prev):\n\t(turn, count_buds, count_leaves) = (0, 0, 0)\n\tfor i in child[p]:\n\t\tif i == prev:\n\t\t\tcontinue\n\t\tx = dfs(i, p)\n\t\tturn = max(x[0], turn)\n\t\tcount_buds += x[1]\n\t\tcount_leaves += x[2]\n\tif turn == 1:\n\t\tcount_buds += 1\n\telse:\n\t\tcount_leaves += 1\n\treturn [turn ^ 1, count_buds, count_leaves]\n\ndef main():\n\tglobal child\n\tfor T in range(int(input())):\n\t\tn = int(input())\n\t\tchild = [[] for i in range(n + 1)]\n\t\tfor i in range(n - 1):\n\t\t\t(u, v) = inp()\n\t\t\tchild[u].append(v)\n\t\t\tchild[v].append(u)\n\t\t(turn, buds, leaves) = dfs(1, -1)\n\t\tif turn == 0:\n\t\t\tbuds -= 1\n\t\telse:\n\t\t\tleaves -= 1\n\t\tif turn == 0:\n\t\t\tans = leaves - buds\n\t\telse:\n\t\t\tans = leaves - buds + 1\n\t\tprint(ans)\nthreading.stack_size(10 ** 8)\nthreading.Thread(target=main).start()\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 solve():\n\tn = int(input())\n\tG = [[] for _ in range(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\tG[u].append(v)\n\t\tG[v].append(u)\n\tisBud = [False] * n\n\troot = 0\n\tvis = [False] * n\n\tstk = [(root, -1)]\n\twhile stk:\n\t\t(node, par) = stk[-1]\n\t\tif not vis[node]:\n\t\t\tvis[node] = True\n\t\t\tfor node0 in G[node]:\n\t\t\t\tif node0 != par:\n\t\t\t\t\tstk.append((node0, node))\n\t\telse:\n\t\t\tstk.pop()\n\t\t\tfor node0 in G[node]:\n\t\t\t\tif node0 != par and (not isBud[node0]):\n\t\t\t\t\tisBud[node] = True\n\tisBud[root] = False\n\tbuds = sum(isBud)\n\tfor node in G[root]:\n\t\tif not isBud[node]:\n\t\t\tprint(n - 2 * buds - 1)\n\t\t\treturn\n\tprint(n - 2 * buds)\n\treturn\nfor nt in range(int(input())):\n\tsolve()\n", "import sys\ninput = sys.stdin.readline\nfrom collections import deque\n\ndef is_buds(x):\n\tif x == 1:\n\t\treturn (False, None)\n\ttmp = [x]\n\tif not children[x]:\n\t\treturn (False, None)\n\tfor c in children[x]:\n\t\ttmp.append(c)\n\t\tif children[c]:\n\t\t\treturn (False, None)\n\treturn (True, tmp)\n(T,) = map(int, input().split())\nfor tt in range(T):\n\t(N,) = map(int, input().split())\n\tG = [[] for _ in range(N + 1)]\n\tfor _ in range(N - 1):\n\t\t(u, v) = map(int, input().split())\n\t\tG[u].append(v)\n\t\tG[v].append(u)\n\tvs = set([1])\n\tll = []\n\tqueue = deque([1])\n\tparents = [0] * (N + 1)\n\tchildren = [set() for _ in range(N + 1)]\n\tll.append(v)\n\twhile queue:\n\t\tv = queue.popleft()\n\t\tfor u in G[v]:\n\t\t\tif u in vs:\n\t\t\t\tcontinue\n\t\t\tparents[u] = v\n\t\t\tchildren[v].add(u)\n\t\t\tll.append(u)\n\t\t\tvs.add(u)\n\t\t\tqueue.append(u)\n\tRR = 0\n\tfll = [0] * (N + 1)\n\tfor i in range(1, N + 1):\n\t\tif not children[i]:\n\t\t\tRR += 1\n\t\t\tfll[i] = 1\n\tll = ll[::-1]\n\tvs = set()\n\tR = 0\n\tfor x in ll:\n\t\tif x in vs:\n\t\t\tcontinue\n\t\t(f, l) = is_buds(parents[x])\n\t\tif not f:\n\t\t\tcontinue\n\t\tfor u in l:\n\t\t\tvs.add(u)\n\t\tchildren[parents[parents[x]]].remove(parents[x])\n\t\tif children[parents[parents[x]]]:\n\t\t\tR += 1\n\tf = 1\n\tfor i in range(1, N + 1):\n\t\tif i not in vs and (not children[i]) and fll[i]:\n\t\t\tf = 0\n\tprint(RR - R)\n", "from os import write\nimport sys\ninput = sys.stdin.readline\n\ndef inp():\n\treturn int(input())\n\ndef input_list():\n\treturn list(map(int, input().split()))\n\ndef input_string():\n\ts = input()\n\treturn list(s[:len(s) - 1])\n\ndef input_int_gen():\n\treturn map(int, input().split())\nfrom collections import defaultdict, deque\ntests = inp()\nfor _ in range(tests):\n\tn = inp()\n\tchildren = [set() for _ in range(n + 1)]\n\tbud_dict = [0 for _ in range(n + 1)]\n\theights = [1 for _ in range(n + 1)]\n\tfor _ in range(n - 1):\n\t\t(a, b) = input_int_gen()\n\t\tchildren[a].add(b)\n\t\tchildren[b].add(a)\n\tbfs_queue = deque([(1, 1)])\n\twhile bfs_queue:\n\t\t(cur, grand) = bfs_queue.pop()\n\t\tchildren[cur].discard(grand)\n\t\tadjs = children[cur]\n\t\tbfs_queue.extendleft([(x, cur) for x in adjs])\n\n\tdef write_height(i):\n\t\tfor child in children[i]:\n\t\t\twrite_height(child)\n\t\t\tif heights[child] == 1:\n\t\t\t\theights[i] = 2\n\tstk = [(1, False)]\n\twhile stk:\n\t\t(cur, visited) = stk.pop()\n\t\tcs = children[cur]\n\t\tif not cs:\n\t\t\tcontinue\n\t\tif visited:\n\t\t\tif any((heights[x] == 1 for x in cs)):\n\t\t\t\theights[cur] = 2\n\t\telse:\n\t\t\tstk.append((cur, True))\n\t\t\tstk.extend(((x, False) for x in cs))\n\tn_buds = heights.count(2)\n\tn_leaves = heights.count(1) - 1\n\tif heights[1] == 2:\n\t\tn_buds -= 1\n\tprint(n_leaves - n_buds)\n", "import sys, math\nfrom collections import Counter, defaultdict, deque\ninput = sys.stdin.buffer.readline\nT = int(input())\nfor _ in range(T):\n\tn = int(input())\n\te = [[] for _ in range(n + 1)]\n\tfor _ in range(n - 1):\n\t\t(a, b) = map(int, input().split())\n\t\te[a].append(b)\n\t\te[b].append(a)\n\t(par, order) = ([0] * (n + 1), [])\n\tq = deque([1])\n\twhile q:\n\t\tu = q.popleft()\n\t\torder.append(u)\n\t\tfor v in e[u]:\n\t\t\tif par[u] == v:\n\t\t\t\tcontinue\n\t\t\tpar[v] = u\n\t\t\tq.append(v)\n\t(s, res) = (defaultdict(int), 0)\n\t(NORMAL, REMOVABLE, REMOVED) = (0, 1, 2)\n\tfor u in reversed(order):\n\t\t(stat, cc) = (REMOVABLE, 0)\n\t\tfor v in e[u]:\n\t\t\tif par[u] == v:\n\t\t\t\tcontinue\n\t\t\tif s[v] == NORMAL:\n\t\t\t\tstat = NORMAL\n\t\t\telif s[v] == REMOVABLE:\n\t\t\t\tcc += 1\n\t\tif stat == REMOVABLE and cc > 0:\n\t\t\tstat = REMOVED\n\t\ts[u] = stat\n\t\tif u == 1:\n\t\t\tres += cc + (stat == REMOVABLE)\n\t\telif stat == NORMAL:\n\t\t\tres += cc\n\t\telif stat == REMOVED:\n\t\t\tres += cc - 1\n\tprint(res)\n", "import sys\ninput = iter(sys.stdin.read().splitlines()).__next__\n\ndef root_tree(root, tree):\n\tparents = [None] * len(tree)\n\tstack = [root]\n\twhile stack:\n\t\tnode = stack.pop()\n\t\tfor child in tree[node]:\n\t\t\tparents[child] = node\n\t\t\ttree[child].remove(node)\n\t\t\tstack.append(child)\n\treturn parents\n\ndef solve():\n\tn = int(input())\n\tgraph = [set() for _ in range(n)]\n\tfor _ in range(n - 1):\n\t\t(u, v) = map(lambda x: int(x) - 1, input().split())\n\t\tgraph[u].add(v)\n\t\tgraph[v].add(u)\n\tparents = root_tree(0, graph)\n\tleaves = list(filter(lambda i: len(graph[i]) == 0, range(n)))\n\tnum_leaves = len(leaves)\n\tnum_leaf_children = [0] * n\n\tfor leaf in leaves:\n\t\tnum_leaf_children[parents[leaf]] += 1\n\tbuds = [node for node in range(1, n) if len(graph[node]) > 0 and len(graph[node]) == num_leaf_children[node]]\n\tnum_buds = 0\n\twhile buds:\n\t\tnum_buds += 1\n\t\tnode = buds.pop()\n\t\tparent = parents[node]\n\t\tgraph[parent].remove(node)\n\t\tif parent == 0:\n\t\t\tif len(graph[parent]) == 0:\n\t\t\t\tnum_leaves += 1\n\t\telif len(graph[parent]) == 0:\n\t\t\tgrandparent = parents[parent]\n\t\t\tnum_leaf_children[grandparent] += 1\n\t\t\tnum_leaves += 1\n\t\t\tif grandparent != 0 and num_leaf_children[grandparent] == len(graph[grandparent]):\n\t\t\t\tbuds.append(grandparent)\n\t\telif len(graph[parent]) == num_leaf_children[parent]:\n\t\t\tbuds.append(parent)\n\treturn num_leaves - num_buds\nt = int(input())\noutput = []\nfor _ in range(t):\n\toutput.append(solve())\nprint(*output, sep='\\n')\n", "def naiveSolve():\n\treturn\n\ndef solve():\n\treturn\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 main():\n\tt = int(input())\n\tallans = []\n\tfor _ in range(t):\n\t\tn = int(input())\n\t\tadj = [[] for _ in range(n + 1)]\n\t\tfor __ in range(n - 1):\n\t\t\t(u, v) = readIntArr()\n\t\t\tadj[u].append(v)\n\t\t\tadj[v].append(u)\n\t\tpruned = [False] * (n + 1)\n\t\tbudCnts = [0]\n\t\tchildCnts = [0] * (n + 1)\n\n\t\t@bootstrap\n\t\tdef dfs(node):\n\t\t\tfor nex in adj[node]:\n\t\t\t\tif not (len(path) >= 2 and nex == path[-2]):\n\t\t\t\t\tchildCnts[node] += 1\n\t\t\t\t\tpath.append(nex)\n\t\t\t\t\tyield dfs(nex)\n\t\t\t\t\tpath.pop()\n\t\t\tif len(path) >= 3 and pruned[node] == pruned[path[-2]] == False:\n\t\t\t\tbudCnts[0] += 1\n\t\t\t\tpruned[path[-2]] = True\n\t\t\t\tchildCnts[path[-3]] -= 1\n\t\t\tyield None\n\t\tpath = [1]\n\t\tdfs(1)\n\t\tbudCnts = budCnts[0]\n\t\tdirectLeaves = childCnts[1]\n\t\tbudContribution = n - 1 - directLeaves - budCnts * 2\n\t\tleavesWithoutBud = max(1, directLeaves)\n\t\tans = leavesWithoutBud + budContribution\n\t\tallans.append(ans)\n\tmultiLineArrayPrint(allans)\n\treturn\nimport sys\ninput = sys.stdin.buffer.readline\n\ndef oneLineArrayPrint(arr):\n\tprint(' '.join([str(x) for x in arr]))\n\ndef multiLineArrayPrint(arr):\n\tprint('\\n'.join([str(x) for x in arr]))\n\ndef multiLineArrayOfArraysPrint(arr):\n\tprint('\\n'.join([' '.join([str(x) for x in y]) for y in arr]))\n\ndef readIntArr():\n\treturn [int(x) for x in input().split()]\n\ndef makeArr(defaultValFactory, dimensionArr):\n\tdv = defaultValFactory\n\tda = dimensionArr\n\tif len(da) == 1:\n\t\treturn [dv() for _ in range(da[0])]\n\telse:\n\t\treturn [makeArr(dv, da[1:]) for _ in range(da[0])]\n\ndef queryInteractive(x):\n\tprint('{}'.format(x))\n\tsys.stdout.flush()\n\treturn int(input())\n\ndef answerInteractive(ans):\n\tprint('! {}'.format(ans))\n\tsys.stdout.flush()\ninf = float('inf')\nfrom math import gcd, floor, ceil\nfor _abc in range(1):\n\tmain()\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')\nfrom collections import defaultdict\nfrom math import ceil, floor, sqrt, log2, gcd, pi\nfrom heapq import heappush, heappop\nfrom bisect import bisect_left, bisect\nimport sys\nabc = 'abcdefghijklmnopqrstuvwxyz'\nABC = 'ABCDEFGHIJKLMNOPQRSTUVWXYZ'\nfor _ in range(int(input())):\n\tn = int(input())\n\tadj = [[] for _ in range(n)]\n\tfor _ in range(n - 1):\n\t\t(a, b) = map(int, input().split())\n\t\tadj[a - 1].append(b - 1)\n\t\tadj[b - 1].append(a - 1)\n\tbelow = [0] * n\n\tvis = [False] * n\n\tvis[0] = True\n\tstack = [0]\n\tpar = [-1] * n\n\tleaves = 0\n\tbuds = 0\n\twhile stack:\n\t\tcurr = stack[-1]\n\t\tif adj[curr]:\n\t\t\tval = adj[curr].pop()\n\t\t\tif not vis[val]:\n\t\t\t\tvis[val] = True\n\t\t\t\tpar[val] = curr\n\t\t\t\tstack.append(val)\n\t\telse:\n\t\t\tif below[curr] == 0:\n\t\t\t\tleaves += 1\n\t\t\t\tif curr:\n\t\t\t\t\tbelow[par[curr]] += 1\n\t\t\telif curr:\n\t\t\t\tbuds += 1\n\t\t\tstack.pop()\n\tprint(leaves - buds)\n", "def divisors(M):\n\td = []\n\ti = 1\n\twhile M >= i ** 2:\n\t\tif M % i == 0:\n\t\t\td.append(i)\n\t\t\tif i ** 2 != M:\n\t\t\t\td.append(M // i)\n\t\ti = i + 1\n\treturn d\n\ndef popcount(x):\n\tx = x - (x >> 1 & 1431655765)\n\tx = (x & 858993459) + (x >> 2 & 858993459)\n\tx = x + (x >> 4) & 252645135\n\tx = x + (x >> 8)\n\tx = x + (x >> 16)\n\treturn x & 127\n\ndef eratosthenes(n):\n\tres = [0 for i in range(n + 1)]\n\tprime = set([])\n\tfor i in range(2, n + 1):\n\t\tif not res[i]:\n\t\t\tprime.add(i)\n\t\t\tfor j in range(1, n // i + 1):\n\t\t\t\tres[i * j] = 1\n\treturn prime\n\ndef factorization(n):\n\tres = []\n\tfor p in prime:\n\t\tif n % p == 0:\n\t\t\twhile n % p == 0:\n\t\t\t\tn //= p\n\t\t\tres.append(p)\n\tif n != 1:\n\t\tres.append(n)\n\treturn res\n\ndef euler_phi(n):\n\tres = n\n\tfor x in range(2, n + 1):\n\t\tif x ** 2 > n:\n\t\t\tbreak\n\t\tif n % x == 0:\n\t\t\tres = res // x * (x - 1)\n\t\t\twhile n % x == 0:\n\t\t\t\tn //= x\n\tif n != 1:\n\t\tres = res // n * (n - 1)\n\treturn res\n\ndef ind(b, n):\n\tres = 0\n\twhile n % b == 0:\n\t\tres += 1\n\t\tn //= b\n\treturn res\n\ndef isPrimeMR(n):\n\td = n - 1\n\td = d // (d & -d)\n\tL = [2, 3, 5, 7, 11, 13, 17]\n\tfor a in L:\n\t\tt = d\n\t\ty = pow(a, t, n)\n\t\tif y == 1:\n\t\t\tcontinue\n\t\twhile y != n - 1:\n\t\t\ty = y * y % n\n\t\t\tif y == 1 or t == n - 1:\n\t\t\t\treturn 0\n\t\t\tt <<= 1\n\treturn 1\n\ndef findFactorRho(n):\n\tfrom math import gcd\n\tm = 1 << n.bit_length() // 8\n\tfor c in range(1, 99):\n\t\tf = lambda x: (x * x + c) % n\n\t\t(y, r, q, g) = (2, 1, 1, 1)\n\t\twhile g == 1:\n\t\t\tx = y\n\t\t\tfor i in range(r):\n\t\t\t\ty = f(y)\n\t\t\tk = 0\n\t\t\twhile k < r and g == 1:\n\t\t\t\tys = y\n\t\t\t\tfor i in range(min(m, r - k)):\n\t\t\t\t\ty = f(y)\n\t\t\t\t\tq = q * abs(x - y) % n\n\t\t\t\tg = gcd(q, n)\n\t\t\t\tk += m\n\t\t\tr <<= 1\n\t\tif g == n:\n\t\t\tg = 1\n\t\t\twhile g == 1:\n\t\t\t\tys = f(ys)\n\t\t\t\tg = gcd(abs(x - ys), n)\n\t\tif g < n:\n\t\t\tif isPrimeMR(g):\n\t\t\t\treturn g\n\t\t\telif isPrimeMR(n // g):\n\t\t\t\treturn n // g\n\t\t\treturn findFactorRho(g)\n\ndef primeFactor(n):\n\ti = 2\n\tret = {}\n\trhoFlg = 0\n\twhile i * i <= n:\n\t\tk = 0\n\t\twhile n % i == 0:\n\t\t\tn //= i\n\t\t\tk += 1\n\t\tif k:\n\t\t\tret[i] = k\n\t\ti += 1 + i % 2\n\t\tif i == 101 and n >= 2 ** 20:\n\t\t\twhile n > 1:\n\t\t\t\tif isPrimeMR(n):\n\t\t\t\t\t(ret[n], n) = (1, 1)\n\t\t\t\telse:\n\t\t\t\t\trhoFlg = 1\n\t\t\t\t\tj = findFactorRho(n)\n\t\t\t\t\tk = 0\n\t\t\t\t\twhile n % j == 0:\n\t\t\t\t\t\tn //= j\n\t\t\t\t\t\tk += 1\n\t\t\t\t\tret[j] = k\n\tif n > 1:\n\t\tret[n] = 1\n\tif rhoFlg:\n\t\tret = {x: ret[x] for x in sorted(ret)}\n\treturn ret\n\ndef divisors(n):\n\tres = [1]\n\tprime = primeFactor(n)\n\tfor p in prime:\n\t\tnewres = []\n\t\tfor d in res:\n\t\t\tfor j in range(prime[p] + 1):\n\t\t\t\tnewres.append(d * p ** j)\n\t\tres = newres\n\tres.sort()\n\treturn res\n\ndef xorfactorial(num):\n\tif num == 0:\n\t\treturn 0\n\telif num == 1:\n\t\treturn 1\n\telif num == 2:\n\t\treturn 3\n\telif num == 3:\n\t\treturn 0\n\telse:\n\t\tx = baseorder(num)\n\t\treturn 2 ** x * ((num - 2 ** x + 1) % 2) + function(num - 2 ** x)\n\ndef xorconv(n, X, Y):\n\tif n == 0:\n\t\tres = [X[0] * Y[0] % mod]\n\t\treturn res\n\tx = [X[i] + X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]\n\ty = [Y[i] + Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]\n\tz = [X[i] - X[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]\n\tw = [Y[i] - Y[i + 2 ** (n - 1)] for i in range(2 ** (n - 1))]\n\tres1 = xorconv(n - 1, x, y)\n\tres2 = xorconv(n - 1, z, w)\n\tformer = [(res1[i] + res2[i]) * inv for i in range(2 ** (n - 1))]\n\tlatter = [(res1[i] - res2[i]) * inv for i in range(2 ** (n - 1))]\n\tformer = list(map(lambda x: x % mod, former))\n\tlatter = list(map(lambda x: x % mod, latter))\n\treturn former + latter\n\ndef merge_sort(A, B):\n\t(pos_A, pos_B) = (0, 0)\n\t(n, m) = (len(A), len(B))\n\tres = []\n\twhile pos_A < n and pos_B < m:\n\t\t(a, b) = (A[pos_A], B[pos_B])\n\t\tif a < b:\n\t\t\tres.append(a)\n\t\t\tpos_A += 1\n\t\telse:\n\t\t\tres.append(b)\n\t\t\tpos_B += 1\n\tres += A[pos_A:]\n\tres += B[pos_B:]\n\treturn res\n\nclass UnionFindVerSize:\n\n\tdef __init__(self, N):\n\t\tself._parent = [n for n in range(0, N)]\n\t\tself._size = [1] * N\n\t\tself.group = N\n\n\tdef find_root(self, x):\n\t\tif self._parent[x] == x:\n\t\t\treturn x\n\t\tself._parent[x] = self.find_root(self._parent[x])\n\t\tstack = [x]\n\t\twhile self._parent[stack[-1]] != stack[-1]:\n\t\t\tstack.append(self._parent[stack[-1]])\n\t\tfor v in stack:\n\t\t\tself._parent[v] = stack[-1]\n\t\treturn self._parent[x]\n\n\tdef unite(self, x, y):\n\t\tgx = self.find_root(x)\n\t\tgy = self.find_root(y)\n\t\tif gx == gy:\n\t\t\treturn\n\t\tself.group -= 1\n\t\tif self._size[gx] < self._size[gy]:\n\t\t\tself._parent[gx] = gy\n\t\t\tself._size[gy] += self._size[gx]\n\t\telse:\n\t\t\tself._parent[gy] = gx\n\t\t\tself._size[gx] += self._size[gy]\n\n\tdef get_size(self, x):\n\t\treturn self._size[self.find_root(x)]\n\n\tdef is_same_group(self, x, y):\n\t\treturn self.find_root(x) == self.find_root(y)\n\nclass WeightedUnionFind:\n\n\tdef __init__(self, N):\n\t\tself.parent = [i for i in range(N)]\n\t\tself.size = [1 for i in range(N)]\n\t\tself.val = [0 for i in range(N)]\n\t\tself.flag = True\n\t\tself.edge = [[] for i in range(N)]\n\n\tdef dfs(self, v, pv):\n\t\tstack = [(v, pv)]\n\t\tnew_parent = self.parent[pv]\n\t\twhile stack:\n\t\t\t(v, pv) = stack.pop()\n\t\t\tself.parent[v] = new_parent\n\t\t\tfor (nv, w) in self.edge[v]:\n\t\t\t\tif nv != pv:\n\t\t\t\t\tself.val[nv] = self.val[v] + w\n\t\t\t\t\tstack.append((nv, v))\n\n\tdef unite(self, x, y, w):\n\t\tif not self.flag:\n\t\t\treturn\n\t\tif self.parent[x] == self.parent[y]:\n\t\t\tself.flag = self.val[x] - self.val[y] == w\n\t\t\treturn\n\t\tif self.size[self.parent[x]] > self.size[self.parent[y]]:\n\t\t\tself.edge[x].append((y, -w))\n\t\t\tself.edge[y].append((x, w))\n\t\t\tself.size[x] += self.size[y]\n\t\t\tself.val[y] = self.val[x] - w\n\t\t\tself.dfs(y, x)\n\t\telse:\n\t\t\tself.edge[x].append((y, -w))\n\t\t\tself.edge[y].append((x, w))\n\t\t\tself.size[y] += self.size[x]\n\t\t\tself.val[x] = self.val[y] + w\n\t\t\tself.dfs(x, y)\n\nclass Dijkstra:\n\n\tclass Edge:\n\n\t\tdef __init__(self, _to, _cost):\n\t\t\tself.to = _to\n\t\t\tself.cost = _cost\n\n\tdef __init__(self, V):\n\t\tself.G = [[] for i in range(V)]\n\t\tself._E = 0\n\t\tself._V = V\n\n\t@property\n\tdef E(self):\n\t\treturn self._E\n\n\t@property\n\tdef V(self):\n\t\treturn self._V\n\n\tdef add_edge(self, _from, _to, _cost):\n\t\tself.G[_from].append(self.Edge(_to, _cost))\n\t\tself._E += 1\n\n\tdef shortest_path(self, s):\n\t\timport heapq\n\t\tque = []\n\t\td = [10 ** 15] * self.V\n\t\td[s] = 0\n\t\theapq.heappush(que, (0, s))\n\t\twhile len(que) != 0:\n\t\t\t(cost, v) = heapq.heappop(que)\n\t\t\tif d[v] < cost:\n\t\t\t\tcontinue\n\t\t\tfor i in range(len(self.G[v])):\n\t\t\t\te = self.G[v][i]\n\t\t\t\tif d[e.to] > d[v] + e.cost:\n\t\t\t\t\td[e.to] = d[v] + e.cost\n\t\t\t\t\theapq.heappush(que, (d[e.to], e.to))\n\t\treturn d\n\ndef Z_algorithm(s):\n\tN = len(s)\n\tZ_alg = [0] * N\n\tZ_alg[0] = N\n\ti = 1\n\tj = 0\n\twhile i < N:\n\t\twhile i + j < N and s[j] == s[i + j]:\n\t\t\tj += 1\n\t\tZ_alg[i] = j\n\t\tif j == 0:\n\t\t\ti += 1\n\t\t\tcontinue\n\t\tk = 1\n\t\twhile i + k < N and k + Z_alg[k] < j:\n\t\t\tZ_alg[i + k] = Z_alg[k]\n\t\t\tk += 1\n\t\ti += k\n\t\tj -= k\n\treturn Z_alg\n\nclass BIT:\n\n\tdef __init__(self, n, mod=0):\n\t\tself.BIT = [0] * (n + 1)\n\t\tself.num = n\n\t\tself.mod = mod\n\n\tdef query(self, idx):\n\t\tres_sum = 0\n\t\tmod = self.mod\n\t\twhile idx > 0:\n\t\t\tres_sum += self.BIT[idx]\n\t\t\tif mod:\n\t\t\t\tres_sum %= mod\n\t\t\tidx -= idx & -idx\n\t\treturn res_sum\n\n\tdef update(self, idx, x):\n\t\tmod = self.mod\n\t\twhile idx <= self.num:\n\t\t\tself.BIT[idx] += x\n\t\t\tif mod:\n\t\t\t\tself.BIT[idx] %= mod\n\t\t\tidx += idx & -idx\n\t\treturn\n\nclass dancinglink:\n\n\tdef __init__(self, n, debug=False):\n\t\tself.n = n\n\t\tself.debug = debug\n\t\tself._left = [i - 1 for i in range(n)]\n\t\tself._right = [i + 1 for i in range(n)]\n\t\tself.exist = [True for i in range(n)]\n\n\tdef pop(self, k):\n\t\tif self.debug:\n\t\t\tassert self.exist[k]\n\t\tL = self._left[k]\n\t\tR = self._right[k]\n\t\tif L != -1:\n\t\t\tif R != self.n:\n\t\t\t\t(self._right[L], self._left[R]) = (R, L)\n\t\t\telse:\n\t\t\t\tself._right[L] = self.n\n\t\telif R != self.n:\n\t\t\tself._left[R] = -1\n\t\tself.exist[k] = False\n\n\tdef left(self, idx, k=1):\n\t\tif self.debug:\n\t\t\tassert self.exist[idx]\n\t\tres = idx\n\t\twhile k:\n\t\t\tres = self._left[res]\n\t\t\tif res == -1:\n\t\t\t\tbreak\n\t\t\tk -= 1\n\t\treturn res\n\n\tdef right(self, idx, k=1):\n\t\tif self.debug:\n\t\t\tassert self.exist[idx]\n\t\tres = idx\n\t\twhile k:\n\t\t\tres = self._right[res]\n\t\t\tif res == self.n:\n\t\t\t\tbreak\n\t\t\tk -= 1\n\t\treturn res\n\nclass SparseTable:\n\n\tdef __init__(self, A, merge_func, ide_ele):\n\t\tN = len(A)\n\t\tn = N.bit_length()\n\t\tself.table = [[ide_ele for i in range(n)] for i in range(N)]\n\t\tself.merge_func = merge_func\n\t\tfor i in range(N):\n\t\t\tself.table[i][0] = A[i]\n\t\tfor j in range(1, n):\n\t\t\tfor i in range(0, N - 2 ** j + 1):\n\t\t\t\tf = self.table[i][j - 1]\n\t\t\t\ts = self.table[i + 2 ** (j - 1)][j - 1]\n\t\t\t\tself.table[i][j] = self.merge_func(f, s)\n\n\tdef query(self, s, t):\n\t\tb = t - s + 1\n\t\tm = b.bit_length() - 1\n\t\treturn self.merge_func(self.table[s][m], self.table[t - 2 ** m + 1][m])\n\nclass BinaryTrie:\n\n\tclass node:\n\n\t\tdef __init__(self, val):\n\t\t\tself.left = None\n\t\t\tself.right = None\n\t\t\tself.max = val\n\n\tdef __init__(self):\n\t\tself.root = self.node(-10 ** 15)\n\n\tdef append(self, key, val):\n\t\tpos = self.root\n\t\tfor i in range(29, -1, -1):\n\t\t\tpos.max = max(pos.max, val)\n\t\t\tif key >> i & 1:\n\t\t\t\tif pos.right is None:\n\t\t\t\t\tpos.right = self.node(val)\n\t\t\t\t\tpos = pos.right\n\t\t\t\telse:\n\t\t\t\t\tpos = pos.right\n\t\t\telif pos.left is None:\n\t\t\t\tpos.left = self.node(val)\n\t\t\t\tpos = pos.left\n\t\t\telse:\n\t\t\t\tpos = pos.left\n\t\tpos.max = max(pos.max, val)\n\n\tdef search(self, M, xor):\n\t\tres = -10 ** 15\n\t\tpos = self.root\n\t\tfor i in range(29, -1, -1):\n\t\t\tif pos is None:\n\t\t\t\tbreak\n\t\t\tif M >> i & 1:\n\t\t\t\tif xor >> i & 1:\n\t\t\t\t\tif pos.right:\n\t\t\t\t\t\tres = max(res, pos.right.max)\n\t\t\t\t\tpos = pos.left\n\t\t\t\telse:\n\t\t\t\t\tif pos.left:\n\t\t\t\t\t\tres = max(res, pos.left.max)\n\t\t\t\t\tpos = pos.right\n\t\t\telif xor >> i & 1:\n\t\t\t\tpos = pos.right\n\t\t\telse:\n\t\t\t\tpos = pos.left\n\t\tif pos:\n\t\t\tres = max(res, pos.max)\n\t\treturn res\n\ndef solveequation(edge, ans, n, m):\n\tx = [0] * m\n\tused = [False] * n\n\tfor v in range(n):\n\t\tif used[v]:\n\t\t\tcontinue\n\t\ty = dfs(v)\n\t\tif y != 0:\n\t\t\treturn False\n\treturn x\n\n\tdef dfs(v):\n\t\tused[v] = True\n\t\tr = ans[v]\n\t\tfor (to, dire, id) in edge[v]:\n\t\t\tif used[to]:\n\t\t\t\tcontinue\n\t\t\ty = dfs(to)\n\t\t\tif dire == -1:\n\t\t\t\tx[id] = y\n\t\t\telse:\n\t\t\t\tx[id] = -y\n\t\t\tr += y\n\t\treturn r\n\nclass SegmentTree:\n\n\tdef __init__(self, init_val, segfunc, ide_ele):\n\t\tn = len(init_val)\n\t\tself.segfunc = segfunc\n\t\tself.ide_ele = ide_ele\n\t\tself.num = 1 << (n - 1).bit_length()\n\t\tself.tree = [ide_ele] * 2 * self.num\n\t\tself.size = n\n\t\tfor i in range(n):\n\t\t\tself.tree[self.num + i] = init_val[i]\n\t\tfor i in range(self.num - 1, 0, -1):\n\t\t\tself.tree[i] = self.segfunc(self.tree[2 * i], self.tree[2 * i + 1])\n\n\tdef update(self, k, x):\n\t\tk += self.num\n\t\tself.tree[k] = x\n\t\twhile k > 1:\n\t\t\tself.tree[k >> 1] = self.segfunc(self.tree[k], self.tree[k ^ 1])\n\t\t\tk >>= 1\n\n\tdef query(self, l, r):\n\t\tif r == self.size:\n\t\t\tr = self.num\n\t\tres = self.ide_ele\n\t\tl += self.num\n\t\tr += self.num\n\t\twhile l < r:\n\t\t\tif l & 1:\n\t\t\t\tres = self.segfunc(res, self.tree[l])\n\t\t\t\tl += 1\n\t\t\tif r & 1:\n\t\t\t\tres = self.segfunc(res, self.tree[r - 1])\n\t\t\tl >>= 1\n\t\t\tr >>= 1\n\t\treturn res\n\n\tdef bisect_l(self, l, r, x):\n\t\tl += self.num\n\t\tr += self.num\n\t\tLmin = -1\n\t\tRmin = -1\n\t\twhile l < r:\n\t\t\tif l & 1:\n\t\t\t\tif self.tree[l] <= x and Lmin == -1:\n\t\t\t\t\tLmin = l\n\t\t\t\tl += 1\n\t\t\tif r & 1:\n\t\t\t\tif self.tree[r - 1] <= x:\n\t\t\t\t\tRmin = r - 1\n\t\t\tl >>= 1\n\t\t\tr >>= 1\n\t\tif Lmin != -1:\n\t\t\tpos = Lmin\n\t\t\twhile pos < self.num:\n\t\t\t\tif self.tree[2 * pos] <= x:\n\t\t\t\t\tpos = 2 * pos\n\t\t\t\telse:\n\t\t\t\t\tpos = 2 * pos + 1\n\t\t\treturn pos - self.num\n\t\telif Rmin != -1:\n\t\t\tpos = Rmin\n\t\t\twhile pos < self.num:\n\t\t\t\tif self.tree[2 * pos] <= x:\n\t\t\t\t\tpos = 2 * pos\n\t\t\t\telse:\n\t\t\t\t\tpos = 2 * pos + 1\n\t\t\treturn pos - self.num\n\t\telse:\n\t\t\treturn -1\nimport sys, random, bisect\nfrom collections import deque, defaultdict\nfrom heapq import heapify, heappop, heappush\nfrom itertools import permutations\nfrom math import gcd, log\ninput = lambda : sys.stdin.buffer.readline()\nmi = lambda : map(int, input().split())\nli = lambda : list(mi())\nfor _ in range(int(input())):\n\tN = int(input())\n\tedge = [[] for i in range(N)]\n\tfor i in range(N - 1):\n\t\t(u, v) = mi()\n\t\tedge[u - 1].append(v - 1)\n\t\tedge[v - 1].append(u - 1)\n\tdeq = deque([0])\n\tparent = [-1 for v in range(N)]\n\ttopo = []\n\twhile deq:\n\t\tv = deq.popleft()\n\t\ttopo.append(v)\n\t\tfor nv in edge[v]:\n\t\t\tif nv != parent[v]:\n\t\t\t\tparent[nv] = v\n\t\t\t\tdeq.append(nv)\n\tleaf = [False for v in range(N)]\n\tbud_cnt = [0 for v in range(N)]\n\tres = 0\n\tfor v in topo[::-1]:\n\t\tif v != 0 and len(edge[v]) == 1:\n\t\t\tres += 1\n\t\t\tleaf[v] = True\n\t\t\tcontinue\n\t\tfor nv in edge[v]:\n\t\t\tif nv != parent[v]:\n\t\t\t\tbud_cnt[v] += bud_cnt[nv]\n\t\tif any((leaf[nv] and nv != parent[v] for nv in edge[v])):\n\t\t\tbud_cnt[v] += 1\n\t\telse:\n\t\t\tleaf[v] = True\n\t\t\tbud_cnt[v] -= 1\n\tminus = 0\n\tbud_cnt[0] = 0\n\tfor v in topo:\n\t\tif v != 0 and len(edge[v]) == 1:\n\t\t\tminus = max(minus, bud_cnt[v])\n\t\telse:\n\t\t\tS = sum((bud_cnt[nv] for nv in edge[v] if nv != parent[v]))\n\t\t\tfor nv in edge[v]:\n\t\t\t\tif nv != parent[v]:\n\t\t\t\t\tbud_cnt[nv] = bud_cnt[v] + S - bud_cnt[nv]\n\tprint(res - minus)\n", "import sys\ninput = sys.stdin.readline\nt = int(input())\nfor tests in range(t):\n\tn = int(input())\n\tE = [[] for i in range(n)]\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\tE[u].append(v)\n\t\tE[v].append(u)\n\tROOT = 0\n\tQUE = [ROOT]\n\tParent = [-1] * (n + 1)\n\tParent[ROOT] = n\n\tTOP_SORT = []\n\tChild = [[] for i in range(n)]\n\twhile QUE:\n\t\tx = QUE.pop()\n\t\tTOP_SORT.append(x)\n\t\tfor to in E[x]:\n\t\t\tif Parent[to] == -1:\n\t\t\t\tParent[to] = x\n\t\t\t\tChild[x].append(to)\n\t\t\t\tQUE.append(to)\n\tDEG = [0] * n\n\tL = [0] * n\n\tANS = []\n\tfor x in TOP_SORT[::-1]:\n\t\tif DEG[x] == len(Child[x]):\n\t\t\tL[x] = 1\n\t\t\tcontinue\n\t\tsc = 0\n\t\tfor ch in Child[x]:\n\t\t\tif L[ch] == 1:\n\t\t\t\tsc += 1\n\t\tif sc != 0:\n\t\t\tANS.append(sc)\n\t\tif x != 0 and Parent[x] != 0:\n\t\t\tDEG[Parent[x]] += 1\n\tLANS = ANS[0]\n\tfor i in range(1, len(ANS)):\n\t\tLANS += ANS[i] - 1\n\tprint(LANS)\n", "from __future__ import division, print_function\nimport os\nimport sys\nfrom io import BytesIO, IOBase\nif sys.version_info[0] < 3:\n\tfrom __builtin__ import xrange as range\n\tfrom future_builtins import ascii, filter, hex, map, oct, zip\n\ndef dfs(graph, start=0):\n\tn = len(graph)\n\tdp = [0] * n\n\t(visited, finished) = ([False] * n, [False] * n)\n\tstack = [start]\n\twhile stack:\n\t\tstart = stack[-1]\n\t\tif not visited[start]:\n\t\t\tvisited[start] = True\n\t\t\tfor child in graph[start]:\n\t\t\t\tif not visited[child]:\n\t\t\t\t\tstack.append(child)\n\t\telse:\n\t\t\tstack.pop()\n\t\t\tdp[start] += 1\n\t\t\tfor child in graph[start]:\n\t\t\t\tif finished[child]:\n\t\t\t\t\tdp[start] += dp[child]\n\t\t\tif dp[start] > 1:\n\t\t\t\tdp[start] = 0\n\t\t\tfinished[start] = True\n\treturn dp\n\ndef main():\n\tt = int(input())\n\tfor _ in range(t):\n\t\tn = int(input())\n\t\ttree = [[] for _ in range(n)]\n\t\tfor _ in range(n - 1):\n\t\t\t(u, v) = map(int, input().split())\n\t\t\ttree[u - 1].append(v - 1)\n\t\t\ttree[v - 1].append(u - 1)\n\t\tdp = dfs(tree)\n\t\tprint(sum([1 if i == 1 else -1 for i in dfs(tree)]) + (dp[0] == 0))\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\ndef print(*args, **kwargs):\n\t(sep, file) = (kwargs.pop('sep', ' '), kwargs.pop('file', sys.stdout))\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(kwargs.pop('end', '\\n'))\n\tif kwargs.pop('flush', False):\n\t\tfile.flush()\nif sys.version_info[0] < 3:\n\t(sys.stdin, sys.stdout) = (FastIO(sys.stdin), FastIO(sys.stdout))\nelse:\n\t(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))\ninput = lambda : sys.stdin.readline().rstrip('\\r\\n')\nmain()\n", "from collections import deque\n\ndef solve():\n\tn = int(input())\n\tg = [[] for i in range(n)]\n\tfor i in range(n - 1):\n\t\t(x, y) = map(int, input().split())\n\t\tx -= 1\n\t\ty -= 1\n\t\tg[x].append(y)\n\t\tg[y].append(x)\n\tv = [0] * n\n\tc = [set() for i in range(n)]\n\tp = [0 for i in range(n)]\n\tL = []\n\tqueue = deque()\n\tqueue.append(0)\n\twhile queue:\n\t\tx = queue.popleft()\n\t\tL.append(x)\n\t\tv[x] = 1\n\t\tfor y in g[x]:\n\t\t\tif v[y] == 0:\n\t\t\t\tp[y] = x\n\t\t\t\tc[x].add(y)\n\t\t\t\tqueue.append(y)\n\tL = L[::-1]\n\tL.pop()\n\tm = m2 = m3 = ans = 0\n\tfor x in L:\n\t\tif c[x]:\n\t\t\tm3 += 1\n\t\t\tm += len(c[x])\n\t\t\tc[p[x]].remove(x)\n\t\telif p[x] == 0:\n\t\t\tm2 += 1\n\tif m2:\n\t\treturn m2 + m - m3\n\treturn m + 1 - m3\nimport sys\ninput = lambda : sys.stdin.readline().rstrip()\nt = int(input())\nfor i in range(t):\n\tprint(solve())\n"]

difficulty: HARD

source: codeforces

raw_problem:
E. Buds Re-hanging

time limit per test
1 second

memory limit per test
256 megabytes

input
standard input

output
standard output

A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a vertex $$$v$$$ (different from root) is the previous to $$$v$$$ vertex on the shortest path from the root to the vertex $$$v$$$. Children of the vertex $$$v$$$ are all vertices for which $$$v$$$ is the parent.

A vertex is a leaf if it has no children. We call a vertex a bud, if the following three conditions are satisfied:

 it is not a root,

 it has at least one child, and

 all its children are leaves.

You are given a rooted tree with $$$n$$$ vertices. The vertex $$$1$$$ is the root. In one operation you can choose any bud with all its children (they are leaves) and re-hang them to any other vertex of the tree. By doing that you delete the edge connecting the bud and its parent and add an edge between the bud and the chosen vertex of the tree. The chosen vertex cannot be the bud itself or any of its children. All children of the bud stay connected to the bud.

What is the minimum number of leaves it is possible to get if you can make any number of the above-mentioned operations (possibly zero)?

Input

The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of the test cases follows.

The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of the vertices in the given tree.

Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) meaning that there is an edge between vertices $$$u$$$ and $$$v$$$ in the tree.

It is guaranteed that the given graph is a tree.

It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output

For each test case print a single integer — the minimal number of leaves that is possible to get after some operations.

Example

Input

5
7
1 2
1 3
1 4
2 5
2 6
4 7
6
1 2
1 3
2 4
2 5
3 6
2
1 2
7
7 3
1 5
1 3
4 6
4 7
2 1
6
2 1
2 3
4 5
3 4
3 6

Output

2
2
1
2
1

Note

In the first test case the tree looks as follows:

Firstly you can choose a bud vertex $$$4$$$ and re-hang it to vertex $$$3$$$. After that you can choose a bud vertex $$$2$$$ and re-hang it to vertex $$$7$$$. As a result, you will have the following tree with $$$2$$$ leaves:

It can be proved that it is the minimal number of leaves possible to get.

In the second test case the tree looks as follows:

You can choose a bud vertex $$$3$$$ and re-hang it to vertex $$$5$$$. As a result, you will have the following tree with $$$2$$$ leaves:

It can be proved that it is the minimal number of leaves possible to get.

question:
A tree is a connected graph without cycles. A rooted tree has a special vertex called the root. The parent of a vertex $$$v$$$ (different from root) is the previous to $$$v$$$ vertex on the shortest path from the root to the vertex $$$v$$$. Children of the vertex $$$v$$$ are all vertices for which $$$v$$$ is the parent.
A vertex is a leaf if it has no children. We call a vertex a bud, if the following three conditions are satisfied:
 -  it is not a root, -  it has at least one child, and -  all its children are leaves. You are given a rooted tree with $$$n$$$ vertices. The vertex $$$1$$$ is the root. In one operation you can choose any bud with all its children (they are leaves) and re-hang them to any other vertex of the tree. By doing that you delete the edge connecting the bud and its parent and add an edge between the bud and the chosen vertex of the tree. The chosen vertex cannot be the bud itself or any of its children. All children of the bud stay connected to the bud.
What is the minimum number of leaves it is possible to get if you can make any number of the above-mentioned operations (possibly zero)?

Input
The input consists of multiple test cases. The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — the number of test cases. Description of the test cases follows.
The first line of each test case contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of the vertices in the given tree.
Each of the next $$$n-1$$$ lines contains two integers $$$u$$$ and $$$v$$$ ($$$1 \le u, v \le n$$$, $$$u \neq v$$$) meaning that there is an edge between vertices $$$u$$$ and $$$v$$$ in the tree.
It is guaranteed that the given graph is a tree.
It is guaranteed that the sum of $$$n$$$ over all test cases doesn't exceed $$$2 \cdot 10^5$$$.

Output
For each test case print a single integer — the minimal number of leaves that is possible to get after some operations.

Example
Input
5
7
1 2
1 3
1 4
2 5
2 6
4 7
6
1 2
1 3
2 4
2 5
3 6
2
1 2
7
7 3
1 5
1 3
4 6
4 7
2 1
6
2 1
2 3
4 5
3 4
3 6

Output
2
2
1
2
1

Note
In the first test case the tree looks as follows:
 ![image](1.png) Firstly you can choose a bud vertex $$$4$$$ and re-hang it to vertex $$$3$$$. After that you can choose a bud vertex $$$2$$$ and re-hang it to vertex $$$7$$$. As a result, you will have the following tree with $$$2$$$ leaves:
 ![image](2.png) It can be proved that it is the minimal number of leaves possible to get.
In the second test case the tree looks as follows:
 ![image](3.png) You can choose a bud vertex $$$3$$$ and re-hang it to vertex $$$5$$$. As a result, you will have the following tree with $$$2$$$ leaves:
 ![image](4.png) It can be proved that it is the minimal number of leaves possible to get.

tags: ['Graph traversal', 'Constructive algorithms', 'Greedy algorithms', 'Tree algorithms', 'Dynamic programming']

skill_types: ['Dynamic programming', 'Greedy algorithms']

raw_tags: ['greedy', 'dfs and similar', 'dp', 'trees', 'constructive algorithms']

image_tags: Tree Tree Tree Tree

data_split: test


G. Ksyusha and Chinchilla

problem_index: G

time_limit: 3 seconds

memory_limit: 256 megabytes

note: ![image](images/cf_1833_G/2.png) The first testcase in first test.

solutions: ["def dfs(node, parent):\n    h = 1\n    for child in adj_list[node]:\n        if child != parent:\n            h += dfs(child, node)\n    if h == 3:\n        if parent:\n            cuts.add(edges[parent, node])\n        return 0\n    return h\n \nt = int(input())\nfor op in range(t):\n    n = int(input())\n    adj_list = [[] for i in range(n+1)]\n    edges = {}\n    for i in range(1, n):\n        u, v = map(int, input().split())\n        adj_list[u]+=[v]\n        adj_list[v]+=[u]\n        edges[u, v] = edges[v, u] = i\n    cuts = set()\n    if dfs(1, 0):\n        print(-1)\n    else:\n        print(len(cuts))\n        print(*cuts)", "t = int(input())\r\n\r\nwhile(t):\r\n    n = int(input())\r\n    from collections import defaultdict\r\n    graph = defaultdict(lambda:[])\r\n    for i in range(n-1):\r\n        a,b = map(int,input().split())\r\n        graph[a].append((b,i+1))\r\n        graph[b].append((a,i+1))\r\n    ans = []\r\n    global flag\r\n    flag= True\r\n    def trav(node,par):\r\n        global flag\r\n        count  = 1\r\n        for ele,index in graph[node]:\r\n            if ele!=par:\r\n                curr=trav(ele,node)\r\n                #print(curr,ele)\r\n                if curr == 0:\r\n                    ans.append(index)\r\n                \r\n                count+=curr \r\n                #print(count,\"ddd\")\r\n        #print(count,node)\r\n        if count>3:\r\n            flag = False\r\n        \r\n        return count%3\r\n    cans = trav(1,-1)\r\n    #print(cans)\r\n    if cans%3!=0:flag  = False\r\n    if not flag:\r\n        print(-1)\r\n    else:\r\n        print(len(ans))\r\n        print(*ans)\r\n    t-=1", "'''\r\nCF 1833G    \r\n                \r\n   /|\\            \r\n    | \\          \r\n    |             \r\n'''\r\n\r\nfrom types import GeneratorType\r\ndef bootstrap(f, stack=[]):\r\n    def wrappedfunc(*args, **kwargs):\r\n        if stack:\r\n            return f(*args, **kwargs)\r\n        else:\r\n            to = f(*args, **kwargs)\r\n            while True:\r\n                if type(to) is GeneratorType:\r\n                    stack.append(to)\r\n                    to = next(to)\r\n                else:\r\n                    stack.pop()\r\n                    if not stack:\r\n                        break\r\n                    to = stack[-1].send(to)\r\n            return to\r\n    return wrappedfunc\r\n\r\ndef main():\r\n\r\n    @bootstrap\r\n    def prune(u, par):\r\n        # return the length remainder\r\n        remainders = [0, 0, 0]  # remainders[length] = counts\r\n        for v, e in adj[u]:\r\n            if v != par:\r\n                l = (yield prune(v, u))\r\n                if l == -1:  # impossible\r\n                    yield -1\r\n                elif l == 3:  # prune\r\n                    pruned_edges.append(e)\r\n\r\n                else:  # 1 or 2\r\n                    remainders[l] += 1\r\n        # print(f'u={u} par={par} remainders={remainders}')\r\n        if remainders[1] == 2 and remainders[2] == 0:\r\n            # join 2 children with u. return 3 to force parent to prune the edge\r\n            yield 3\r\n        if remainders[1] == 1 and remainders[2] == 0:\r\n            yield 2\r\n        if remainders[1] == 0 and remainders[2] == 1:\r\n            yield 3\r\n        if remainders[1] == remainders[2] == 0:\r\n            yield 1\r\n        yield -1\r\n\r\n\r\n    t = int(input())\r\n    allans = []\r\n    for _ in range(t):\r\n        n = int(input())\r\n        adj = [[] for __ in range(n + 1)]\r\n\r\n        for e in range(1, n):\r\n            u, v = readIntArr()\r\n            adj[u].append((v, e))\r\n            adj[v].append((u, e))\r\n        \r\n        pruned_edges = []\r\n        if prune(1, -1) != 3:  # -1 or 1 or 2\r\n            allans.append([-1])\r\n        else:\r\n            allans.append([len(pruned_edges)])\r\n            allans.append(pruned_edges)\r\n    multiLineArrayOfArraysPrint(allans)\r\n\r\n    return\r\n\r\nimport sys\r\ninput=sys.stdin.buffer.readline #FOR READING PURE INTEGER INPUTS (space separation ok)\r\n# input=lambda: sys.stdin.readline().rstrip(\"\\r\\n\") #FOR READING STRING/TEXT INPUTS.\r\n \r\ndef oneLineArrayPrint(arr):\r\n    print(' '.join([str(x) for x in arr]))\r\ndef multiLineArrayPrint(arr):\r\n    print('\\n'.join([str(x) for x in arr]))\r\ndef multiLineArrayOfArraysPrint(arr):\r\n    print('\\n'.join([' '.join([str(x) for x in y]) for y in arr]))\r\n \r\ndef readIntArr():\r\n    return [int(x) for x in input().split()]\r\n# def readFloatArr():\r\n#     return [float(x) for x in input().split()]\r\n \r\ndef makeArr(defaultValFactory,dimensionArr): # eg. makeArr(lambda:0,[n,m])\r\n    dv=defaultValFactory;da=dimensionArr\r\n    if len(da)==1:return [dv() for _ in range(da[0])]\r\n    else:return [makeArr(dv,da[1:]) for _ in range(da[0])]\r\n \r\ndef queryInteractive(a, b):\r\n    print('? {} {}'.format(a, b))\r\n    sys.stdout.flush()\r\n    return int(input())\r\n \r\ndef answerInteractive(ans):\r\n    print('! {}'.format(ans))\r\n    sys.stdout.flush()\r\n \r\ninf=float('inf')\r\n# MOD=10**9+7\r\n# MOD=998244353\r\n \r\nfrom math import gcd,floor,ceil\r\nimport math\r\n# from math import floor,ceil # for Python2\r\n \r\nfor _abc in range(1):\r\n    main()", "def dfs(node, parent):\r\n    h = 1\r\n    for child in adj_list[node]:\r\n        if child != parent:\r\n            h += dfs(child, node)\r\n    if h == 3:\r\n        if parent:\r\n            cuts.add(edges[parent, node])\r\n        return 0\r\n    return h\r\n \r\nt = int(input())\r\nfor op in range(t):\r\n    n = int(input())\r\n    adj_list = [[] for i in range(n+1)]\r\n    edges = {}\r\n    for i in range(1, n):\r\n        u, v = map(int, input().split())\r\n        adj_list[u]+=[v]\r\n        adj_list[v]+=[u]\r\n        edges[u, v] = edges[v, u] = i\r\n    cuts = set()\r\n    if dfs(1, 0):\r\n        print(-1)\r\n    else:\r\n        print(len(cuts))\r\n        print(*cuts)", "from sys import stdin\r\n\r\ninput = lambda: stdin.readline().rstrip('\\r\\n')\r\n\r\nfor _ in range(int(input())):\r\n    n = int(input())\r\n    g = [[] for _ in range(n + 1)]\r\n\r\n    for i in range(1, n):\r\n        u, v = map(int, input().split())\r\n        g[u] += [(v, i)]\r\n        g[v] += [(u, i)]\r\n\r\n    ans = []\r\n\r\n\r\n    def dfs(u, p, i, ans):\r\n        nodes = 1\r\n        for v, j in g[u]:\r\n            if v == p: continue\r\n            nodes += dfs(v, u, j, ans)\r\n\r\n        if nodes == 3:\r\n            if i: ans += [i]\r\n            return 0\r\n\r\n        return nodes\r\n\r\n\r\n    if dfs(1, 0, 0, ans):\r\n        print(-1)\r\n    else:\r\n        print(len(ans))\r\n        print(*ans)"]

source: codeforces

raw_problem:
G. Ksyusha and Chinchilla

time limit per test
3 seconds

memory limit per test
256 megabytes

input
standard input

output
standard output

Ksyusha has a pet chinchilla, a tree on $$$n$$$ vertices and huge scissors. A tree is a connected graph without cycles. During a boring physics lesson Ksyusha thought about how to entertain her pet.

Chinchillas like to play with branches. A branch is a tree of $$$3$$$ vertices.
  The branch looks like this.
A cut is the removal of some (not yet cut) edge in the tree. Ksyusha has plenty of free time, so she can afford to make enough cuts so that the tree splits into branches. In other words, after several (possibly zero) cuts, each vertex must belong to exactly one branch.

Help Ksyusha choose the edges to be cut or tell that it is impossible.

Input

The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of testcases.

The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.

The next $$$n - 1$$$ rows of each testcase contain integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — the numbers of vertices that the $$$i$$$-th edge connects.

It is guaranteed that this set of edges forms a tree. It is also guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

Output

Print the answer for each testcase.

If the desired way to cut the tree does not exist, print $$$-1$$$.

Otherwise, print an integer $$$k$$$ — the number of edges to be cut. In the next line, print $$$k$$$ different integers $$$e_i$$$ ($$$1 \le e_i < n$$$) — numbers of the edges to be cut. If $$$k = 0$$$, print an empty string instead.

If there are several solutions, you can print any.

Examples

Input

4

9

1 2

4 3

7 9

5 4

4 6

3 2

8 7

1 7

6

1 2

1 3

4 3

1 5

6 1

6

1 2

3 2

3 4

4 5

6 5

5

1 3

5 3

5 2

3 4

Output

2
2 8
-1
1
3
-1

Input

4

2

1 2

3

1 2

3 1

6

1 2

3 1

3 4

3 5

6 1

9

2 6

6 9

9 1

9 7

1 8

7 3

8 5

4 7

Output

-1
0

1
2
2
4 3

Note
  The first testcase in first test.

question:
Ksyusha has a pet chinchilla, a tree on $$$n$$$ vertices and huge scissors. A tree is a connected graph without cycles. During a boring physics lesson Ksyusha thought about how to entertain her pet.
Chinchillas like to play with branches. A branch is a tree of $$$3$$$ vertices.
 ![image](1.png) The branch looks like this. A cut is the removal of some (not yet cut) edge in the tree. Ksyusha has plenty of free time, so she can afford to make enough cuts so that the tree splits into branches. In other words, after several (possibly zero) cuts, each vertex must belong to exactly one branch.
Help Ksyusha choose the edges to be cut or tell that it is impossible.

Input
The first line contains a single integer $$$t$$$ ($$$1 \le t \le 10^4$$$) — number of testcases.
The first line of each testcase contains a single integer $$$n$$$ ($$$2 \le n \le 2 \cdot 10^5$$$) — the number of vertices in the tree.
The next $$$n - 1$$$ rows of each testcase contain integers $$$v_i$$$ and $$$u_i$$$ ($$$1 \le v_i, u_i \le n$$$) — the numbers of vertices that the $$$i$$$-th edge connects.
It is guaranteed that this set of edges forms a tree. It is also guaranteed that the sum of $$$n$$$ over all testcases does not exceed $$$2 \cdot 10^5$$$.

Output
Print the answer for each testcase.
If the desired way to cut the tree does not exist, print $$$-1$$$.
Otherwise, print an integer $$$k$$$ — the number of edges to be cut. In the next line, print $$$k$$$ different integers $$$e_i$$$ ($$$1 \le e_i < n$$$) — numbers of the edges to be cut. If $$$k = 0$$$, print an empty string instead.
If there are several solutions, you can print any.

Examples
Input
4
9
1 2
4 3
7 9
5 4
4 6
3 2
8 7
1 7
6
1 2
1 3
4 3
1 5
6 1
6
1 2
3 2
3 4
4 5
6 5
5
1 3
5 3
5 2
3 4

Output
2
2 8
-1
1
3
-1

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

Output
-1
0

1
2
2
4 3

Note
 ![image](2.png) The first testcase in first test.

image_tags: Tree Tree

data_split: test