Ариан любит теорию графов больше всего на свете. Хотя нет, больше всего он любит хвастаться своей научной работой по линейным графам. Чтобы начать с вами разговор, он решил дать вам задачу на линейные графы. В математической дисциплине теории графов линейный граф простого неориентированного графа $$$G$$$ — это другой простой неориентированный граф $$$L(G)$$$, который отображает смежность между любыми двумя рёбрами в $$$G$$$.
Точнее говоря, для неориентированного графа $$$G$$$ без петель и кратных рёбер его линейный граф $$$L(G)$$$ определяется так:
- Каждая вершина $$$L(G)$$$ соответствует ребру графа $$$G$$$.
- Две вершины $$$L(G)$$$ соединены ребром тогда и только тогда, когда соответствующие им рёбра в $$$G$$$ имеют общую вершину.
Также $$$L^0(G)=G$$$, а $$$L^k(G)=L(L^{k-1}(G))$$$ для $$$k\geq 1$$$.
Эйлеров путь — это последовательность рёбер, проходящая по каждому ребру графа ровно один раз. Такой путь может быть либо путём (начинается и заканчивается в разных вершинах), либо циклом (начинается и заканчивается в одной и той же вершине). Вершины могут посещаться несколько раз, но каждое ребро должно быть использовано ровно один раз.
Ариан даёт вам простой связный граф $$$G$$$ с $$$n$$$ вершинами и $$$m$$$ рёбрами и целое число $$$k$$$. Гарантируется, что в $$$G$$$ существует эйлеров путь и что граф не является бамбуком$$$^{\text{∗}}$$$. Он просит вас определить, существует ли эйлеров путь в $$$L^k(G)$$$.
$$$^{\text{∗}}$$$Бамбук — это дерево, в котором каждая вершина соединена не более чем с двумя другими вершинами.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит три целых числа $$$n$$$, $$$m$$$ и $$$k$$$ ($$$5 \le n \le 2 \cdot 10^5$$$, $$$n-1 \le m \le \min(\frac{n\cdot(n-1)}{2} ,2 \cdot 10^5)$$$, $$$1 \le k \le 2 \cdot 10^5$$$).
Следующие $$$m$$$ строк каждого набора входных данных содержат по два целых числа $$$u$$$ и $$$v$$$ ($$$1 \le u,v \le n$$$, $$$u \neq v$$$), обозначающих, что вершины $$$u$$$ и $$$v$$$ соединены ребром.
Гарантируется, что сумма $$$n$$$ и $$$m$$$ по всем наборам входных данных не превосходит $$$2\cdot 10^5$$$.
Для каждого набора входных данных выведите «YES», если в $$$L^k(G)$$$ существует эйлеров путь; иначе выведите «NO».
Вы можете выводить каждую букву в любом регистре (строчную или заглавную). Например, строки «yEs», «yes», «Yes» и «YES» будут приняты как положительный ответ.
45 5 21 22 33 44 55 15 6 11 22 33 44 55 11 310 11 31 22 33 44 54 64 75 76 77 88 99 107 8 21 32 31 44 52 51 66 72 7
YES NO YES NO
В первом примере $$$L^2(G)$$$ изоморфен самому $$$G$$$. Поэтому, так как в $$$G$$$ существует эйлеров путь, то и в $$$L^2(G)$$$ он тоже существует.
Во втором примере $$$L(G)$$$ выглядит следующим образом (вершина $$$i-j$$$ в $$$L(G)$$$ на рисунке соответствует ребру между вершинами $$$i$$$ и $$$j$$$ в $$$G$$$). Можно доказать, что в этом графе эйлерова пути нет.
