Una red mesh es un conjunto de routers inalámbricos (wifi) interconectados entre sí inalambricamente haciendo uso de diferentes protocolos. Esta red puede cubrir grandes áreas como ciudades completas o barrios (haciendo uso de antenas y routers en el techo de edificios) de tal forma que todas las personas conectadas en esta área puedan comunicarse. Una persona puede conectar su celular o laptop a estos routers y podrá comunicarse con todas las personas conectadas dentro del área de la red mesh.

Una de las ventajas de este tipo de redes es la capacidad de ser descentralizada. Si existe una gran cantidad de routers conectados y la conexión entre dos de estos cae, esto no debería afectar a la red, es decir, una máquina o un router conectado a la mesh aún debería tener la capacidad comunicarse con cualquier otra máquina o router conectado a la mesh. Por otro lado, si la comunicación entre dos routers cae y esto sí afecta a que a una máquina o router no pueda comunicarse con cualquier otra máquina o router conectado a la mesh, entonces esta red no es descentralizada.

Un grupo de hackers en la ciudad de Río Fugitivo decidió implementar una red mesh. Tras días de trabajo, la red por fín está lista. Con el objetivo de tener una red descentralizada en la que cualquier persona pueda: conectarse, montar servicios, compartir información, jugar, etc. Para asegurar la descentralización de la red y su calidad, es necesario hacer pruebas cada cierto tiempo. Las pruebas que los hackers hacen son de la siguiente forma.

• Se hace ping entre dos nodos seleccionados aleatoriamente para ver si existe conexión.

• A veces ocurre que algunos nodos de la mesh caen.

• También, otras veces pero lamentablemente con menos frecuencia, nuevos nodos son creados.

Inicialmente los hackers realizaban estas pruebas manualmente, pero con el pasar del tiempo la red mesh creció demasiado, ahora existen demasiados routers conectados! Es por ello que este grupo de hackers necesita automatizar estas pruebas y generar un reporte para ver si la red mesh es descentralizada. Es por ello que debes aplicar tus conocimientos de programación para automatizar este proceso.

nota las variables deben ser a1, a2, a3... (en orden).

Una red mesh es un conjunto de routers inalámbricos (wifi) interconectados entre sí inalambricamente haciendo uso de diferentes protocolos. Esta red puede cubrir grandes áreas como ciudades completas o barrios (haciendo uso de antenas y routers en el techo de edificios) de tal forma que todas las personas conectadas en esta área puedan comunicarse. Una persona puede conectar su celular o laptop a estos routers y podrá comunicarse con todas las personas conectadas dentro del área de la red mesh.

Figura 1. Diagrama de una posible configuración de una red mesh.

Una de las ventajas de este tipo de redes es la capacidad de ser descentralizada. Si existe una gran cantidad de routers conectados y la conexión entre dos de estos cae, esto no debería afectar a la red, es decir, una máquina o un router conectado a la mesh aún debería tener la capacidad comunicarse con cualquier otra máquina o router conectado a la mesh. Por otro lado, si la comunicación entre dos routers cae y esto sí afecta a que a una máquina o router no pueda comunicarse con cualquier otra máquina o router conectado a la mesh, entonces esta red no es descentralizada.

Un grupo de hackers en la ciudad de Río Fugitivo decidió implementar una red mesh. Tras días de trabajo, la red por fín está lista. Con el objetivo de tener una red descentralizada en la que cualquier persona pueda: conectarse, montar servicios, compartir información, jugar, etc. Para asegurar la descentralización de la red y su calidad, es necesario hacer pruebas cada cierto tiempo. Las pruebas que los hackers hacen son de la siguiente forma.

• Se hace ping entre dos nodos seleccionados aleatoriamente para ver si existe conexión.

• A veces ocurre que algunos nodos de la mesh caen.

• También, otras veces pero lamentablemente con menos frecuencia, nuevos nodos son creados.

Inicialmente los hackers realizaban estas pruebas manualmente, pero con el pasar del tiempo la red mesh creció demasiado, ahora existen demasiados routers conectados! Es por ello que este grupo de hackers necesita automatizar estas pruebas y generar un reporte para ver si la red mesh es descentralizada. Es por ello que debes aplicar tus conocimientos de programación para automatizar este proceso.

La entrada consta de T casos de prueba ($1 \leq T \leq 10$). Cada caso de prueba inicia con dos números R y C ($2 \leq R,C \leq 10^5$) que representan la cantidad de routers y la cantidad de enlaces iniciales entre estos dispositivos. Luego debes leer C pares de enteros a, b ($0 \leq a, b < R$) que indican las conexiones iniciales entre los nodos.

A continuación serán introducidos una serie de comandos cuya cantidad no exederá $10^5$, los cuales podrían ser:

• “PING a b” Este comando indica que se está probando la conexión entre el nodo a y el nodo b.

• “RM c” Cuando este comando es introducido, significa que el nodo c ya no existe en la mesh.

• “ADD $x_1$ $x_2$ $x_n$” El comando “ADD” añade un nodo nuevo a la mesh. Al nuevo nodo le corresponde el valor que le continúa a la cantidad de nodos que existen. Por ejemplo, si existen ya n nodos etiquetados del 0 al n-1, la etiqueta del nuevo nodo será n. Los valores que preceden al comando son los nodos con los que tiene conexión el nuevo nodo.

• “EXIT” Indica el fin de los comandos.

Lamentablemente la cantidad de nuevos nodos en la mesh es mucho menor a la cantidad de los nodos que desaparecen. Se sabe que la cantidad de comandos “ADD” no superan los 10 en cada caso de prueba.

Por cada caso de entrada debes imprimir dos líneas con las siguientes oraciones en el idioma inglés.

“X successful tests”
“Y failed tests”

Donde debes reemplazar en “X” la cantidad de pruebas que fueron exitosas, y en “Y” la cantidad de pruebas que fallaron. Es indistinta la frase en caso de que la cantidad de tests exitosos o fallidos sea solo uno.