Dla danego grafu nieskierowanego znajdź minimalne pokrycie wierzchołkowe. Szalone, prawda?

Niech $M$ będzie rozmiarem maksymalnego skojarzenia, a $C$ rozmiarem minimalnego pokrycia wierzchołkowego. Jeśli minimalne pokrycie wierzchołkowe jest "smol", co oznacza $C \le M + 1$, to znajdź je.

Wejście

Każdy test zawiera wiele przypadków testowych. Pierwsza linia zawiera liczbę przypadków testowych $T$ ($1 \le T \le 10^4$).

Dalej następuje opis przypadków testowych.

Pierwsza linia każdego przypadku testowego zawiera dwie liczby całkowite $n$ oraz $m$ ($1 \le n \le 500$, $0 \le m \le \frac{n(n-1)}{2}$) — liczbę wierzchołków oraz krawędzi w grafie.

Kolejne $m$ linii opisuje krawędzie grafu, każda z nich zawiera dwie liczby całkowite $u$ oraz $v$ ($1 \le u < v \le n$) — wierzchołki połączone krawędzią. Wierzchołki są numerowane od $1$ do $n$.

Gwarantuje się, że graf nie zawiera wielokrotnych krawędzi.

Gwarantuje się, że suma $n^2$ we wszystkich przypadkach testowych nie przekracza $250\,000$.

Wyjście

Dla każdego przypadku testowego, jeśli minimalne pokrycie wierzchołkowe jest "smol", wypisz jego rozmiar $C$ w pierwszej linii, a następnie $C$ różnych, oddzielonych spacjami wierzchołków tworzących pokrycie wierzchołkowe w drugiej linii. W przeciwnym razie wypisz "not smol" w pojedynczej linii (bez cudzysłowów).

Jeśli istnieje kilka możliwych minimalnych pokryć wierzchołkowych typu "smol", wypisz dowolne z nich.

Przykład

Wejście 1

1
5 5
1 2
2 3
3 4
4 5
1 5

Wyjście 1

3
2 3 5

Wejście 2

2
3 0
5 10
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

Wyjście 2

0
not smol

Uwagi

Pokrycie wierzchołkowe to zbiór wierzchołków taki, że dla każdej krawędzi przynajmniej jeden z jej końców należy do tego zbioru.

Skojarzenie to zbiór krawędzi taki, że żadne dwie krawędzie z tego zbioru nie mają wspólnego końca.

Zauważ, że minimalne pokrycie wierzchołkowe nie zostanie zaakceptowane jako poprawna odpowiedź, jeśli nie jest ono "smol".