Bienvenue aux participants de l'APLSPC !
Comme chacun le sait, les données des compétitions sont générées la veille au soir.
Malheureusement, lors de la vérification des données d'un problème de théorie des graphes avant la NFLSPC, l'Empereur a découvert que les deux premières lignes de toutes les données avaient été supprimées par le maléfique petit P.
En observant les données incomplètes, l'Empereur se demande soudain combien il existe de manières de compléter les deux premières lignes pour que les données soient valides, modulo $998244353$.
Comme l'Empereur est l'Empereur, il vous confie le fichier d'entrée pour que vous résolviez ce problème.
L'Empereur, dans sa grande clémence, garantit qu'il existe au moins une manière valide de compléter les données.
Étant donné plusieurs lignes de données, déterminez combien de jeux de données complets existent tels que :
- Ces données, après suppression des deux premières lignes, correspondent exactement aux lignes données.
- Ces données respectent parfaitement le format d'entrée du problème original.
Le format d'entrée du problème original est le suivant :
La première ligne contient un entier positif $T$, suivi de $T$ jeux de données.
La première ligne de chaque jeu de données contient deux entiers positifs $n, m$.
Les $m$ lignes suivantes contiennent chacune deux entiers positifs $u, v\ (1\leq u, v\leq n)$, décrivant un graphe.
Le graphe peut ne pas être connexe, et peut contenir des arêtes multiples ou des boucles.
Les contraintes du problème original sont :
$1\le T \leq 2\times 10^5$ ;
$1\le n, m \leq 2\times 10^5$.
Entrée
Plusieurs lignes (au plus $2\times 10^5$ lignes), chaque ligne contenant deux entiers positifs.
Sortie
Une seule ligne contenant un entier positif, représentant le nombre de manières de compléter les données, modulo $998244353$.
Données
Pour toutes les données : tous les nombres en entrée sont dans l'intervalle $[1, 2\times 10^5]$, et le nombre de lignes lues ne dépasse pas $2\times 10^5$.
Exemples
Entrée 1
2 1 1 1
Sortie 1
199999