Consideremos un grafo no dirigido compuesto por ~n~ nodos y ~m~ aristas. Pueden ocurrir dos tipos de eventos:

1. Se crea una nueva arista entre los nodos ~a~ y ~b~.
2. Se elimina una arista existente entre los nodos ~a~ y ~b~.

Tu tarea consiste en informar el número de componentes después de cada evento.

Entrada

La primera línea de entrada contiene tres números enteros: ~n, m~ y ~k~: el número de nodos, aristas y eventos.

A continuación, hay ~m~ líneas que describen las aristas. Cada línea contiene dos números enteros, ~a~ y ~b~: existe una arista entre los nodos ~a~ y ~b~. Existe como máximo una arista entre cualquier par de nodos.

Luego, hay ~k~ líneas que describen los eventos. Cada línea tiene la forma "t a b", donde ~t~ es ~1~ (crea una nueva arista) ó ~2~ (elimina una arista). Siempre se crea una nueva arista entre dos nodos que no tienen una arista existente, y solo se pueden eliminar aristas existentes.

Salida

Imprime ~k+1~ enteros: primero, el número de componentes antes del primer evento, y después, el nuevo número de componentes tras cada evento.

Restricciones

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

Ejemplo de Entrada

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

Ejemplo de Salida

2 2 2 1