D. Веселые фонари
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
256 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Кот ученый гулял ночью по улицам города Мышкина. Он заметил, что по городу во многих местах стоят фонари. Фонари могут стоять только в начале или конце улицы или просто стоять в парках, не соединяя никакие улицы. Один фонарь может стоять в начале или конце нескольких улиц одновременно.

Кот понял, что город хорошо освещен, но заметил, что все фонари светят одним и тем же цветом — желтым. Так как приближался праздник, то Кот подумал, что надо сделать город более веселым и поменять лампочки в некоторых фонарях на другой цвет.

Кот на складе нашел только лампочки белого цвета и потому решил, что он поменяет лампочки так, чтобы два фонаря, соединенные улицей, имели различные цвета.

Помогите Коту определить, может ли он так поменять лампочки, что будет выполняться вышеприведенное правило.

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

В первой строке содержится единственное целое число $$$T$$$ ($$$1 \le T \le 50$$$) — количество тестовых случаев.

Каждая из следующих $$$T$$$ строк содержит описание одного случая — набор целых чисел через пробел:

  • сначала идет $$$N$$$ $$$(1 \le N \le 400)$$$ — количество фонарей в городе;
  • затем идет $$$M$$$ $$$(0 \le M \le \frac{N \cdot (N - 1)}{2})$$$ — количество улиц, соединяющих фонари;
  • далее идет $$$M$$$ пар $$$A_i$$$ $$$B_i$$$ $$$(1 \le A_i, B_i \le N)$$$ — номера фонарей, соединенных $$$i$$$-й улицей.

Между двумя фонарями может быть более одной улицы. Улица может соединять фонарь с самим собой.

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

Для каждого тестового случая выведите единственную строку:

  • YES, если Кот может поменять лампочки так, чтобы все улицы соединяли фонари разных цветов;
  • NO в обратном случае.
Пример
Входные данные
3
7 3 1 2 1 3 6 1
4 4 2 1 3 2 1 4 3 1
4 4 1 3 4 2 4 1 2 3
Выходные данные
YES
NO
YES