Codeforces Round 599 (Div. 1) |
---|
Закончено |
У Уджана в коробках накопилось много чисел. Ему нравится баланс и порядок, поэтому он решил перераспределить числа.
Всего есть $$$k$$$ коробок, пронумерованных числами от $$$1$$$ до $$$k$$$. $$$i$$$-я коробка содержит $$$n_i$$$ целых чисел. Числа могут быть и отрицательными. Все данные числа различны.
Уджан ленивый, поэтому он выполнит следующее перераспределение ровно один раз. Вначале он выберет по одному числу из каждой коробки, всего $$$k$$$ чисел. Затем он поместит выбранные числа по одному числу в каждую из коробок, так, что количество чисел в каждой коробке такое же, как и в начале. Учтите, что он может поместить число, которое он выбрал из одной коробки обратно в ту же коробку.
Уджан будет рад, если сумма чисел во всех коробках станет одинаковая. Может ли он достичь этого, и сбалансировать таким образом все коробки, как все вещи и должны быть?
Первая строка ввода содержит одно целое число $$$k$$$ ($$$1 \leq k \leq 15$$$), количество коробок.
$$$i$$$-я из следующих $$$k$$$ строк начинается с одного целого числа $$$n_i$$$ ($$$1 \leq n_i \leq 5\,000$$$), количества чисел в коробке с номером $$$i$$$. Затем та же строка содержит $$$n_i$$$ чисел $$$a_{i,1}, \ldots, a_{i,n_i}$$$ ($$$|a_{i,j}| \leq 10^9$$$), числа, которые находятся в $$$i$$$-й коробке.
Гарантируется, что все числа $$$a_{i,j}$$$ различны.
Если Уджан не может достичь своей цели, выведите «No». В противоположном случае выведите сначала «Yes», и затем выведите $$$k$$$ строк. $$$i$$$-я из этих строк должна содержать два целых числа $$$c_i$$$ и $$$p_i$$$. Эти числа должны означать то, что Уджан выберет число $$$c_i$$$ из $$$i$$$-й коробки и поместит его в $$$p_i$$$-ю коробку.
Если существует больше одного решения, выведите любое.
Вы можете выводить каждую букву в любом регистре (строчную или заглавную).
4 3 1 7 4 2 3 2 2 8 5 1 10
Yes 7 2 2 3 5 1 10 4
2 2 3 -2 2 -1 5
No
2 2 -10 10 2 0 -20
Yes -10 2 -20 1
В первом примере Уджан может поместить число $$$7$$$ во $$$2$$$-ю коробку, число $$$2$$$ в $$$3$$$-ю коробку, число $$$5$$$ в $$$1$$$-ю коробку, а число $$$10$$$ оставить в той же $$$4$$$-й коробке. Тогда коробки будут содержать числа $$$\{1,5,4\}$$$, $$$\{3, 7\}$$$, $$$\{8,2\}$$$ и $$$\{10\}$$$. Сумма чисел в каждой коробке станет равна $$$10$$$.
Во втором примере невозможно выбрать и перераспределить числа данным способом.
В третьем примере можно поменять местами числа $$$-20$$$ и $$$-10$$$, тогда сумма чисел в обеих коробках станет равна $$$-10$$$.
Название |
---|