Hay $n$ invitados en una fiesta. Cada uno tiene 2 aficiones diferentes. No hay dos invitados con el mismo conjunto de aficiones. El anfitrión quiere dividirlos en grupos de 2 o 3 personas de modo que cualesquiera dos invitados de un mismo grupo tengan una afición en común. Es decir, cada grupo pertenece a uno de los siguientes casos:

• Tipo A: un grupo de dos invitados que tienen una afición en común;

• Tipo B: un grupo de tres invitados que tienen todos una afición en común;

• Tipo C: un grupo de tres invitados en el que cada pareja tiene una afición en común, excluyendo el caso del tipo B.

El anfitrión quiere reducir al mínimo posible el número $\alpha$ de invitados que no están asignados a ningún grupo. Si hay varias soluciones con el mínimo $\alpha$, debemos encontrar una que minimice el número $\beta$ de grupos del tipo B usados, manteniendo $\alpha$ mínimo. Escribe un programa que determine estos dos números.

Figura 15: La imagen muestra dos soluciones diferentes del tercer caso de prueba. La solución de la derecha no usa ningún grupo del tipo B, por lo que es mejor que la de la izquierda.

Entrada

Cada caso de prueba consta de $n+1$ líneas. La primera contiene dos enteros $n,h$. A continuación hay $n$ líneas. La línea $(i+1)$ contiene dos enteros $x,y$ con $1 \le x,y \le h$, que indican que el $i$-ésimo invitado tiene las aficiones $x$ e $y$.

Restricciones

• $2 \le n \le 10^6$.

• $3 \le h \le 2n$.

Salida

Encuentra la mejor solución e imprime el número $\alpha$ de invitados no asignados y el número $\beta$ de grupos del tipo B usados en ella. Ten en cuenta que el objetivo es minimizar primero $\alpha$ y después minimizar $\beta$, manteniendo $\alpha$ en su mínimo posible.

Ejemplos

Entrada 1

2 4
1 2
3 4

Salida 1

2 0

Entrada 2

2 3
1 2
3 1

Salida 2

0 0

Entrada 3

5 5
1 2
2 3
2 4
5 2
5 4

Salida 3

0 0