Ujan has a lot of numbers in his boxes. He likes order and balance, so he decided to reorder the numbers.

There are $k$ boxes numbered from $1$ to $k$. The $i$-th box contains $n_i$ integer numbers. The integers can be negative. All of the integers are distinct. 

Ujan is lazy, so he will do the following reordering of the numbers exactly once. He will pick a single integer from each of the boxes, $k$ integers in total. Then he will insert the chosen numbers — one integer in each of the boxes, so that the number of integers in each box is the same as in the beginning. Note that he may also insert an integer he picked from a box back into the same box.

Ujan will be happy if the sum of the integers in each box is the same. Can he achieve this and make the boxes perfectly balanced, like all things should be?


-----Input-----

The first line contains a single integer $k$ ($1 \leq k \leq 15$), the number of boxes. 

The $i$-th of the next $k$ lines first contains a single integer $n_i$ ($1 \leq n_i \leq 5\,000$), the number of integers in box $i$. Then the same line contains $n_i$ integers $a_{i,1}, \ldots, a_{i,n_i}$ ($|a_{i,j}| \leq 10^9$), the integers in the $i$-th box. 

It is guaranteed that all $a_{i,j}$ are distinct.


-----Output-----

If Ujan cannot achieve his goal, output "No" in a single line. Otherwise in the first line output "Yes", and then output $k$ lines. The $i$-th of these lines should contain two integers $c_i$ and $p_i$. This means that Ujan should pick the integer $c_i$ from the $i$-th box and place it in the $p_i$-th box afterwards.

If there are multiple solutions, output any of those.

You can print each letter in any case (upper or lower).


-----Examples-----
Input
4
3 1 7 4
2 3 2
2 8 5
1 10

Output
Yes
7 2
2 3
5 1
10 4

Input
2
2 3 -2
2 -1 5

Output
No

Input
2
2 -10 10
2 0 -20

Output
Yes
-10 2
-20 1



-----Note-----

In the first sample, Ujan can put the number $7$ in the $2$nd box, the number $2$ in the $3$rd box, the number $5$ in the $1$st box and keep the number $10$ in the same $4$th box. Then the boxes will contain numbers $\{1,5,4\}$, $\{3, 7\}$, $\{8,2\}$ and $\{10\}$. The sum in each box then is equal to $10$.

In the second sample, it is not possible to pick and redistribute the numbers in the required way.

In the third sample, one can swap the numbers $-20$ and $-10$, making the sum in each box equal to $-10$.

Source: codeforces | Difficulty: VERY_HARD
Tags: Dynamic programming

Bit manipulation

Graph algorithms

Graph traversal


Solutions:
import sys
reader = (s.rstrip() for s in sys.stdin)
input = reader.__next__
k = int(input())
d = {}
aa = []
sa = []
for i in range(k):
	(ni, *a) = map(int, input().split())
	for ai in a:
		d[ai] = i
	aa.append(a)
	sa.append(sum(a))
s = sum(sa)
if s % k != 0:
	print('No')
	exit()
s //= k

def calc_next(i, aij):
	bij = s - sa[i] + aij
	if bij not in d:
		return (-1, bij)
	else:
		return (d[bij], bij)

def loop_to_num(loop):
	ret = 0
	for i in reversed(range(k)):
		ret <<= 1
		ret += loop[i]
	return ret
loop_dict = {}
used = set()
for i in range(k):
	for aij in aa[i]:
		if aij in used:
			continue
		loop = [0] * k
		num = [float('Inf')] * k
		start_i = i
		start_aij = aij
		j = i
		loop[j] = 1
		num[j] = aij
		used.add(aij)
		exist = False
		for _ in range(100):
			(j, aij) = calc_next(j, aij)
			if j == -1:
				break
			if loop[j] == 0:
				loop[j] = 1
				num[j] = aij
			else:
				if j == start_i and aij == start_aij:
					exist = True
				break
		if exist:
			m = loop_to_num(loop)
			loop_dict[m] = tuple(num)
			for numi in num:
				if numi != float('inf'):
					used.add(numi)
mask = 1 << k
for state in range(1, mask):
	if state in loop_dict:
		continue
	j = state - 1 & state
	while j:
		i = state ^ j
		if i in loop_dict and j in loop_dict:
			tp = tuple((min(loop_dict[i][l], loop_dict[j][l]) for l in range(k)))
			loop_dict[state] = tp
			break
		j = j - 1 & state
if mask - 1 not in loop_dict:
	print('No')
else:
	print('Yes')
	t = loop_dict[mask - 1]
	ns = [sa[i] - t[i] for i in range(k)]
	need = [s - ns[i] for i in range(k)]
	for i in range(k):
		print(t[i], need.index(t[i]) + 1)


def main():
	k = int(input())
	n = []
	a = []
	for i in range(k):
		line = [int(x) for x in input().split()]
		ni = line[0]
		ai = []
		n.append(ni)
		a.append(ai)
		for j in range(ni):
			ai.append(line[1 + j])
	(answer, c, p) = solve(k, n, a)
	if answer:
		print('Yes')
		for i in range(k):
			print(c[i], p[i] + 1)
	else:
		print('No')

def solve(k, n, a):
	(asum, sums) = calc_sums(k, n, a)
	if asum % k != 0:
		return (False, None, None)
	tsum = asum / k
	num_map = build_num_map(k, n, a)
	masks = [None] * (1 << k)
	answer = [False] * (1 << k)
	left = [0] * (1 << k)
	right = [0] * (1 << k)
	for i in range(k):
		for j in range(n[i]):
			(found, mask, path) = find_cycle(i, j, i, j, k, n, a, sums, tsum, num_map, 0, dict())
			if found:
				answer[mask] = True
				masks[mask] = path
	for mask_right in range(1 << k):
		if not masks[mask_right]:
			continue
		zeroes_count = 0
		for u in range(k):
			if 1 << u > mask_right:
				break
			if mask_right & 1 << u == 0:
				zeroes_count += 1
		for mask_mask in range(1 << zeroes_count):
			mask_left = 0
			c = 0
			for u in range(k):
				if 1 << u > mask_right:
					break
				if mask_right & 1 << u == 0:
					if mask_mask & 1 << c != 0:
						mask_left = mask_left | 1 << u
					c += 1
			joint_mask = mask_left | mask_right
			if answer[mask_left] and (not answer[joint_mask]):
				answer[joint_mask] = True
				left[joint_mask] = mask_left
				right[joint_mask] = mask_right
				if joint_mask == (1 << k) - 1:
					return build_answer(k, masks, left, right)
	if answer[(1 << k) - 1]:
		return build_answer(k, masks, left, right)
	return (False, None, None)

def build_answer(k, masks, left, right):
	c = [-1] * k
	p = [-1] * k
	pos = (1 << k) - 1
	while not masks[pos]:
		for (key, val) in masks[right[pos]].items():
			c[key] = val[0]
			p[key] = val[1]
		pos = left[pos]
	for (key, val) in masks[pos].items():
		c[key] = val[0]
		p[key] = val[1]
	return (True, c, p)

def build_num_map(k, n, a):
	result = dict()
	for i in range(k):
		for j in range(n[i]):
			result[a[i][j]] = (i, j)
	return result

def find_cycle(i_origin, j_origin, i, j, k, n, a, sums, tsum, num_map, mask, path):
	if mask & 1 << i != 0:
		if i == i_origin and j == j_origin:
			return (True, mask, path)
		else:
			return (False, None, None)
	mask = mask | 1 << i
	a_needed = tsum - (sums[i] - a[i][j])
	if a_needed not in num_map:
		return (False, None, None)
	(i_next, j_next) = num_map[a_needed]
	path[i_next] = (a[i_next][j_next], i)
	return find_cycle(i_origin, j_origin, i_next, j_next, k, n, a, sums, tsum, num_map, mask, path)

def calc_sums(k, n, a):
	sums = [0] * k
	for i in range(k):
		for j in range(n[i]):
			sums[i] = sums[i] + a[i][j]
	asum = 0
	for i in range(k):
		asum = asum + sums[i]
	return (asum, sums)
main()


def main():
	k = int(input())
	n = []
	a = []
	for i in range(k):
		line = [int(x) for x in input().split()]
		ni = line[0]
		ai = []
		n.append(ni)
		a.append(ai)
		for j in range(ni):
			ai.append(line[1 + j])
	(answer, c, p) = solve(k, n, a)
	if answer:
		print('Yes')
		for i in range(k):
			print(c[i], p[i] + 1)
	else:
		print('No')

def solve(k, n, a):
	(asum, sums) = calc_sums(k, n, a)
	if asum % k != 0:
		return (False, None, None)
	tsum = asum / k
	num_map = build_num_map(k, n, a)
	masks = [None] * (1 << k)
	simple = [False] * (1 << k)
	answer = [False] * (1 << k)
	left = [0] * (1 << k)
	right = [0] * (1 << k)
	by_last_one = [[] for _ in range(k)]
	for i in range(k):
		for j in range(n[i]):
			(found, mask, path) = find_cycle(i, j, i, j, k, n, a, sums, tsum, num_map, 0, [])
			if found and (not answer[mask]):
				answer[mask] = True
				masks[mask] = path
				simple[mask] = True
				by_last_one[calc_last_one(mask)].append(mask)
	if answer[(1 << k) - 1]:
		return build_answer(k, masks, left, right)
	for mask_right in range(2, 1 << k):
		if not simple[mask_right]:
			continue
		last_one = calc_last_one(mask_right)
		zeroes_count = 0
		alternative_sum = 0
		zero_list = []
		for u in range(last_one):
			if mask_right & 1 << u == 0:
				zeroes_count += 1
				alternative_sum += len(by_last_one[u])
				zero_list.append(u)
		if zeroes_count == 0:
			continue
		if alternative_sum < 1 << zeroes_count:
			for fill_last_zero in zero_list:
				for mask_left in by_last_one[fill_last_zero]:
					if mask_left & mask_right != 0:
						continue
					joint_mask = mask_left | mask_right
					if not answer[joint_mask]:
						answer[joint_mask] = True
						left[joint_mask] = mask_left
						right[joint_mask] = mask_right
						by_last_one[last_one].append(joint_mask)
						if joint_mask == (1 << k) - 1:
							return build_answer(k, masks, left, right)
		else:
			for mask_mask in range(1 << zeroes_count):
				mask_left = 0
				for u in range(zeroes_count):
					if mask_mask & 1 << u != 0:
						mask_left = mask_left | 1 << zero_list[u]
				joint_mask = mask_left | mask_right
				if answer[mask_left] and (not answer[joint_mask]):
					answer[joint_mask] = True
					left[joint_mask] = mask_left
					right[joint_mask] = mask_right
					by_last_one[last_one].append(joint_mask)
					if joint_mask == (1 << k) - 1:
						return build_answer(k, masks, left, right)
	return (False, None, None)

def calc_last_one(x):
	result = -1
	while x > 0:
		x = x >> 1
		result = result + 1
	return result

def build_answer(k, masks, left, right):
	c = [-1] * k
	p = [-1] * k
	pos = (1 << k) - 1
	while not masks[pos]:
		for (i, a, j) in masks[right[pos]]:
			c[i] = a
			p[i] = j
		pos = left[pos]
	for (i, a, j) in masks[pos]:
		c[i] = a
		p[i] = j
	return (True, c, p)

def build_num_map(k, n, a):
	result = dict()
	for i in range(k):
		for j in range(n[i]):
			result[a[i][j]] = (i, j)
	return result

def find_cycle(i_origin, j_origin, i, j, k, n, a, sums, tsum, num_map, mask, path):
	if mask & 1 << i != 0:
		if i == i_origin and j == j_origin:
			return (True, mask, path)
		else:
			return (False, None, None)
	mask = mask | 1 << i
	a_needed = tsum - (sums[i] - a[i][j])
	if a_needed not in num_map:
		return (False, None, None)
	(i_next, j_next) = num_map[a_needed]
	path.append((i_next, a[i_next][j_next], i))
	return find_cycle(i_origin, j_origin, i_next, j_next, k, n, a, sums, tsum, num_map, mask, path)

def calc_sums(k, n, a):
	sums = [0] * k
	for i in range(k):
		for j in range(n[i]):
			sums[i] = sums[i] + a[i][j]
	asum = 0
	for i in range(k):
		asum = asum + sums[i]
	return (asum, sums)

def __starting_point():
	main()
__starting_point()


from collections import defaultdict
data = defaultdict(list)
position = defaultdict()
nxt = defaultdict()
agg_sum = list()
k = int(input())
trace = defaultdict()
F = [False for x in range(1 << k)]
back = [0 for x in range(1 << k)]
total_sum = 0
res = [(0, 0) for x in range(k)]

def build_mask(trace_mask):
	if trace_mask == 0:
		return
	if trace.get(trace_mask):
		for data in trace.get(trace_mask):
			(fr, to, v) = data
			res[fr] = (v, to)
		return
	sub_mask = back[trace_mask]
	build_mask(sub_mask)
	build_mask(trace_mask - sub_mask)
for i in range(k):
	values = list(map(int, input().split(' ')))
	data[i] = values[1:]
	agg_sum.append(sum(data[i]))
	total_sum += agg_sum[i]
	for (cnt, v) in enumerate(data[i], 0):
		position[v] = (i, cnt)
if total_sum % k != 0:
	print('No')
	exit(0)
row_sum = total_sum // k
for i in range(k):
	for (cnt, value) in enumerate(data.get(i), 0):
		x = i
		y = cnt
		mask = 1 << x
		could = True
		circle = list()
		while True:
			next_value = row_sum - agg_sum[x] + data.get(x)[y]
			if position.get(next_value) is None:
				could = False
				break
			last_x = x
			last_y = y
			(x, y) = position.get(next_value)
			circle.append((x, last_x, next_value))
			if x == i and y == cnt:
				break
			if mask & 1 << x:
				could = False
				break
			mask |= 1 << x
		F[mask] |= could
		if could:
			trace[mask] = circle
for mask in range(1, 1 << k):
	sub = mask
	while sub > 0:
		if F[sub] and F[mask - sub]:
			F[mask] = True
			back[mask] = sub
			break
		sub = mask & sub - 1
if F[(1 << k) - 1]:
	print('Yes')
	build_mask((1 << k) - 1)
	for value in res:
		print(value[0], value[1] + 1)
else:
	print('No')


import sys
n = sys.stdin.readline()
n = int(n)

def get_graph(n):
	graph = []
	for _ in range(n):
		entries = list(map(lambda x: int(x), sys.stdin.readline().split(' ')[1:]))
		graph.append(entries)
	return graph

def chain(target, buckets, reverse_bucket, sum_bucket, bucket_num, val):
	mask = 2 ** bucket_num
	mem = []
	buckets_seen = set({bucket_num})
	og_bucket = bucket_num
	og_val = val
	for _ in range(len(buckets)):
		rem = target - sum_bucket[bucket_num] + val
		if rem not in reverse_bucket:
			return (None, [])
		new_bucket = reverse_bucket[rem]
		if new_bucket == og_bucket and rem != og_val:
			return (None, [])
		elif new_bucket == og_bucket and rem == og_val:
			mem.append((rem, bucket_num))
			return (mask | 2 ** new_bucket, mem)
		elif new_bucket in buckets_seen:
			return (None, [])
		buckets_seen.add(new_bucket)
		mask = mask | 2 ** new_bucket
		mem.append((rem, bucket_num))
		bucket_num = new_bucket
		val = rem
	return (None, [])

def helper(chains, mask, mem):
	if mask == 0:
		return []
	if mask in mem:
		return mem[mask]
	for (i, chain) in enumerate(chains):
		if mask >> i & 0:
			continue
		for key in chain:
			if key | mask != mask:
				continue
			future = helper(chains, ~key & mask, mem)
			if future is not None:
				mem[mask] = chain[key] + future
				return mem[mask]
	mem[mask] = None
	return None

def solve(n):
	buckets = get_graph(n)
	reverse_bucket = {}
	sum_bucket = [0] * len(buckets)
	total_sum = 0
	for (i, bucket) in enumerate(buckets):
		for x in bucket:
			total_sum += x
			sum_bucket[i] += x
			reverse_bucket[x] = i
	target = total_sum / len(buckets)
	chains = []
	for (i, bucket) in enumerate(buckets):
		seto = {}
		for x in bucket:
			(key, val) = chain(target, buckets, reverse_bucket, sum_bucket, i, x)
			if key is not None:
				seto[key] = val
		chains.append(seto)
	return (helper(chains, 2 ** len(buckets) - 1, {}), reverse_bucket)

def result(n):
	(res, reverse_bucket) = solve(n)
	if res is None:
		sys.stdout.write('No\n')
	else:
		res = sorted(res, key=lambda x: reverse_bucket[x[0]])
		sys.stdout.write('Yes\n')
		for (x, y) in res:
			x = int(x)
			y = int(y) + 1
			stuff = ' '.join([str(x), str(y), '\n'])
			sys.stdout.write(stuff)
result(n)


def main():
	k = int(input())
	n = []
	a = []
	for i in range(k):
		line = [int(x) for x in input().split()]
		ni = line[0]
		ai = []
		n.append(ni)
		a.append(ai)
		for j in range(ni):
			ai.append(line[1 + j])
	(answer, c, p) = solve(k, n, a)
	if answer:
		print('Yes')
		for i in range(k):
			print(c[i], p[i] + 1)
	else:
		print('No')

def solve(k, n, a):
	(asum, sums) = calc_sums(k, n, a)
	if asum % k != 0:
		return (False, None, None)
	tsum = asum / k
	num_map = build_num_map(k, n, a)
	masks = [None] * (1 << k)
	simple = [False] * (1 << k)
	for i in range(k):
		for j in range(n[i]):
			(found, mask, path) = find_cycle(i, j, i, j, k, n, a, sums, tsum, num_map, 0, dict())
			if found:
				simple[mask] = True
				masks[mask] = path
	for i in range(1 << k):
		if not simple[i]:
			continue
		mask = i
		zeroes_count = 0
		for u in range(k):
			if 1 << u > mask:
				break
			if mask & 1 << u == 0:
				zeroes_count += 1
		for mask_mask in range(1 << zeroes_count):
			mask_child = 0
			c = 0
			for u in range(k):
				if 1 << u > mask:
					break
				if mask & 1 << u == 0:
					if mask_mask & 1 << c != 0:
						mask_child = mask_child | 1 << u
					c += 1
			if masks[mask_child] and (not masks[mask_child | mask]):
				masks[mask_child | mask] = {**masks[mask_child], **masks[mask]}
				if mask_child | mask == (1 << k) - 1:
					c = [-1] * k
					p = [-1] * k
					d = masks[(1 << k) - 1]
					for (key, val) in d.items():
						c[key] = val[0]
						p[key] = val[1]
					return (True, c, p)
	if masks[(1 << k) - 1]:
		c = [-1] * k
		p = [-1] * k
		d = masks[(1 << k) - 1]
		for (key, val) in d.items():
			c[key] = val[0]
			p[key] = val[1]
		return (True, c, p)
	return (False, None, None)

def build_num_map(k, n, a):
	result = dict()
	for i in range(k):
		for j in range(n[i]):
			result[a[i][j]] = (i, j)
	return result

def find_cycle(i_origin, j_origin, i, j, k, n, a, sums, tsum, num_map, mask, path):
	if mask & 1 << i != 0:
		if i == i_origin and j == j_origin:
			return (True, mask, path)
		else:
			return (False, None, None)
	mask = mask | 1 << i
	a_needed = tsum - (sums[i] - a[i][j])
	if a_needed not in num_map:
		return (False, None, None)
	(i_next, j_next) = num_map[a_needed]
	path[i_next] = (a[i_next][j_next], i)
	return find_cycle(i_origin, j_origin, i_next, j_next, k, n, a, sums, tsum, num_map, mask, path)

def calc_sums(k, n, a):
	sums = [0] * k
	for i in range(k):
		for j in range(n[i]):
			sums[i] = sums[i] + a[i][j]
	asum = 0
	for i in range(k):
		asum = asum + sums[i]
	return (asum, sums)
main()


from itertools import accumulate
from sys import stdin, stdout

def main():
	k = int(stdin.readline())
	a = [tuple(map(int, stdin.readline().split()[1:])) for _ in range(k)]
	a2ij = {aij: (i, j) for (i, ai) in enumerate(a) for (j, aij) in enumerate(ai)}
	plena = [0] + list(accumulate(map(len, a)))
	suma = tuple(map(sum, a))
	totala = sum(suma)
	if totala % k != 0:
		stdout.write('No\n')
	else:
		needle = totala // k
		mask2i2cp = compute_mask2i2cp(a, a2ij, needle, plena, suma)
		dp = compute_previous_mask(mask2i2cp)
		output(dp, mask2i2cp)

def compute_mask2i2cp(a, a2ij, needle, plena, suma):
	used = [False] * plena[-1]
	number_of_masks = 1 << len(a)
	mask2i2cp = [-1] * number_of_masks
	for (i, ai) in enumerate(a):
		for (j, aij) in enumerate(ai):
			if not used[plena[i] + j]:
				(mask, i2cp) = compute_mask_i2cp(a2ij, aij, i, j, needle, suma)
				if i2cp != -1:
					mask2i2cp[mask] = i2cp
					for cp in i2cp:
						if cp != -1:
							(c, p) = cp
							(ii, jj) = a2ij[c]
							used[plena[ii] + jj] = True
	return mask2i2cp

def output(dp, mask2i2cp):
	mask = len(mask2i2cp) - 1
	if dp[mask] == -1:
		stdout.write('No\n')
	else:
		answer = [-1] * len(mask2i2cp[dp[mask]])
		while mask > 0:
			current_mask = dp[mask]
			for (i, cp) in enumerate(mask2i2cp[current_mask]):
				if 1 == current_mask >> i & 1:
					(c, p) = cp
					answer[i] = (c, p)
			mask ^= current_mask
		stdout.write('Yes\n' + '\n'.join(('{} {}'.format(c, 1 + p) for (c, p) in answer)))

def compute_mask_i2cp(a2ij, aij, i, j, needle, suma):
	i2cp = [-1] * len(suma)
	mask = 0
	current_a = aij
	current_i = i
	try:
		while True:
			next_a = needle - (suma[current_i] - current_a)
			(next_i, next_j) = a2ij[next_a]
			if mask >> next_i & 1 == 1:
				return (mask, -1)
			mask |= 1 << next_i
			i2cp[next_i] = (next_a, current_i)
			if next_i == i:
				if next_j == j:
					return (mask, i2cp)
				return (mask, -1)
			if next_i == current_i:
				return (mask, -1)
			current_a = next_a
			current_i = next_i
	except KeyError:
		return (mask, -1)

def compute_previous_mask(mask2cp):
	number_of_masks = len(mask2cp)
	dp = [-1] * number_of_masks
	dp[0] = 0
	for (mask, cp) in enumerate(mask2cp):
		if cp != -1:
			complement_mask = number_of_masks - 1 & ~mask
			previous_mask = complement_mask
			while previous_mask > 0:
				if dp[previous_mask] != -1 and dp[previous_mask | mask] == -1:
					dp[previous_mask | mask] = mask
				previous_mask = previous_mask - 1 & complement_mask
			if dp[mask] == -1:
				dp[mask] = mask
	return dp
main()