Gegeben ist ein ungerichteter Graph ohne Schleifen oder Mehrfachkanten.

Ordne jedem Knoten des Graphen einen nichtnegativen ganzzahligen Wert zu. Eine Zuweisung ist gültig, wenn sie zwei Bedingungen erfüllt:

• je zwei benachbarte Knoten haben Werte, die sich um genau $1$ unterscheiden;
• wenn der Wert eines Knotens echt kleiner ist als die Werte aller seiner Nachbarn, dann ist er gleich $0$.

Finde die Anzahl der gültigen Zuweisungen modulo $998\,244\,353$. Zwei Zuweisungen sind verschieden, wenn es einen Knoten gibt, der in diesen Zuweisungen unterschiedliche Werte hat.

Eingabe

Die erste Zeile enthält eine ganze Zahl $t$, die Anzahl der Testfälle.

Die erste Zeile jedes Testfalls enthält zwei ganze Zahlen $n$ und $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$): die Anzahl der Knoten und Kanten im Graphen.

Jede der nächsten $m$ Zeilen enthält zwei ganze Zahlen $u$ und $v$ ($1 \le u, v \le n$, $u \ne v$): die Endpunkte der entsprechenden Kante. Der Graph enthält weder Schleifen noch Mehrfachkanten. Jeder Knoten hat mindestens einen Nachbarn.

Die Summe von $m$ über alle Testfälle hinweg überschreitet nicht $10^6$.

Ausgabe

Gib für jeden Testfall eine ganze Zahl aus: die Anzahl der gültigen Zuweisungen modulo $998\,244\,353$.

Beispiel

Eingabe 1

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

Ausgabe 1

6
0