Киараш собирает себе домой клубнику...
Граф называется сладким, если и только если степень каждой вершины в нём не превосходит $$$2$$$.
Вам дан простой, неориентированный связный граф $$$G$$$ из $$$n\le 30$$$ вершин, обладающий особым свойством: каждая вершина принадлежит не более чем $$$5$$$ простым циклам$$$^{\text{∗}}$$$.
Каково максимальное количество рёбер среди всех подграфов$$$^{\text{†}}$$$ графа $$$G$$$, которые являются сладкими?
$$$^{\text{∗}}$$$Простой цикл — это связный подграф, в котором степень каждой вершины равна $$$2$$$.
$$$^{\text{†}}$$$Подграф графа $$$G$$$ — это граф, вершины и рёбра которого являются подмножествами $$$G$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 50$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Первая строка каждого набора входных данных содержит два целых числа $$$n$$$ и $$$m$$$ ($$$3 \leq n \leq 30$$$, $$$n-1 \leq m \leq \frac{n(n-1)}{2}$$$) — количество вершин и количество рёбер.
Затем следуют $$$m$$$ строк, в $$$i$$$-й строке содержатся два целых числа $$$u$$$ и $$$v$$$ ($$$1 \leq u, v \leq n$$$) — две вершины, которые соединяет $$$i$$$-е ребро.
Гарантируется, что данный граф простой и связный, и что каждая вершина принадлежит не более чем $$$5$$$ простым циклам.
Гарантируется, что сумма значений $$$n^2$$$ по всем наборам входных данных не превосходит $$$900$$$.
Для каждого набора входных данных выведите одно целое число — максимальное количество рёбер среди всех подграфов, которые являются сладкими графами.
34 41 21 32 33 47 101 21 31 42 43 44 54 65 65 76 79 101 21 33 43 74 54 65 67 87 98 9
3 7 8
В первом наборе входных данных вы можете выбрать рёбра, отмеченные на изображении ниже. Вы не можете выбрать все рёбра, потому что степень вершины $$$3$$$ превысит $$$2$$$. Таким образом, максимальное количество рёбер среди всех подграфов, которые являются сладкими, равно $$$3$$$.
Во втором наборе входных данных вы можете выбрать рёбра, отмеченные на изображении ниже. Можно доказать, что любой подграф, который является сладким, имеет не более $$$7$$$ рёбер.
В третьем наборе входных данных изображение ниже показывает один из подграфов с максимальным возможным количеством рёбер, который является сладким.
