Copiado al portapapeles
Descripción
A Gaussito le gustan las fiestas y sobre todo bailar (¡especialmente con Mikail y Mathzy!) y todos los demás en la fiesta también quieren bailar con el (se considera un gran honor).
La duración de las fiestas pueden ser cortas y no todas las personas llegan a bailar con Gaussito, así que solo queda conformarse con el numero ordinal de gran honor obtenido.
El numero de ordinal de gran honor se obtiene de la siguiente forma:
1. Bailar con Gaussito es el primer gran honor.
2. Bailar con alguien que ha bailado con Gaussito es el segundo gran honor.
3. Bailar con alguien que ha bailado con el que a bailado con Gaussito es el tercer gran honor, y asi sucesivamente.
A la fiesta asistirán $N$ personas y se formaran $M$ parejas de baile, cada persona tendrá un numero identificador único de $1$ a $N-1$, como Gaussito es el mas solicitado tendrá como numero identificador el numero $0$.
Tu trabajo es escribir un programa que calcule el numero ordinal de gran honor obtenido para todas las personas que asisten a la fiesta. Se garantiza que todas las personas que asistan a la fiesta bailaran minimamente con una persona.
Entrada
La primera línea de entrada consiste en un numero $T$ que representa el numero de casos de prueba ($1 \leq T \leq 100$).
Por cada caso de prueba dos enteros $N$ y $M$ que representa el numero de personas en la fiesta incluyendo a Gaussito, numero de parejas de baile (Rangos $N \leq 1000$, $M \leq \frac{N*(N-1)}{2})$.
Luego $M$ lineas cada una contiene las parejas de baile $m_{i}$ y $m_{j}$ que representa que la persona $m_{i}$ baila con la persona $m_{j}$ ($0 \leq m_{i}, m_{j} \leq (N-1)$).
Salida
Para cada caso de prueba imprimir el numero ordinal de gran honor obtenido de cada persona con identificador $1$ hasta $N-1$, cada caso consecutivo debe estar separado por una linea en blanco.
Ejemplo Entrada
1 5 6 0 1 0 2 3 2 2 4 4 3 1 2
Ejemplo Salida
1 1 2 2
Ayuda
No imprima un salto de linea extra para el ultimo caso de entrada.