Switch es el encargado del edificio Kase, sabe que los programadores estan en constante expansión, son demasiados!!!. Hay N programadores en el edifico y cada uno esta en una sola maquina. Las programadores se numeran por números enteros de 1 a N, ambos inclusive. Switch quiere garantizar la seguridad de las programadores de cada piso (seria una catastrofe si alguna de las programadores no puede salir). El quiere tener una salida de emergencia y quiere entrenar a las programadores a utilizar éstos mediante la realización de simulacros.

Switch sabe que el número de programadores que estan en el edificion puede ser muy grande. Con el fin de evitar la aglomeración de una ruta de escape de incendios común durante la emergencia, Switch ha decidido construir múltiples escaleras de incendios. Para la seguridad de todas las programadores, cada piso tiene una salida de incendios que está conectado a una de las rutas de emergencia.

Muchos de las programadores son amigos entre sí. La amistad es mutua. Esto significa que si programador $x_i$ es un amigo de la programador $x_j$ entonces programador $x_j$ es un amigo del programador $x_i$. Pero la amistad no es necesariamente transitiva. Esto significa que si programador $x_i$ es un amigo de $x_j$ y $x_j$ es un amigo de $x_k$, entonces $x_i$ no es necesariamente amigo de $x_k$.

Si dos programadores son amigos, no quieren escapar a través de diferentes rutas.

Esto complica la tarea para Switch. Como ya se ha mencionado, quiere tener el máximo número de rutas de escape de incendios para garantizar la máxima seguridad. Además, para cada ruta de escape, uno de las programadores que utilizan esa ruta tiene que ser nombrado capitán del simulacro. El capitán será responsable de la realización de los simulacros y capacitar a todos las programadores que utilizan esa ruta.

Su tarea es simple. Dado el número de programadores y la lista de amigos, es necesario decirle a Switch el número máximo de rutas de escape que puede tener en el edificio y el número de maneras de seleccionar los capitanes para cada ruta.

Ya que el número de formas puede ser muy grande, mostrar la módulo $10^{9} + 7$.

La primera línea de la entrada contiene un único entero T, que indica el número de casos de prueba. La descripción de casos de prueba T sigue. La primera línea de cada caso de prueba contiene dos números enteros separados por espacios N y M, que indica el número de programadores y el número de relaciones de amistad, respectivamente. Cada una de las siguientes líneas M contiene dos enteros i y j separados por espacios, que denota persona $x_i$ y persona $x_j$ son amigos.

Para cada caso de prueba, la salida de una sola línea que contiene dos enteros separados por espacios, que indica el número máximo de distintas rutas de escape de incendios que se pueden construir y el número de maneras de seleccionar los capitanes modulo $10^{9} + 7$.