Zadanie

Ja chcem bývať tu

Počet bodov: 60

Možno, že celoštátko bude prezenčne. Mali by sme sa na to pripraviť. Izby pre súťažiatká sú jednolôžkové a sú za radom, jedna vedľa druhej. Keďže steny sú tenké, každé ubytované súťažiatko cíti prítomnosť toho s kým susedí. Súťažiatko je spokojné, ak aspoň v jednej zo susedných izieb býva niekto z jeho kraja. Súťažiatok je \(n\), rovnako ako izieb. Dávid chce, aby aspoň niektoré súťažiatko bolo spokojné. Zaujíma ho preto, koľkými spôsobmi ich vie rozmiestniť do izieb tak, aby existovali dve susedné izby, v ktorých bývajú súťažiatka z rovnakého kraja.

Vstup a výstup

Na prvom riadku vstupu je číslo \(T\) – počet testov. Nasleduje \(T\) testov. Platí \(1 \leq T \leq 30\).

Na prvom riadku testu sú čísla \(n\) – počet súťažiacich osôb (aj počet izieb) a \(m\) – počet dvojíc, o ktorých viete, že sú z rovnakého kraja. Súťažiatká sú očíslované od \(1\) do \(n\). Platí \(1 \leq n \leq 30\) a \(0 \leq m \leq 800\).

Nasleduje \(m\) riadkov. Na \(i\)-tom z nich sa nachádzajú dve čísla \(a_i\), \(b_i\). Tie hovoria, že súťažiatká \(a_i\) a \(b_i\) sú z toho istého kraja. Platí \(1 \leq a_i, b_i \leq n\).

Ak vieme že \(a\) a \(b\) sú z toho istého kraja, a zároveň že \(b\) a \(c\) sú z toho istého kraja, tak určite aj \(a\) a \(c\) sú z toho istého kraja.

Hodnotenie

Sú 3 sady vstupov. V jednej z nich navyše platí \(4 \leq n \leq 8\). V inej naviac platí \(1 \leq n \leq 20\).

Príklad

Input:

3
4 4
4 4
1 2
2 2
1 2
7 2
6 6
1 5
4 3
3 3
4 2
4 4

Output:

12
1440
12