У Алексея есть $$$n$$$ друзей. А ещё Алексей сейчас в отпуске, поэтому у него есть целых $$$m$$$ дней, чтобы поиграть в эту новую популярную кооперативную игру! Поскольку эта игра кооперативная, Алексею нужен один сокомандник в каждый из $$$m$$$ дней.
Каждый день какие-то его друзья свободны и готовы играть в эту игру, а остальные заняты и не могут. Каждый день Алексей должен выбрать одного из свободных друзей и предложить ему поиграть (а тот, разумеется, согласится). Однако если какой-то из друзей будет играть с Алексеем суммарно строго больше $$$\left\lceil\dfrac{m}{2}\right\rceil$$$ раз (округление вверх), то все остальные обидятся. Конечно же, Алексей не хочет никого обижать.
Помогите ему выбрать сокомандников таким образом, чтобы никто не играл с Алексеем суммарно строго больше $$$\left\lceil\dfrac{m}{2}\right\rceil$$$ раз.
Во входных данных находятся несколько наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10\,000$$$) — количество наборов входных данных. Далее следуют наборы входных данных.
Первая строка каждого набора входных данных содержит два натуральных числа $$$n$$$ и $$$m$$$ ($$$1\leq n, m\leq 100\,000$$$) — количество друзей и количество дней, соответственно.
В $$$i$$$-й из следующих $$$m$$$ строк содержится натуральное число $$$k_i$$$ ($$$1\leq k_i\leq n$$$), за которым следуют $$$k_i$$$ попарно различных целых чисел $$$f_{i1}$$$, ..., $$$f_{ik_i}$$$ ($$$1\leq f_{ij}\leq n$$$), разделённых пробелами — свободные друзья в день $$$i$$$.
Гарантируется, что сумма значений $$$n$$$ и сумма значений $$$m$$$ по всем наборам входных данных не превосходят $$$100\,000$$$. Гарантируется, что сумма всех $$$k_i$$$ по всем дням всех наборов входных данных не превосходит $$$200\,000$$$.
Выведите ответ для каждого набора входных данных. Если невозможно никого не обидеть, то выведите «NO».
В противном случае в первой строке выведите «YES», а во второй строке выведите $$$m$$$ целых чисел $$$c_1$$$, ..., $$$c_m$$$, разделённых пробелами. Каждое $$$c_i$$$ должно быть номером друга, взятого в команду в $$$i$$$-й день (соответственно, это должно быть одно из чисел $$$f_{ij}$$$).
Никакое значение не должно встречаться больше, чем $$$\left\lceil\dfrac{m}{2}\right\rceil$$$ раз. Если есть несколько возможных ответов, выведите любой из них.
2 4 6 1 1 2 1 2 3 1 2 3 4 1 2 3 4 2 2 3 1 3 2 2 1 1 1 1
YES 1 2 1 1 2 3 NO
| Технокубок 2021 - Финал |
|---|
| Закончено |
