Сізге ілмектері және еселік қабырғалары жоқ бағытталмаған граф берілген.

Графтың әрбір төбесіне теріс емес бүтін мән меншіктеңіз. Егер меншіктеу екі шартты қанағаттандырса, ол жарамды деп аталады:

• кез келген екі көршілес төбенің мәндері дәл $1$-ге ерекшеленеді;
• егер төбенің мәні оның барлық көршілерінің мәндерінен қатаң кіші болса, онда ол $0$-ге тең.

Жарамды меншіктеулер санын $998\,244\,353$ модулі бойынша табыңыз. Егер осы меншіктеулерде мәндері әртүрлі болатын төбе табылса, екі меншіктеу әртүрлі деп есептеледі.

Кіріс деректері

Бірінші жолда бір бүтін сан $t$ — тест жағдайларының саны берілген.

Әрбір тест жағдайының бірінші жолында екі бүтін сан $n$ және $m$ ($2 \le n \le 10^6$, $1 \le m \le 10^6$) — графтағы төбелер мен қабырғалар саны берілген.

Келесі $m$ жолдың әрқайсысында екі бүтін сан $u$ және $v$ ($1 \le u, v \le n$, $u \ne v$) — сәйкес қабырғаның ұштары берілген. Графта ілмектер немесе еселік қабырғалар жоқ. Әрбір төбенің кемінде бір көршісі бар.

Барлық тест жағдайлары бойынша $m$ мәндерінің қосындысы $10^6$-нен аспайды.

Шығыс деректері

Әрбір тест жағдайы үшін бір бүтін санды — жарамды меншіктеулер санын $998\,244\,353$ модулі бойынша шығарыңыз.

Мысал

Кіріс деректері 1

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

Шығыс деректері 1

6
0