Hay ~n~ ciudades e inicialmente no hay carreteras entre ellas. Sin embargo, cada día se construirá una nueva carretera y habrá un total de ~m~ carreteras.

Un componente es un grupo de ciudades en el que existe una ruta entre dos ciudades cualesquiera utilizando las carreteras. Después de cada día, tu tarea es encontrar el número de componentes y el tamaño del componente más grande.

Entrada

La primera línea de entrada tiene dos números enteros ~n~ y ~m~: el número de ciudades y de carreteras. Las ciudades se numeran ~1,2,\dots,n~. A continuación, hay ~m~ líneas que describen las nuevas carreteras. Cada línea tiene dos enteros ~a~ y ~b~: se construye una nueva carretera entre las ciudades ~a~ y ~b~. Puedes suponer que cada carretera se construirá entre dos ciudades diferentes.

Salida

Imprime ~m~ líneas: la información requerida después de cada día.

Restricciones

• ~1 \leq n \leq 10^5~
• ~1 \leq m \leq 2 \cdot 10^5~
• ~1 \leq a,b \leq n~

Ejemplo de Entrada

5 3
1 2
1 3
4 5

Ejemplo de Salida

4 2
3 3
2 3