406425: GYM102399 I Жулик, не воруй

I. Жулик, не воруйограничение по времени на тест2 секундыограничение по памяти на тест512 мегабайтвводстандартный вводвыводстандартный выводЯ Карта! Я КАрТa! Я КААААРТА!!!Карта

В ожидании новых приключений Башмачок захотел совершить доброе дело. Посовещавшись с Картой и Рюкзаком, он решил подарить Даше связный граф. Даша не любит, когда в графе присутствуют петли или кратные ребра, и Башмачок прекрасно об этом знает. После долгих поисков Башмачок выбрал $$$t$$$ вариантов графа, которые могли бы понравиться Даше, но, к сожалению, все его планы решил испортить лис Жулик.

Жулик узнал, что Даша недавно научилась считать до $$$3$$$, и у него родилась идея. Он хочет совершить кражу так, чтобы Даша не заметила пропажи, поэтому он решил украсть непустой набор вершин такой, что если удалить выбранные вершины и связанные с ними рёбра из графа, то для любой из оставшихся вершин будет верно, что ее степень (число смежных рёбер) будет иметь такой же остаток от деления на $$$3$$$, что и степень до удаления рёбер. Также он понял, что будет слишком подозрительно, если он украдет все вершины, поэтому он решил воздержаться от такой соблазнительной затеи.

Башмачок понял, что он никак не может позволить случиться преступлению. Но он вскоре осознал, что одному ему не справиться. Поэтому он решил попросить у вас помощи. Башмачок хочет для каждого варианта графа узнать, сможет ли Жулик осуществить свои злобные планы.

Входные данные

В первой строке задано целое число $$$t$$$ ($$$1 \leq t \leq 100\,000$$$) — количество вариантов графа.

Первая строка описания каждого варианта содержит два целых числа $$$n$$$, $$$m$$$ ($$$1 \leq n \leq 500\,000,\ 0 \leq m \leq 500\,000$$$) — количество вершин и рёбер в графе, соответственно.

Затем следуют $$$m$$$ строк, в каждой из которых записаны два целых числа $$$a_i$$$, $$$b_i$$$ ($$$1 \leq a_i, b_i \leq n$$$) — номера вершин, соединяемых $$$i$$$-м ребром. Гарантируется, что граф связен и что в нем нет петель и кратных ребер.

Гарантируется, что сумма $$$n$$$ по всем вариантам не превосходит $$$500\,000$$$, и что сумма $$$m$$$ по всем вариантам не превосходит $$$500\,000$$$.

Описания вариантов графа разделены одной пустой строкой.

Выходные данные

Для каждого из вариантов графа выведите «Yes», если Жулик может осуществить свой план для данного варианта графа, или «No», если Жулику не удастся обмануть Дашу.

В случае, если Жулик может осуществить свой коварный план, выведите пример, как именно он может это сделать. Первая строка примера должна содержать целое число $$$c$$$ ($$$1 < c < n$$$) — количество вершин, которые может украсть Жулик, чтобы Даша не заметила пропажи. В следующей строке выведите $$$c$$$ различных чисел — номера этих вершин. Порядок вывода вершин не важен. Если способов украсть вершины требуемым образом несколько, выведите любой из них.

Обратите внимание, что Жулик необязательно крадет максимальное возможное число вершин.

ПримерВходные данные

3
3 3
1 2
2 3
3 1

6 6
1 2
1 3
2 3
2 5
2 6
2 4

8 12
1 2
1 3
2 3
1 4
4 5
5 1
3 6
3 7
3 8
6 1
7 1
8 1

Выходные данные

No
Yes
3
4 5 6
Yes
3
6 7 8

Примечание

На картинке ниже изображен третий вариант из примера. Жирным отмечены вершины, которые может украть Жулик.