F. Раскраска рёбер в три цвета
ограничение по времени на тест
4 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Дан неориентированный связный граф из $$$n$$$ вершин и $$$m$$$ рёбер, в котором $$$m \le n + 9$$$.

Каждое ребро графа нужно покрасить в один из трёх цветов, пронумерованных от $$$1$$$ до $$$3$$$. Будем говорить, что вершины $$$u$$$ и $$$v$$$ достижимы по цвету $$$c$$$, если существует путь из $$$u$$$ в $$$v$$$, состоящий только из рёбер цвета $$$c$$$.

Определите, существует ли способ покрасить рёбра, для которого выполнены следующие условия:

  • в каждый из трёх цветов покрашено хотя бы одно ребро;
  • для каждой пары цветов $$$i$$$ и $$$j$$$ и каждой пары вершин $$$u$$$ и $$$v$$$ выполняется следующее: если $$$u$$$ и $$$v$$$ достижимы по цвету $$$i$$$ и $$$i \lt j$$$, то они достижимы и по цвету $$$j$$$.
Входные данные

Первая строка содержит одно целое число $$$t$$$ ($$$1 \le t \le 1000$$$) — количество наборов входных данных.

Каждый набор входных данных начинается со строки, которая содержит два целых числа $$$n$$$ и $$$m$$$ ($$$2 \le n \le 3000$$$; $$$n - 1 \le m \le n + 9$$$) — количество вершин и рёбер графа.

Следующие $$$m$$$ строк набора входных данных содержат по два целых числа $$$u_i$$$ и $$$v_i$$$ ($$$1 \le u_i, v_i \le n$$$, $$$u_i \ne v_i$$$) — концы $$$i$$$-го ребра.

Дополнительные ограничения на входные данные:

  • сумма $$$n$$$ по всем наборам входных данных не превосходит $$$3000$$$;
  • в графе нет ни петель, ни кратных рёбер;
  • граф является связным.
Выходные данные

Для каждого набора входных данных выведите ответ следующим образом: если раскраска рёбер существует, выведите YES, иначе выведите NO. Каждую букву можно выводить в любом регистре.

Пример
Входные данные
4
4 6
1 2
2 3
3 1
1 4
2 4
3 4
3 3
1 2
2 3
3 1
7 9
1 2
2 3
3 1
1 4
4 5
5 1
1 6
6 7
7 1
5 8
1 2
2 3
3 4
4 1
5 1
5 2
5 3
5 4
Выходные данные
YES
NO
NO
YES
Примечание

В первом примере можно покрасить $$$5$$$-е ребро в цвет $$$1$$$, $$$1$$$-е и $$$4$$$-е ребро в цвет $$$2$$$, а остальные рёбра в цвет $$$3$$$.