Annettuna on suuntaamaton verkko, jossa ei ole silmukoita eikä moninkertaisia kaaria.

Aseta verkon jokaiselle solmulle epänegatiivinen kokonaislukuarvo. Sijoitus on kelvollinen, jos se täyttää kaksi ehtoa:

• minkä tahansa kahden vierekkäisen solmun arvot eroavat toisistaan täsmälleen $1$:llä;
• jos solmun arvo on aidosti pienempi kuin sen kaikkien naapureiden arvot, niin se on yhtä suuri kuin $0$.

Laske kelvollisten sijoitusten lukumäärä modulo $998\,244\,353$. Kaksi sijoitusta ovat erilaisia, jos on olemassa solmu, jolla on eri arvot näissä sijoituksissa.

Syöte

Ensimmäinen rivi sisältää kokonaisluvun $t$, testitapausten lukumäärän.

Jokaisen testitapauksen ensimmäinen rivi sisältää kaksi kokonaislukua $n$ ja $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$): verkon solmujen ja kaarien lukumäärät.

Jokainen seuraavista $m$ rivistä sisältää kaksi kokonaislukua $u$ ja $v$ ($1 \le u, v \le n$, $u \ne v$): vastaavan kaaren päätepisteet. Verkko ei sisällä silmukoita eikä moninkertaisia kaaria. Jokaisella solmulla on vähintään yksi naapuri.

Lukujen $m$ summa yli kaikkien testitapausten ei ylitä arvoa $10^6$.

Tuloste

Tulosta jokaiselle testitapaukselle yksi kokonaisluku: kelvollisten sijoitusten lukumäärä modulo $998\,244\,353$.

Esimerkki

Syöte 1

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

Tuloste 1

6
0