Read problems statements in Mandarin Chinese, Russian and Vietnamese as well. 

Sergey recently studied lock-free data structures. He particularly liked the data structure called Lock-Free Stack.
So, lock-free stack is basically an ordinary stack, which can be used by multiple threads of the same program. There are N threads, which do push and pop the numbers to this stack simultaneously.
In order to check his knowledge, Sergey implemented this data structure. But he was still unsure, whether his code works correct or not. So he made the test case of the following kind:

For every thread (say, the i^{th}), there is a list of A_{i} numbers, which will be pushed to the stack by this thread in this order (so, first, the first number from this list will be added, then the second one, and so on).

So Sergey runs the program, the numbers get pushed to the stack from all the threads simultaneously. When all the threads are done with it, he wanted to pop all the numbers from the stack and to check the correctness of the output.
But it appeared to be not so easy problem, because in general, there could be a few different correct sequences he could obtain, because the order in which the processes add the numbers is not strictly defined. Moreover, the processes can interrupt in between.
For example, even if he had only two threads and for each of them, there was a list of 1 unique number, then there can be two valid orders: either the first thread added its' number first, or it was the second one.
The another example could be the following: if there are also two thread, the first one having the list (1, 2) and the second one having the list (3, 4), then after doing all pops even the sequence (4, 2, 3, 1) is correct, because in this case:

First, the first thread added the first number 1 from its' list;
Then, the second thread added the first number 3 from its' list;
Then, the first thread added the second number 2 from its' list;
Then, the second thread added the second number 4 from its' list;

So since it is a LIFO (last in, first out) stack, after the pops we get the sequence (4, 2, 3, 1).

You are given the number of the threads and the list of integers to be added in order for each of the threads. You are also given a sequence. Determine, whether this sequence could be obtained after the process described above.

------ Input ------ 

The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.
The first line of each test case contains a single integer N denoting the number of threads.
Each of the following N lines contains the description of the numbers to be pushed in the following way: the first number in the list is A_{i}; the following numbers are the numbers B_{i, 1}, B_{i, 2}, ..., Bi, A_{i} denoting the numbers that will be added to the stack (in this order) by the i^{th} thread.
The last line on the test case contains A_{1}+A_{2}+...+A_{N} integer numbers, denoting the sequence Sergey got after he popped all the numbers from the stack.

------ Output ------ 

For each test case, output a single line containing Yes, if Sergey could have got this sequence of numbers and No otherwise.

------ Constraints ------ 

$1 ≤ T ≤ 15$
$1 ≤ A_{i}$
$1 ≤ B_{i, j} ≤ 1000$
$Let's denote P = (A_{1} + 1) × (A_{2} + 1) × ... × (A_{N} + 1)$
$1 ≤ sum of P ≤ 10^{6}$

------ Subtaks ------ 

$Subtask #1 (33 points): 1 ≤ sum of P ≤ 1000$
$Subtask #2 (11 points): N = 1$
$Subtask #3 (56 points): no additional constraints$

------ Example ------ 

Input:
2
2
2 1 2
2 3 4
4 3 2 1
2
2 1 2
2 3 4
4 1 2 3

Output:
Yes
No

------ Explanation ------ 

Example case 1. First, the integers of the first thread were added: 1, 2. Then, the integers of the second thread were added: 3, 4. So the sequence of the additions is 1, 2, 3, 4. Since it is a LIFO stack, when we pop, we get 4, 3, 2, 1. This way, the given sequence is reachable.
Example case 2. We need to get the following sequence of pushes to the stack: 3, 2, 1, 4. So, 2 should be added before 1. But only the first thread in the example can add these integers, and it will add 2 only after it has added 1. So, the given configuration is impossible to obtain.

Source: codechef | Difficulty: HARD
Tags: Dynamic programming

Complete search


Solutions:
for _ in range(int(input())):
	temp = int(input())
	global_list = []
	for __ in range(temp):
		(aa, *cache) = map(int, input().split())
		global_list.append(cache)
	memory = list(map(int, input().split()))
	ans = 'Yes'
	for i in global_list:
		for j in memory:
			if len(i) and i[-1] == j:
				del i[-1]
		if i != []:
			ans = 'No'
			break
	print(ans)


for _ in range(int(input())):
	N = int(input())
	global_list = []
	for __ in range(N):
		(aa, *cache) = map(int, input().split())
		global_list.append(cache)
	memory = list(map(int, input().split()))
	ans = 'Yes'
	for a in global_list:
		for b in memory:
			if len(a) and a[-1] == b:
				del a[-1]
		if a != []:
			ans = 'No'
			break
	print(ans)


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def check(thread, stak):
	if not stak:
		return True
	for th in thread:
		if th and th[-1] == stak[-1]:
			t = stack.pop()
			th.pop()
			if check(thread, stak):
				return True
			th.append(t)
			stak.append(t)
	return False
for _ in range(int(input())):
	threads = list()
	tn = int(input())
	for i in range(tn):
		line = list(map(int, input().split()))
		threads.append(line[1:][::-1])
	stack = list(map(int, input().split()))
	if check(threads, stack):
		print('Yes')
	else:
		print('No')


import heapq
for _ in range(int(input())):
	N = int(input())
	data = []
	for _ in range(N):
		data.append([int(num) for num in input().split()[1:]])
	sequence = [int(num) for num in input().split()]
	queue = [(len(sequence) - 1, [0] * N)]
	while len(queue):
		(cur_pos, cur_state) = heapq.heappop(queue)
		if cur_pos == 0:
			print('Yes')
			break
		for n in range(N):
			thread_idx = cur_state[n]
			if thread_idx == len(data[n]):
				continue
			if sequence[cur_pos] == data[n][thread_idx]:
				cur_state_copy = cur_state.copy()
				cur_state_copy[n] += 1
				heapq.heappush(queue, (cur_pos - 1, cur_state_copy))
	else:
		print('No')


import heapq
for _ in range(int(input())):
	threads_amount = int(input())
	data = []
	for _ in range(threads_amount):
		data.append([int(num) for num in input().split()[1:]])
	sequence = [int(num) for num in input().split()]
	queue = [(len(sequence) - 1, [0] * threads_amount)]
	while len(queue):
		(seq_idx, indices) = heapq.heappop(queue)
		if seq_idx == 0:
			print('Yes')
			break
		for thread_num in range(threads_amount):
			thread_idx = indices[thread_num]
			if thread_idx == len(data[thread_num]):
				continue
			if sequence[seq_idx] == data[thread_num][thread_idx]:
				indices_copy = indices.copy()
				indices_copy[thread_num] += 1
				heapq.heappush(queue, (seq_idx - 1, indices_copy))
	else:
		print('No')


from sys import setrecursionlimit
setrecursionlimit(10 ** 9)

def is_valid_stack(thread_lists, stack):
	if not stack:
		return True
	for thread_list in thread_lists:
		if thread_list and thread_list[-1] == stack[-1]:
			thread_list.pop()
			popped_ele = stack.pop()
			if is_valid_stack(thread_lists, stack):
				return True
			thread_list.append(popped_ele)
			stack.append(popped_ele)
	return False
for _ in range(int(input())):
	num_threads = int(input())
	thread_lists = []
	for i in range(num_threads):
		thread_lists.append(list(map(int, input().split()))[1:][::-1])
	stack = list(map(int, input().split()))
	print('Yes' if is_valid_stack(thread_lists, stack) else 'No')


import sys
import time
input_lines = [line.strip() for line in sys.stdin.readlines() if line.strip()]
C = int(input_lines[0])

def problem(threads, output):
	if len(output) == 0:
		if sum([len(t) for t in threads]) > 0:
			return 0
		else:
			return 1
	else:
		res = 0
		for tid in range(len(threads)):
			if len(threads[tid]) > 0 and threads[tid][-1] == output[0]:
				res += problem(threads[:tid] + [threads[tid][:-1]] + threads[tid + 1:], output[1:])
				if res > 0:
					break
		if res > 0:
			return 1
		else:
			return 0
t = 0
cid = 0
while cid < C:
	num_threads = int(input_lines[t + 1])
	step = num_threads + 2
	threads = []
	for line in input_lines[t + 2:t + 2 + num_threads]:
		threads.append(line.split()[1:])
	output = input_lines[t + 2 + num_threads].split()
	if num_threads == 1:
		if output[::-1] == threads[0]:
			print('Yes')
		else:
			print('No')
	else:
		res = problem(threads, output)
		if res > 0:
			print('Yes')
		else:
			print('No')
	t += step
	cid += 1


for _ in range(int(input())):
	n = int(input())
	s = []
	for i in range(n):
		s.append(list(map(int, input().split()[1:])))
	x = list(map(int, input().split()))
	ans = 'Yes'
	for a in s:
		for b in x:
			if len(a) and a[-1] == b:
				del a[-1]
		if a != []:
			ans = 'No'
			break
	print(ans)


def rec(f, l, n):
	if len(f) == 0:
		return True
	else:
		for i in range(n):
			if len(l[i]) > 0 and l[i][0] == f[0]:
				l[i] = l[i][1:]
				if rec(f[1:], l, n):
					return True
				else:
					l[i] = [f[0]] + l[i]
		return False
for i in range(int(input())):
	n = int(input())
	if n == 1:
		a = list(map(int, input().split()))[1:]
		f = list(map(int, input().split()))[::-1]
		if a == f:
			print('Yes')
		else:
			print('No')
	else:
		l = []
		for j in range(n):
			l.append(list(map(int, input().split()))[1:])
		f = list(map(int, input().split()))[::-1]
		if rec(f, l, n):
			print('Yes')
		else:
			print('No')


for _ in range(int(input())):
	threads = []
	for _ in range(int(input())):
		threads.append(list(map(int, input().split()))[1:])
	a = list(map(int, input().split()))
	ans = 'Yes'
	for thread in threads:
		for each in a:
			if thread and each == thread[-1]:
				del thread[-1]
		if thread:
			ans = 'No'
			break
	print(ans)


def isValidOutput(stack_list, input_result):
	if not input_result:
		return True
	for element in stack_list:
		if element[element[0]] == input_result[0]:
			element[0] -= 1
			result_op = input_result.pop(0)
			if isValidOutput(stack_list, input_result):
				return True
			else:
				element[0] += 1
				input_result.insert(0, result_op)
	return False

def main():
	T = int(input())
	for _ in range(T):
		num_stacks = int(input())
		stacks = []
		i = 0
		while i < num_stacks:
			stacks.append(list(map(int, input().split())))
			i += 1
		output_string = list(map(int, input().split()))
		if num_stacks == 1:
			stacks[0].reverse()
			stacks[0].pop()
			if stacks[0] == output_string:
				print('Yes')
			else:
				print('No')
			continue
		if isValidOutput(stacks, output_string):
			print('Yes')
		else:
			print('No')
main()


def abc(currstack, array):
	if len(array) == 0:
		return True
	for x in currstack:
		if x[0] == 0:
			continue
		elif x[x[0]] == array[0]:
			y = array.pop(0)
			x[0] -= 1
			if abc(currstack, array):
				return True
			else:
				array.insert(0, y)
				x[0] += 1
	return False
T = int(input())
for _ in range(T):
	N = int(input())
	stacks = []
	for x in range(N):
		stacks.append(list(map(int, input().split())))
	finalarray = list(map(int, input().split()))
	if N == 1:
		newstack = stacks[0]
		newstack.pop(0)
		newstack.reverse()
		if newstack == finalarray:
			print('Yes')
		else:
			print('No')
	elif abc(stacks, finalarray):
		print('Yes')
	else:
		print('No')


T = int(input())
while T > 0:
	lis = []
	for _ in range(int(input())):
		lis.append(list(map(int, input().split()))[1:])
	a = list(map(int, input().split()))
	ans = 'Yes'
	for thread in lis:
		for each in a:
			if len(thread) and each == thread[-1]:
				del thread[-1]
		if len(thread) != 0:
			ans = 'No'
			break
	print(ans)
	T = T - 1


def solve(stacks, arr, index, refs):
	if index >= len(arr):
		return True
	ans = False
	for (ind, l) in enumerate(stacks):
		if isinstance(l, list) and refs[ind] >= 0 and (arr[index] == l[refs[ind]]):
			refs[ind] -= 1
			ans = solve(stacks, arr, index + 1, refs)
			refs[ind] += 1
			if ans:
				return True
	return ans
from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 9)
for i in range(int(input())):
	threads = int(input())
	stacks = []
	refs = []
	for j in range(threads):
		temparr = list(map(int, input().strip().split()[1:]))
		refs.append(len(temparr) - 1)
		stacks.append(temparr)
	arrList = list(map(int, input().strip().split(' ')))
	print('Yes' if solve(stacks, arrList, 0, refs) else 'No')


for i in range(int(input())):
	threads = int(input())
	stacks = []
	for j in range(threads):
		stacks.append(list(map(int, input().strip().split()[1:])))
	arrList = list(map(int, input().strip().split(' ')))
	ans = 'Yes'
	for l in stacks:
		for x in arrList:
			if len(l) and x == l[-1]:
				del l[-1]
		if l != []:
			ans = 'No'
			break
	print(ans)


def rec_ans(ptrs, data, stp, st):
	if stp == -1:
		return True
	for i in range(len(ptrs)):
		if ptrs[i] < len(data[i]) and data[i][ptrs[i]] == st[stp]:
			ptrs[i] += 1
			if rec_ans(ptrs, data, stp - 1, st):
				return True
			ptrs[i] -= 1
	return False
from sys import stdin, setrecursionlimit
setrecursionlimit(10 ** 9)
for _ in range(int(input())):
	n = int(input())
	data = []
	ptrs = [1] * n
	for i in range(n):
		data.append(list(map(int, stdin.readline().strip().split())))
	st = list(map(int, stdin.readline().strip().split()))
	if rec_ans(ptrs, data, len(st) - 1, st):
		print('Yes')
	else:
		print('No')


t = int(input())
for l in range(t):
	n = int(input())
	stack = []
	for i in range(n):
		l = [int(i) for i in input().split()]
		stack.append(l)
	output = [int(i) for i in input().split()]
	l1 = [1] * n
	ok = []
	for i in range(1, len(output) + 1):
		for j in range(n):
			if l1[j] <= stack[j][0]:
				if output[-i] == stack[j][l1[j]]:
					ok.append(stack[j][l1[j]])
					l1[j] += 1
	if len(ok) == len(output):
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	b = []
	for _ in range(n):
		b.append(list(map(int, input().split()))[1:])
	a = list(map(int, input().split()))
	ans = 'Yes'
	for thread in b:
		for each in a:
			if len(thread) and each == thread[-1]:
				del thread[-1]
		if len(thread) != 0:
			ans = 'No'
			break
	print(ans)


import copy

def popper(a, b, n):
	if len(b) == 0:
		return 'Yes'
	for i in range(0, n):
		if len(a[i]) > 0 and a[i][0] == b[0]:
			a[i] = a[i][1:]
			if popper(a, b[1:], n) == 'Yes':
				return 'Yes'
			else:
				a[i] = [b[0]] + a[i]
	return 'No'
for t in range(int(input())):
	n = int(input())
	a = []
	for tmp in range(n):
		tmp1 = [int(num) for num in input().split(' ')]
		a.append(copy.deepcopy(tmp1)[1:])
	b = [int(op) for op in input().split(' ')]
	b = b[::-1]
	if n == 1:
		if a[0] == b:
			print('Yes')
		else:
			print('No')
	else:
		print(popper(a, b, n))


for _ in range(int(input())):
	n = int(input())
	b = [[*map(int, input().split())][1:] for _ in range(n)]
	s = [*map(int, input().split())]
	ans = 'Yes'
	for i in b:
		for j in s:
			if len(i) and j == i[-1]:
				del i[-1]
		if i != []:
			ans = 'No'
			break
	print(ans)


def check(a, b, n):
	if len(b) == 0:
		return 'Yes'
	for i in range(0, n):
		if len(a[i]) > 0 and a[i][0] == b[0]:
			a[i] = a[i][1:]
			if check(a, b[1:], n) == 'Yes':
				return 'Yes'
			else:
				a[i] = [b[0]] + a[i]
	return 'No'
t = int(input())
for ijk in range(0, t):
	n = int(input())
	a = []
	for i in range(0, n):
		a.append(list(map(int, input().strip().split()))[1:])
	b = list(map(int, input().strip().split()))[::-1]
	if n == 1:
		if a[0] == b:
			print('Yes')
		else:
			print('No')
	else:
		print(check(a, b, n))


def checkPossible(rev, k, n):
	if len(rev) == 0:
		return True
	else:
		for i in range(n):
			if len(k[i]) > 0 and k[i][0] == rev[0]:
				k[i] = k[i][1:]
				if checkPossible(rev[1:], k, n):
					return True
				else:
					k[i] = [rev[0]] + k[i]
		return False
for i in range(int(input())):
	n = int(input())
	if n == 1:
		a = list(map(int, input().split()))[1:]
		b = list(map(int, input().split()))[::-1]
		if a == b:
			print('Yes')
		else:
			print('No')
	else:
		k = []
		for j in range(n):
			k.append(list(map(int, input().split()))[1:])
		rev = list(map(int, input().split()))[::-1]
		if checkPossible(rev, k, n):
			print('Yes')
		else:
			print('No')


for _ in range(int(input())):
	n = int(input())
	threads = [None] * n
	for i in range(n):
		threads[i] = [int(o) for o in input().split()]
	stack = [int(p) for p in input().split()]
	size = [threads[i][0] for i in range(n)]
	for j in stack:
		for k in range(n):
			if size[k] != 0:
				if j == threads[k][size[k]]:
					size[k] -= 1
	print('Yes' if size.count(0) == n else 'No')


for i in range(int(input())):
	n = int(input())
	threads = []
	for i in range(n):
		threads.append(list(map(int, input().split())))
	stack = list(map(int, input().split()))
	size = []
	for s in range(len(threads)):
		size.append(threads[s][0])
	for j in stack:
		for k in range(n):
			if size[k] != 0:
				if j == threads[k][size[k]]:
					size[k] -= 1
	if size.count(0) == n:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	n = int(input())
	sz = list()
	ls = list()
	for i in range(n):
		ls.append(list(map(int, input().split())))
		sz.append(ls[i][0])
		ls[i].pop(0)
	q = list(map(int, input().split()))
	for i in q:
		for k in range(n):
			if sz[k] != 0:
				if ls[k][sz[k] - 1] == i:
					sz[k] -= 1
	flag = True
	for i in range(n):
		if sz[i] != 0:
			flag = False
			break
	print('Yes') if flag else print('No')


for i in range(int(input())):
	n = int(input())
	threads = []
	for i in range(n):
		threads.append(list(map(int, input().split())))
	seq = list(map(int, input().split()))
	state = []
	for e in range(len(threads)):
		state.append(threads[e][0])
	for j in seq:
		for k in range(n):
			if state[k] != 0:
				if j == threads[k][state[k]]:
					state[k] -= 1
	if state.count(0) == n:
		print('Yes')
	else:
		print('No')


for _ in range(int(input())):
	(n, total) = (int(input()), 0)
	ls = list()
	sz = list()
	for i in range(n):
		temp = list(map(int, input().split()))
		sz.append(temp[0])
		total += temp[0]
		temp.pop(0)
		ls.append(temp)
	q = list(map(int, input().split()))
	q.reverse()
	flag = True
	for i in range(n):
		(start, end) = (0, sz[i])
		for j in range(total):
			if start == end:
				break
			if q[j] == ls[i][start]:
				start += 1
		if start < end:
			flag = False
			break
	print('Yes') if flag else print('No')


t = int(input())
for _ in range(t):
	n = int(input())
	l1 = []
	for _ in range(n):
		l = list(map(int, input().split()))
		l.pop(0)
		l1.append(l)
	final_list = list(map(int, input().split()))
	final_list1 = final_list[::-1]
	ans = True
	for i in range(len(l1)):
		k = 0
		for j in range(len(final_list1)):
			if l1[i][k] == final_list1[j]:
				k += 1
				if k == len(l1[i]):
					break
		if k != len(l1[i]):
			ans = False
			break
	if ans:
		print('Yes')
	else:
		print('No')


def find_next(s, aa, l, c):
	e = 0
	for i in range(len(aa)):
		if len(aa[i]) > 0:
			e += 1
			break
	if e == 0 or l >= len(s):
		if c > len(s):
			return -1
		else:
			return c
	for i in range(len(aa)):
		if len(aa[i]) > 0 and l <= len(s) - 1 and (aa[i][-1] == s[l]):
			aaa = []
			for j in range(len(aa)):
				if j != i:
					aaa.append([k for k in aa[j]])
				elif len(aa[j]) > 0:
					aaa.append([k for k in aa[j][:-1]])
			c = find_next(s, aaa, l + 1, c + 1)
			if c == len(s):
				return c
			else:
				c -= 1
				continue
	return c
t = int(input())
for _ in range(t):
	n = int(input().split()[0])
	aa = []
	for i in range(n):
		a = input().split()
		j = int(a[0])
		aa.append([int(k) for k in a[1:]])
	s = [int(l) for l in input().split()]
	if n == 1:
		ss = ''.join((str(x) for x in s))
		bb = aa[0][::-1]
		sss = ''.join((str(x) for x in bb))
		if ss == sss:
			print('Yes')
		else:
			print('No')
	else:
		c = find_next(s, aa, 0, 0)
		if c == len(s):
			print('Yes')
		else:
			print('No')


t = int(input())

def check_if_correct(input_threads):
	for thread in input_threads:
		if len(thread) != 0:
			return False
	return True

def recursive_check_stack(input_lists, stack):
	if stack:
		item = stack[-1]
		stack = stack[:-1]
		exists = False
		res = False
		for i in range(len(input_lists)):
			if len(input_lists[i]) > 0 and input_lists[i][0] == item:
				exists = True
				input_lists[i] = input_lists[i][1:]
				res = recursive_check_stack(input_lists, stack)
				if res:
					return True
		if not exists and (not res):
			return False
		if len(stack) == 0:
			if check_if_correct(input_lists):
				return True
			else:
				return False
	return False
for _ in range(t):
	n = int(input())
	input_lists = []
	sum_nums = 0
	set1 = set()
	set2 = set()
	for _ in range(n):
		thread_numbers = list(map(int, input().split()))[1:]
		input_lists.append(thread_numbers)
		sum_nums += len(thread_numbers)
		for num in thread_numbers:
			set1.add(num)
	stack = list(map(int, input().split()))
	for num in stack:
		set2.add(num)
	if sum_nums != len(stack) and set1 != set2:
		print('No')
		continue
	result = True
	for i in range(len(input_lists)):
		k = 0
		stack1 = stack[::-1]
		for j in range(len(stack1)):
			if input_lists[i][k] == stack1[j]:
				k += 1
				if k == len(input_lists[i]):
					break
		if k != len(input_lists[i]):
			result = False
			break
	if result:
		print('Yes')
	else:
		print('No')


S = 0
N = 1
possibilities = 1
initial_states = []
threads = []
sequence = []

def hashing(lst):
	pass

def recursion(position, states):
	if position == S:
		for state in states:
			if state > 0:
				return False
		return True
	for idx in range(N):
		if states[idx] > 0 and threads[idx][states[idx] - 1] == sequence[position]:
			states[idx] -= 1
			if recursion(position + 1, states):
				states[idx] += 1
				return True
			states[idx] += 1
	return False
for _ in range(int(input().strip())):
	N = int(input().strip())
	threads = []
	initial_states = []
	S = 0
	possibilities = 1
	for idx in range(N):
		thread = list(map(int, input().strip().split()))
		S += thread[0]
		initial_states.append(thread[0])
		possibilities *= thread[0] + 1
		threads.append(thread[1:])
	sequence = list(map(int, input().strip().split()))
	if N == 1:
		print('Yes' if sequence == threads[0][::-1] else 'No')
	else:
		possible = recursion(0, initial_states)
		print('Yes' if possible else 'No')


def traverse(thr, seq, n):
	if len(seq) == 0:
		return True
	for i in range(n):
		if len(thr[i]) > 0 and thr[i][-1] == seq[0]:
			thr[i] = thr[i][:-1]
			if traverse(thr, seq[1:], n):
				return True
			else:
				thr[i].append(seq[0])
	return False
for t in range(int(input())):
	n = int(input())
	if n == 1:
		l = list(map(int, input().split()))
		l.pop(0)
		seq = list(map(int, input().split()))
		seq.reverse()
		if l == seq:
			print('Yes')
		else:
			print('No')
		continue
	thr = []
	for i in range(n):
		l = list(map(int, input().split()))
		l.pop(0)
		thr.append(l)
	seq = list(map(int, input().split()))
	if traverse(thr, seq, n):
		print('Yes')
	else:
		print('No')


import sys
sys.setrecursionlimit(1000)

def check(ind):
	if ind < 0:
		return True
	num = goal[ind]
	for ls in threads:
		if not ls:
			continue
		if ls[-1] == num:
			ls.pop()
			if mem.get(ind - 1):
				return True
			if check(ind - 1):
				mem[ind - 1] = True
				return True
			ls.append(num)
	return False

def check1():
	target = threads[0]
	target.reverse()
	ind = 0
	ans = 0
	for a in goal:
		for b in range(ind, len(target) - 1):
			if a == target[b]:
				ind = b
				ans += 1
				break
	if ans == len(goal):
		return True
	return False
t = int(input())
for q in range(t):
	mem = {}
	n = int(input())
	threads = []
	for q2 in range(n):
		threads.append([int(u) for u in input().strip().split()])
	goal = [int(u) for u in input().strip().split()]
	if n == 1:
		if check1():
			print('Yes')
		else:
			print('No')
		continue
	goal.reverse()
	if check(len(goal) - 1):
		print('Yes')
	else:
		print('No')


def test(N, data, res):
	cur = [len(data[i]) - 1 for i in range(N)]
	back = [-1] * len(res)
	curr = len(res) - 1
	while True:
		next = res[curr]
		notfound = True
		for i in range(back[curr] + 1, N):
			if cur[i] >= 0 and data[i][cur[i]] == next:
				back[curr] = i
				curr -= 1
				if curr < 0:
					return True
				cur[i] -= 1
				notfound = False
				break
		if notfound:
			back[curr] = -1
			curr += 1
			if curr >= len(res):
				return False
			else:
				cur[back[curr]] += 1
T = int(input())
for t in range(T):
	N = int(input())
	data = [list(map(int, input().split()))[1:] for i in range(N)]
	res = list(reversed(list(map(int, input().split()))))
	if test(N, data, res):
		print('Yes')
	else:
		print('No')


import sys
f = sys.stdin

def isOK(A, B, x):
	if not B:
		return True
	for (i, k) in enumerate(x):
		if A[i][k] != B[0]:
			continue
		x[i] = k + 1
		if isOK(A, B[1:], x):
			return True
		x[i] = k
	return False

def solve(A, B):
	A = [a[1:] + [-1] for a in A]
	if len(A) == 1:
		if all((a == b for (a, b) in zip(A[0], B))):
			return 'Yes'
		else:
			return 'No'
	if isOK(A, B, [0] * len(A)):
		return 'Yes'
	else:
		return 'No'
t = int(f.readline())
for j in range(t):
	n = int(f.readline())
	A = []
	for i in range(n):
		A += [list(map(int, f.readline().split()))]
	B = list(map(int, f.readline().split()))[::-1]
	print(solve(A, B))