Kingdom and its Cities (Codeforces 613D)
Tags: DP, divide and conquer

Meanwhile, the kingdom of K is getting ready for the marriage of the King's daughter. However, in order not to lose face in front of the relatives, the King should first finish reforms in his kingdom. As the King can not wait for his daughter's marriage, reforms must be finished as soon as possible.The kingdom currently consists of n cities. Cities are connected by n - 1 bidirectional road, such that one can get from any city to any other city. As the King had to save a lot, there is only one path between any two cities.What is the point of the reform? The key ministries of the state should be relocated to distinct cities (we call such cities important). However, due to the fact that there is a high risk of an attack by barbarians it must be done carefully. The King has made several plans, each of which is described by a set of important cities, and now wonders what is the best plan.Barbarians can capture some of the cities that are not important (the important ones will have enough protection for sure), after that the captured city becomes impassable. In particular, an interesting feature of the plan is the minimum number of cities that the barbarians need to capture in order to make all the important cities isolated, that is, from all important cities it would be impossible to reach any other important city.Help the King to calculate this characteristic for each of his plan.

Input: The first line of the input contains integer n (1 ≤ n ≤ 100 000) — the number of cities in the kingdom.Each of the next n - 1 lines contains two distinct integers ui, vi (1 ≤ ui, vi ≤ n) — the indices of the cities connected by the i-th road. It is guaranteed that you can get from any city to any other one moving only along the existing roads.The next line contains a single integer q (1 ≤ q ≤ 100 000) — the number of King's plans.Each of the next q lines looks as follows: first goes number ki — the number of important cities in the King's plan, (1 ≤ ki ≤ n), then follow exactly ki space-separated pairwise distinct numbers from 1 to n — the numbers of important cities in this plan.The sum of all ki's does't exceed 100 000.

Output: For each plan print a single integer — the minimum number of cities that the barbarians need to capture, or print  - 1 if all the barbarians' attempts to isolate important cities will not be effective.

Note: In the first sample, in the first and the third King's plan barbarians can capture the city 3, and that will be enough. In the second and the fourth plans all their attempts will not be effective.In the second sample the cities to capture are 3 and 5.

Sample Inputs:
4
1 3
2 3
4 3
4
2 1 2
3 2 3 4
3 1 2 4
4 1 2 3 4

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

Sample Outputs:
1
-1
1
-1

2

Solution (Python):
import sys
from collections import deque

def solve():
    sys.setrecursionlimit(10 ** 6)
    readline = sys.stdin.readline
    writelines = sys.stdout.writelines
    N = int(readline())
    G = [[] for i in range(N)]
    for i in range(N - 1):
        (u, v) = map(int, readline().split())
        G[u - 1].append(v - 1)
        G[v - 1].append(u - 1)
    S = []
    FS = [0] * N
    LS = [0] * N
    depth = [0] * N
    stk = [-1, 0]
    it = [0] * N
    while len(stk) > 1:
        v = stk[-1]
        i = it[v]
        if i == 0:
            FS[v] = len(S)
            depth[v] = len(stk)
        if i < len(G[v]) and G[v][i] == stk[-2]:
            it[v] += 1
            i += 1
        if i == len(G[v]):
            LS[v] = len(S)
            stk.pop()
        else:
            stk.append(G[v][i])
            it[v] += 1
        S.append(v)
    L = len(S)
    lg = [0] * (L + 1)
    for i in range(2, L + 1):
        lg[i] = lg[i >> 1] + 1
    st = [[L] * (L - (1 << i) + 1) for i in range(lg[L] + 1)]
    st[0][:] = S
    b = 1
    for i in range(lg[L]):
        st0 = st[i]
        st1 = st[i + 1]
        for j in range(L - (b << 1) + 1):
            st1[j] = st0[j] if depth[st0[j]] <= depth[st0[j + b]] else st0[j + b]
        b <<= 1
    INF = 10 ** 18
    ans = []
    Q = int(readline())
    G0 = [[]] * N
    P = [0] * N
    deg = [0] * N
    KS = [0] * N
    A = [0] * N
    B = [0] * N
    for t in range(Q):
        (k, *vs) = map(int, readline().split())
        for i in range(k):
            vs[i] -= 1
            KS[vs[i]] = 1
        vs.sort(key=FS.__getitem__)
        for i in range(k - 1):
            x = FS[vs[i]]
            y = FS[vs[i + 1]]
            l = lg[y - x + 1]
            w = st[l][x] if depth[st[l][x]] <= depth[st[l][y - (1 << l) + 1]] else st[l][y - (1 << l) + 1]
            vs.append(w)
        vs.sort(key=FS.__getitem__)
        stk = []
        prv = -1
        for v in vs:
            if v == prv:
                continue
            while stk and LS[stk[-1]] < FS[v]:
                stk.pop()
            if stk:
                G0[stk[-1]].append(v)
            G0[v] = []
            it[v] = 0
            stk.append(v)
            prv = v
        que = deque()
        prv = -1
        P[vs[0]] = -1
        for v in vs:
            if v == prv:
                continue
            for w in G0[v]:
                P[w] = v
            deg[v] = len(G0[v])
            if deg[v] == 0:
                que.append(v)
            prv = v
        while que:
            v = que.popleft()
            if KS[v]:
                a = 0
                for w in G0[v]:
                    ra = A[w]
                    rb = B[w]
                    if depth[v] + 1 < depth[w]:
                        a += min(ra, rb + 1)
                    else:
                        a += ra
                A[v] = INF
                B[v] = a
            else:
                a = 0
                b = c = INF
                for w in G0[v]:
                    ra = A[w]
                    rb = B[w]
                    (a, b, c) = (a + ra, min(a + rb, b + ra), min(b + rb, c + min(ra, rb)))
                A[v] = min(a, b + 1, c + 1)
                B[v] = b
            p = P[v]
            if p != -1:
                deg[p] -= 1
                if deg[p] == 0:
                    que.append(p)
        v = min(A[vs[0]], B[vs[0]])
        if v >= INF:
            ans.append('-1\n')
        else:
            ans.append('%d\n' % v)
        for v in vs:
            KS[v] = 0
    writelines(ans)
solve()

Solution (Python):
import sys
readline = sys.stdin.readline

class Segment_Tree:

    def __init__(self, N, f, e, lst=None, dynamic=False):
        self.f = f
        self.e = e
        self.N = N
        if dynamic:
            self.segment_tree = defaultdict(lambda : self.e)
        elif lst == None:
            self.segment_tree = [self.e] * 2 * self.N
        else:
            assert len(lst) <= self.N
            self.segment_tree = [self.e] * self.N + [x for x in lst] + [self.e] * (N - len(lst))
            for i in range(self.N - 1, 0, -1):
                self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def __getitem__(self, i):
        if type(i) == int:
            if -self.N <= i < 0:
                return self.segment_tree[i + self.N * 2]
            elif 0 <= i < self.N:
                return self.segment_tree[i + self.N]
            else:
                raise IndexError('list index out of range')
        else:
            (a, b, c) = (i.start, i.stop, i.step)
            if a == None:
                a = self.N
            else:
                a += self.N
            if b == None:
                b = self.N * 2
            else:
                b += self.N
            return self.segment_tree[slice(a, b, c)]

    def __setitem__(self, i, x):
        if -self.N <= i < 0:
            i += self.N * 2
        elif 0 <= i < self.N:
            i += self.N
        else:
            raise IndexError('list index out of range')
        self.segment_tree[i] = x
        while i > 1:
            i >>= 1
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Build(self, lst):
        for (i, x) in enumerate(lst, self.N):
            self.segment_tree[i] = x
        for i in range(self.N - 1, 0, -1):
            self.segment_tree[i] = self.f(self.segment_tree[i << 1], self.segment_tree[i << 1 | 1])

    def Fold(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        vL = self.e
        vR = self.e
        while L < R:
            if L & 1:
                vL = self.f(vL, self.segment_tree[L])
                L += 1
            if R & 1:
                R -= 1
                vR = self.f(self.segment_tree[R], vR)
            L >>= 1
            R >>= 1
        return self.f(vL, vR)

    def Fold_Index(self, L=None, R=None):
        if L == None:
            L = self.N
        else:
            L += self.N
        if R == None:
            R = self.N * 2
        else:
            R += self.N
        if L == R:
            return None
        x = self.Fold(L - self.N, R - self.N)
        while L < R:
            if L & 1:
                if self.segment_tree[L] == x:
                    i = L
                    break
                L += 1
            if R & 1:
                R -= 1
                if self.segment_tree[R] == x:
                    i = R
                    break
            L >>= 1
            R >>= 1
        while i < self.N:
            if self.segment_tree[i] == self.segment_tree[i << 1]:
                i <<= 1
            else:
                i <<= 1
                i |= 1
        i -= self.N
        return i

    def Bisect_Right(self, L=None, f=None):
        if L == self.N:
            return self.N
        if L == None:
            L = 0
        L += self.N
        vl = self.e
        vr = self.e
        (l, r) = (L, self.N * 2)
        while l < r:
            if l & 1:
                vl = self.f(vl, self.segment_tree[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.f(self.segment_tree[r], vr)
            l >>= 1
            r >>= 1
        if f(self.f(vl, vr)):
            return self.N
        v = self.e
        while True:
            while L % 2 == 0:
                L >>= 1
            vv = self.f(v, self.segment_tree[L])
            if f(vv):
                v = vv
                L += 1
            else:
                while L < self.N:
                    L <<= 1
                    vv = self.f(v, self.segment_tree[L])
                    if f(vv):
                        v = vv
                        L += 1
                return L - self.N

    def Bisect_Left(self, R=None, f=None):
        if R == 0:
            return 0
        if R == None:
            R = self.N
        R += self.N
        vl = self.e
        vr = self.e
        (l, r) = (self.N, R)
        while l < r:
            if l & 1:
                vl = self.f(vl, self.segment_tree[l])
                l += 1
            if r & 1:
                r -= 1
                vr = self.f(self.segment_tree[r], vr)
            l >>= 1
            r >>= 1
        if f(self.f(vl, vr)):
            return 0
        v = self.e
        while True:
            R -= 1
            while R > 1 and R % 2:
                R >>= 1
            vv = self.f(self.segment_tree[R], v)
            if f(vv):
                v = vv
            else:
                while R < self.N:
                    R = 2 * R + 1
                    vv = self.f(self.segment_tree[R], v)
                    if f(vv):
                        v = vv
                        R -= 1
                return R + 1 - self.N

    def __str__(self):
        return '[' + ', '.join(map(str, self.segment_tree[self.N:])) + ']'

class Graph:

    def __init__(self, V, edges=None, graph=None, directed=False, weighted=False, inf=float('inf')):
        self.V = V
        self.directed = directed
        self.weighted = weighted
        self.inf = inf
        if graph != None:
            self.graph = graph
            self.edges = []
            for i in range(self.V):
                if self.weighted:
                    for (j, d) in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j, d))
                else:
                    for j in self.graph[i]:
                        if self.directed or (not self.directed and i <= j):
                            self.edges.append((i, j))
        else:
            self.edges = edges
            self.graph = [[] for i in range(self.V)]
            if weighted:
                for (i, j, d) in self.edges:
                    self.graph[i].append((j, d))
                    if not self.directed:
                        self.graph[j].append((i, d))
            else:
                for (i, j) in self.edges:
                    self.graph[i].append(j)
                    if not self.directed:
                        self.graph[j].append(i)

    def SIV_DFS(self, s, bipartite_graph=False, cycle_detection=False, directed_acyclic=False, euler_tour=False, linked_components=False, lowlink=False, parents=False, postorder=False, preorder=False, subtree_size=False, topological_sort=False, unweighted_dist=False, weighted_dist=False):
        seen = [False] * self.V
        finished = [False] * self.V
        if directed_acyclic or cycle_detection or topological_sort:
            dag = True
        if euler_tour:
            et = []
        if linked_components:
            lc = []
        if lowlink:
            order = [None] * self.V
            ll = [None] * self.V
            idx = 0
        if parents or cycle_detection or lowlink or subtree_size:
            ps = [None] * self.V
        if postorder or topological_sort:
            post = []
        if preorder:
            pre = []
        if subtree_size:
            ss = [1] * self.V
        if unweighted_dist or bipartite_graph:
            uwd = [self.inf] * self.V
            uwd[s] = 0
        if weighted_dist:
            wd = [self.inf] * self.V
            wd[s] = 0
        stack = [(s, 0)] if self.weighted else [s]
        while stack:
            if self.weighted:
                (x, d) = stack.pop()
            else:
                x = stack.pop()
            if not seen[x]:
                seen[x] = True
                stack.append((x, d) if self.weighted else x)
                if euler_tour:
                    et.append(x)
                if linked_components:
                    lc.append(x)
                if lowlink:
                    order[x] = idx
                    ll[x] = idx
                    idx += 1
                if preorder:
                    pre.append(x)
                for y in self.graph[x]:
                    if self.weighted:
                        (y, d) = y
                    if not seen[y]:
                        stack.append((y, d) if self.weighted else y)
                        if parents or cycle_detection or lowlink or subtree_size:
                            ps[y] = x
                        if unweighted_dist or bipartite_graph:
                            uwd[y] = uwd[x] + 1
                        if weighted_dist:
                            wd[y] = wd[x] + d
                    elif not finished[y]:
                        if (directed_acyclic or cycle_detection or topological_sort) and dag:
                            dag = False
                            if cycle_detection:
                                cd = (y, x)
            elif not finished[x]:
                finished[x] = True
                if euler_tour:
                    et.append(~x)
                if lowlink:
                    bl = True
                    for y in self.graph[x]:
                        if self.weighted:
                            (y, d) = y
                        if ps[x] == y and bl:
                            bl = False
                            continue
                        ll[x] = min(ll[x], order[y])
                    if x != s:
                        ll[ps[x]] = min(ll[ps[x]], ll[x])
                if postorder or topological_sort:
                    post.append(x)
                if subtree_size:
                    for y in self.graph[x]:
                        if self.weighted:
                            (y, d) = y
                        if y == ps[x]:
                            continue
                        ss[x] += ss[y]
        if bipartite_graph:
            bg = [[], []]
            for tpl in self.edges:
                (x, y) = tpl[:2] if self.weighted else tpl
                if uwd[x] == self.inf or uwd[y] == self.inf:
                    continue
                if not uwd[x] % 2 ^ uwd[y] % 2:
                    bg = False
                    break
            else:
                for x in range(self.V):
                    if uwd[x] == self.inf:
                        continue
                    bg[uwd[x] % 2].append(x)
        retu = ()
        if bipartite_graph:
            retu += (bg,)
        if cycle_detection:
            if dag:
                cd = []
            else:
                (y, x) = cd
                cd = self.Route_Restoration(y, x, ps)
            retu += (cd,)
        if directed_acyclic:
            retu += (dag,)
        if euler_tour:
            retu += (et,)
        if linked_components:
            retu += (lc,)
        if lowlink:
            retu = (ll,)
        if parents:
            retu += (ps,)
        if postorder:
            retu += (post,)
        if preorder:
            retu += (pre,)
        if subtree_size:
            retu += (ss,)
        if topological_sort:
            if dag:
                tp_sort = post[::-1]
            else:
                tp_sort = []
            retu += (tp_sort,)
        if unweighted_dist:
            retu += (uwd,)
        if weighted_dist:
            retu += (wd,)
        if len(retu) == 1:
            retu = retu[0]
        return retu

    def Build_LCA(self, s, segment_tree=False):
        self.lca_segment_tree = segment_tree
        if self.lca_segment_tree:
            (self.lca_euler_tour, self.lca_parents, depth) = self.SIV_DFS(s, euler_tour=True, parents=True, unweighted_dist=True)
            self.lca_dfs_in_index = [None] * self.V
            self.lca_dfs_out_index = [None] * self.V
            for (i, x) in enumerate(self.lca_euler_tour):
                if x >= 0:
                    self.lca_dfs_in_index[x] = i
                else:
                    self.lca_dfs_out_index[~x] = i
            self.ST = Segment_Tree(2 * self.V, lambda x, y: min(x, y), self.V)
            lst = [None] * (2 * self.V)
            for i in range(2 * self.V - 1):
                if self.lca_euler_tour[i] >= 0:
                    lst[i] = depth[self.lca_euler_tour[i]]
                else:
                    lst[i] = depth[self.lca_parents[~self.lca_euler_tour[i]]]
            lst[2 * self.V - 1] = -1
            self.ST.Build(lst)
        else:
            (self.lca_parents, self.lca_depth) = self.SIV_DFS(s, parents=True, unweighted_dist=True)
            self.lca_PD = Path_Doubling(self.V, self.lca_parents)
            self.lca_PD.Build_Next(self.V)

    def LCA(self, a, b):
        if self.lca_segment_tree:
            m = min(self.lca_dfs_in_index[a], self.lca_dfs_in_index[b])
            M = max(self.lca_dfs_in_index[a], self.lca_dfs_in_index[b])
            x = self.lca_euler_tour[self.ST.Fold_Index(m, M + 1)]
            if x >= 0:
                lca = x
            else:
                lca = self.lca_parents[~x]
        else:
            if self.lca_depth[a] > self.lca_depth[b]:
                (a, b) = (b, a)
            b = self.lca_PD.Permutation_Doubling(b, self.lca_depth[b] - self.lca_depth[a])
            if a != b:
                for k in range(self.lca_PD.k - 1, -1, -1):
                    if self.lca_PD.permutation_doubling[k][a] != self.lca_PD.permutation_doubling[k][b]:
                        (a, b) = (self.lca_PD.permutation_doubling[k][a], self.lca_PD.permutation_doubling[k][b])
                (a, b) = (self.lca_PD.permutation_doubling[0][a], self.lca_PD.permutation_doubling[0][b])
            lca = a
        return lca

    def Build_Auxiliary_Tree(self, s):
        self.Build_LCA(s, segment_tree=True)
        self.auxiliary_tree_use = [False] * self.V

    def Auxiliary_Tree(self, points):
        points = sorted(points, key=lambda x: self.lca_dfs_in_index[x])
        for x in points:
            self.auxiliary_tree_use[x] = True
        le = len(points)
        for i in range(le - 1):
            lca = self.LCA(points[i], points[i + 1])
            if not self.auxiliary_tree_use[lca]:
                points.append(lca)
                self.auxiliary_tree_use[lca] = True
        points.sort(key=lambda x: self.lca_dfs_in_index[x])
        le = len(points)
        parents = [None] * le
        stack = []
        for i in range(le):
            while stack and self.lca_dfs_out_index[points[stack[-1]]] < self.lca_dfs_in_index[points[i]]:
                stack.pop()
            if stack:
                parents[i] = stack[-1]
            stack.append(i)
        for x in points:
            self.auxiliary_tree_use[x] = False
        return (parents, points)
N = int(readline())
edges = []
for n in range(N - 1):
    (u, v) = map(int, readline().split())
    u -= 1
    v -= 1
    edges.append((u, v))
inf = 1 << 30
G = Graph(N, edges=edges)
parents = G.SIV_DFS(0, parents=True)
G.Build_Auxiliary_Tree(0)
Q = int(readline())
use_points = [False] * N
for q in range(Q):
    (K, *points) = map(int, readline().split())
    for k in range(K):
        points[k] -= 1
        use_points[points[k]] = True
    for x in points:
        if parents[x] != None and use_points[parents[x]]:
            ans = -1
            break
    else:
        (P, decomp) = G.Auxiliary_Tree(points)
        le = len(P)
        E = [(i, P[i]) for i in range(1, le)]
        AT = Graph(le, edges=E)
        dp0 = [inf] * le
        dp1 = [inf] * le
        (AT_parents, tour) = AT.SIV_DFS(0, parents=True, postorder=True)
        for x in tour:
            child = [y for y in AT.graph[x] if y != AT_parents[x]]
            if use_points[decomp[x]]:
                dp1[x] = sum((dp0[y] for y in child))
                dp0[x] = dp1[x] + 1
            else:
                dp1[x] = sum((dp0[y] for y in child)) - max((dp0[y] - dp1[y] for y in child))
                dp0[x] = min(sum((dp0[y] for y in child)), dp1[x] + 1, sum((min(dp0[y], dp1[y]) for y in child)) + 1)
        ans = min(dp0[0], dp1[0])
    for x in points:
        use_points[x] = False
    print(ans)

Solution (Python):
from io import BytesIO, IOBase
import math
import random
import sys
import os
import bisect
import typing
from collections import Counter, defaultdict, deque
from copy import deepcopy
from functools import cmp_to_key, lru_cache, reduce
from heapq import heapify, heappop, heappush, heappushpop, nlargest, nsmallest
from itertools import accumulate, combinations, permutations, count
from operator import add, iand, ior, itemgetter, mul, xor
from string import ascii_lowercase, ascii_uppercase, ascii_letters
from typing import *
BUFSIZE = 4096

class FastIO(IOBase):
    newlines = 0

    def __init__(self, file):
        self._fd = file.fileno()
        self.buffer = BytesIO()
        self.writable = 'x' in file.mode or 'r' not in file.mode
        self.write = self.buffer.write if self.writable else None

    def read(self):
        while True:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            if not b:
                break
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines = 0
        return self.buffer.read()

    def readline(self):
        while self.newlines == 0:
            b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
            self.newlines = b.count(b'\n') + (not b)
            ptr = self.buffer.tell()
            (self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
        self.newlines -= 1
        return self.buffer.readline()

    def flush(self):
        if self.writable:
            os.write(self._fd, self.buffer.getvalue())
            (self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

    def __init__(self, file):
        self.buffer = FastIO(file)
        self.flush = self.buffer.flush
        self.writable = self.buffer.writable
        self.write = lambda s: self.buffer.write(s.encode('ascii'))
        self.read = lambda : self.buffer.read().decode('ascii')
        self.readline = lambda : self.buffer.readline().decode('ascii')
sys.stdin = IOWrapper(sys.stdin)
sys.stdout = IOWrapper(sys.stdout)
input = lambda : sys.stdin.readline().rstrip('\r\n')
if True:

    def I():
        return input()

    def II():
        return int(input())

    def MII():
        return map(int, input().split())

    def LI():
        return list(input().split())

    def LII():
        return list(map(int, input().split()))

    def GMI():
        return map(lambda x: int(x) - 1, input().split())

    def LGMI():
        return list(map(lambda x: int(x) - 1, input().split()))
inf = float('inf')

class LCA:

    def __init__(self, parent, depth, root):
        self.n = len(parent)
        self.root = root
        self.num = self.n.bit_length()
        self.depth = depth
        self.parent = [[-1] * self.n for i in range(self.num)]
        self.parent[0] = parent
        for k in range(self.num - 1):
            for v in range(self.n):
                if self.parent[k][v] == -1:
                    self.parent[k + 1][v] = -1
                else:
                    self.parent[k + 1][v] = self.parent[k][self.parent[k][v]]

    def getLCA(self, u, v):
        if self.depth[u] > self.depth[v]:
            (u, v) = (v, u)
        for k in range(self.num):
            if self.depth[v] - self.depth[u] >> k & 1:
                v = self.parent[k][v]
        if u == v:
            return u
        for k in reversed(range(self.num)):
            if self.parent[k][u] != self.parent[k][v]:
                u = self.parent[k][u]
                v = self.parent[k][v]
        return self.parent[0][u]

    def search(self, v, x):
        for k in reversed(range(self.num)):
            if x >> k & 1:
                v = self.parent[k][v]
        return v

    def getDepth(self, u):
        return self.depth[u]
n = II()
path = [[] for _ in range(n)]
for _ in range(n - 1):
    (u, v) = GMI()
    path[u].append(v)
    path[v].append(u)
t = 0
parent = [-1] * n
tmstamp = [-1] * n
stack = [0]
depth = [0] * n
while stack:
    u = stack.pop()
    tmstamp[u] = t
    t += 1
    for v in path[u]:
        if parent[u] != v:
            parent[v] = u
            depth[v] = depth[u] + 1
            stack.append(v)
lca = LCA(parent, depth, 0)
tmp_parent = [-1] * n
dp0 = [0] * n
dp1 = [0] * n
tot_son = [0] * n
max_val = [0] * n
notes = [0] * n
q = II()
for _ in range(q):
    (m, *nodes) = GMI()
    m += 1
    nodes.sort(key=lambda x: tmstamp[x])
    for node in nodes:
        tmp_parent[node] = -1
    dfs_order = nodes[:]
    for i in range(m - 1):
        (u, v) = (nodes[i], nodes[i + 1])
        l = lca.getLCA(u, v)
        dfs_order.append(l)
    dfs_order = sorted(set(dfs_order), key=lambda x: -tmstamp[x])
    k = len(dfs_order)
    for x in nodes:
        notes[x] = 1
        dp0[x] = 1
        dp1[x] = 0
    for i in range(k - 1):
        tmp_parent[dfs_order[i]] = lca.getLCA(dfs_order[i], dfs_order[i + 1])
    for i in range(k):
        u = dfs_order[i]
        if not notes[u]:
            dp0[u] = min(dp0[u], tot_son[u] + 1)
            dp1[u] = min(dp1[u] - max_val[u], tot_son[u] + 1)
        if i != k - 1:
            if notes[u] and notes[parent[u]]:
                print(-1)
                break
            p = tmp_parent[u]
            if notes[p]:
                dp0[p] += dp0[u]
                dp1[p] += dp0[u]
            else:
                dp0[p] += dp0[u]
                dp1[p] += dp0[u]
                tot_son[p] += dp1[u]
                max_val[p] = max(max_val[p], dp0[u] - dp1[u])
    else:
        print(dp1[dfs_order[k - 1]])
    for x in dfs_order:
        tmp_parent[x] = -1
        notes[x] = 0
        dp0[x] = dp1[x] = 0
        tot_son[x] = 0
        max_val[x] = 0