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

Как всем известно, Ариан — весёлый парень. Он решил создавать забавные графы. Для графа $$$G$$$ он определяет забавный граф $$$G'$$$ графа $$$G$$$ следующим образом:

  • Каждая вершина $$$v'$$$ графа $$$G'$$$ отображается в непустое независимое множество$$$^{\text{∗}}$$$ или клику$$$^{\text{†}}$$$ в $$$G$$$.
  • Множества вершин графа $$$G$$$, в которые отображаются вершины $$$G'$$$, попарно не пересекаются и в совокупности покрывают все вершины $$$G$$$, то есть множества вершин $$$G$$$, соответствующие вершинам $$$G'$$$, образуют разбиение множества вершин $$$G$$$.
  • Если ребро соединяет две вершины $$$v_1'$$$ и $$$v_2'$$$ в $$$G'$$$, то между каждой вершиной из множества $$$G$$$, соответствующего $$$v_1'$$$, и каждой вершиной из множества $$$G$$$, соответствующего $$$v_2'$$$, есть ребро.
  • Если ребро не соединяет две вершины $$$v_1'$$$ и $$$v_2'$$$ в $$$G'$$$, то между любой вершиной из множества $$$G$$$, соответствующего $$$v_1'$$$, и любой вершиной из множества $$$G$$$, соответствующего $$$v_2'$$$, нет ребра.

Как всем снова известно, Харшит — превосходный парень. Он решил использовать забавные графы для создания своих собственных превосходных графов. Для графа $$$G$$$ забавный граф $$$G' '$$$ называется превосходным графом $$$G$$$, если $$$G' '$$$ имеет минимальное число вершин среди всех возможных забавных графов $$$G$$$.

Ариян даёт Харшиту $$$k$$$ простых неориентированных графов$$$^{\text{‡}}$$$ $$$G_1, G_2,\ldots,G_k$$$, все на одном и том же множестве вершин $$$V$$$. Харшит задаётся вопросом, существуют ли $$$k$$$ других графов $$$H_1, H_2,\ldots,H_k$$$, все на некотором другом множестве вершин $$$V'$$$, таких что:

  • $$$G_i$$$ является превосходным графом для $$$H_i$$$ для всех $$$i\in \{1,2,\ldots,k\}$$$.
  • Если вершина $$$v\in V$$$ отображается в независимое множество размера больше $$$1$$$ в какой-либо паре $$$G_i, H_i$$$ (для $$$1\leq i\leq k$$$), то не существует пары $$$G_j, H_j$$$ (для $$$1\leq j\leq k, j\neq i$$$), где $$$v$$$ отображается в клику размера больше $$$1$$$.

Помогите Харшиту разобраться с этим вопросом.

$$$^{\text{∗}}$$$Для графа $$$G$$$ подмножество вершин $$$S$$$ называется независимым, если никакие две вершины из $$$S$$$ не соединены ребром.

$$$^{\text{†}}$$$Для графа $$$G$$$ подмножество вершин $$$S$$$ называется кликой, если каждая вершина из $$$S$$$ соединена ребром с каждой другой вершиной из $$$S$$$.

$$$^{\text{‡}}$$$Граф называется простым неориентированным, если его рёбра неориентированы и в нём нет петель и кратных рёбер.

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

Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 100$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.

Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$k$$$ ($$$1\leq n\leq 300, 1\leq k\leq 10$$$).

Далее описываются $$$k$$$ графов. Первая строка описания каждого графа содержит одно целое число $$$m$$$ ($$$0\leq m\leq \frac{n\cdot(n-1)}{2} $$$).

Следующие $$$m$$$ строк содержат по два разделённых пробелом целых числа $$$u$$$ и $$$v$$$ ($$$1\leq u, v\leq n, u\neq v$$$), обозначающих, что вершины $$$u$$$ и $$$v$$$ соединены ребром.

Гарантируется, что сумма $$$m$$$ по всем графам во всех наборах входных данных не превосходит $$$2\cdot 10^5$$$, а сумма $$$n$$$ по всем наборам входных данных не превосходит $$$300$$$.

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

Для каждого набора входных данных выведите «Yes», если существуют $$$k$$$ графов, удовлетворяющих условиям; иначе выведите «No».

Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.

Пример
Входные данные
3
5 2
3
3 4
5 3
5 1
6
3 5
3 4
1 4
1 2
2 3
4 2
4 3
0
3
3 1
1 4
1 2
4
4 2
4 3
1 2
2 3
3 2
0
3
3 1
3 2
1 2
Выходные данные
Yes
Yes
No
Примечание

Для первого набора входных данных ниже приведены графы $$$G_1, H_1$$$ и $$$G_2, H_2$$$, такие что $$$G_1$$$ — превосходный граф для $$$H_1$$$, а $$$G_2$$$ — превосходный граф для $$$H_2$$$.

В каждом графе вершина $$$2$$$ из $$$G_i$$$ соответствует независимому множеству $$$\{2\_1, 2\_2\}$$$ в соответствующем $$$H_i$$$, а остальные вершины $$$v\in\{1,3,4,5\}$$$ из $$$G_i$$$ соответствуют независимому множеству/клике $$$\{v\}$$$ в соответствующем $$$H_i$$$ (множество из одной вершины можно считать и независимым множеством, и кликой).

В третьем наборе входных данных можно доказать, что ответ — «No».