Sum Balance
Contest: Codeforces Round 599 (Div. 1)
Difficulty rating: 2400
Tags: bitmasks, dfs and similar, dp, graphs

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 format:
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 format:
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).

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

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$$$.

Example input:
4
3 1 7 4
2 3 2
2 8 5
1 10

Example output:
Yes
7 2
2 3
5 1
10 4

Example input:
2
2 3 -2
2 -1 5

Example output:
No

Editorial:
First, calculate the total average sum $$$s := (\sum_{i=1}^n a_i)/k$$$. If the answer is positive, the sum of integers in each box must be equal to $$$s$$$ after reordering. If $$$s$$$ is not integer, then the answer is immediately negative.
Now, suppose that an integer $$$x := a_{i,p}$$$ is taken out of some box $$$i$$$. Then we know that it should be replaced by $$$y := s - \sum_{j = 1}^{n_i} a_{i,j} + a_{i,p}$$$. We then construct a graph where all of the given integers are vertices, and we draw a directed edge from $$$x$$$ to $$$y$$$.
Note that we obtain a functional graph. Examine all of the cycles of this graph; since this a functional graph, no two cycles share the same vertex. Let $$$n := \sum_{i=1}^k n_i$$$, then the total number of cycles is at most $$$n \leq 15 \cdot 5000 = 75000$$$.
Examine any valid reordering. It is easy to see that it is a collection of cycles from the obtained graph such that each box is visited by some cycle exactly once. Therefore, lets extract all of the cycles from our graph such that do not pass through the same box twice. A valid reordering then is some subset of these cycles that visit all of the $$$k$$$ boxes exactly once.
We can also reformulate this problem in the following way: each of the extracted cycles $$$C$$$ visits some set of boxes $$$S$$$. Find all of such subsets $$$S$$$; the number of such subsets is at most $$$2^k$$$. Now, the problem is reduced to exactly covering the set $$$\{1,\ldots,k\}$$$ with some subset of such sets.
This is a classical problem that can be solved in $$$O(3^n)$$$ using dynamic programming. For a subset $$$X$$$ of $$$\{1,\ldots,k\}$$$, define $$$dp[X]$$$ to be true if $$$X$$$ can be exactly covered, and false otherwise. Firstly, $$$dp[\varnothing] = true$$$. To find $$$dp[X]$$$ for $$$X \neq \varnothing$$$, iterate over all subsets $$$S$$$ of $$$X$$$, and check whether $$$S$$$ is visited by some cycle and $$$X \setminus S$$$ can be covered (e.g., $$$dp[X \setminus S]$$$ is true). Then the answer is $$$dp[\{1,\ldots,k\}]$$$. This algorithm can be implemented with complexity $$$O(3^k)$$$, you can read about it here:https://cp-algorithms.com/algebra/all-submasks.html. The reordering can be restored from this DP table.
The total complexity of the algorithm: $$$O(k \cdot \sum_{i=1}^k n_i + 3^k)$$$.