Hay un grafo no dirigido simple con ~N~ vértices y ~M~ aristas, donde los vértices están numerados de ~1~ a ~N~, y las aristas están numeradas de ~1~ a ~M~. La arista ~i~ conecta el vértice ~a_i~ y el vértice ~b_i~.

~K~ guardias de seguridad numerados de ~1~ a ~K~ están en algunos vértices. El guardia ~i~ está en el vértice ~p_i~ y tiene estamina de ~h_i~. Todos los ~p_i~ son distintos.

Un vértice ~v~ se dice que está resguardado cuando la siguiente condición es satisfecha:

• Hay al menos un guardia ~i~ tal que la distancia entre el vértice ~v~ y el vértice ~p_i~ es a los más ~h_i~.

Aquí, la distancia entre el vértice ~u~ y el vértice ~v~ es el mínimo número de aristas en el camino que conecta los vértices ~u~ y ~v~.

Muestre todos los vértices resguardados en orden ascendente.

Entrada

La primera línea contiene ~N~, ~M~ y ~K~ el número de vértices, el número de aristas, y el número de guardias.

Las siguientes ~M~ líneas contienen dos enteros ~a_i~ y ~b_i~ cada una, los pares de vértices conectados por cada arista.

Las siguientes ~K~ líneas contienen dos enteros ~p_i~ y ~h_i~ cada una, la posición y la estamina de cada uno de los guardias.

Salida

La primera línea contendrá el número de vértices que están resguardados.

La segunda línea contendrá ~v_1,v_2,...,v_G~, el número de los vértices que están resguardados, en orden ascendente.

Límites

• ~1 \le N \le 2*10^5~
• ~0 \le M \le min(N(N-1)/2,2*10^5)~
• ~1 \le K \le N~
• ~1 \le a_i,b_i \le N~
• El grafo dado es simple.
• ~1 \le p_i \le N~
• Todos los ~p_i~ son distintos.
• ~1 \le h_i \le N~
• Todos los valores de la entrada son enteros.

Subtareas:

• Subtarea 1 (40 pts.): ~N \le 1000~, ~M \le 2000~.
• Subtarea 2 (60 pts.): Sin restricciones adicionales.

Ejemplos

Entrada de ejemplo 1

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

Salida de ejemplo 1

4
1 2 3 5

Explicación ejemplo 1

Los vértices resguardados son ~1,2,3,5~.

Estos vértices están resguardados por las siguientes razones:

• La distancia entre el vértice ~1~ y el vértice ~p_1 = 1~ es ~0~, lo cual no es mayor que ~h_1 = 1~. Así, el vértice ~1~ está resguardado.
• La distancia entre el vértice ~2~ y el vértice ~p_1 = 1~ es ~1~, el cual no es mayor que ~h_1 = 1~. Así, el vértice ~2~ está resguardado.
• La distancia entre el vértice ~3~ y el vértice ~p_2 = 5~ es ~1~, el cual no es mayor que ~h_2 = 2~. Así, el vértice ~3~ está resguardado.
• La distancia entre el vértice ~5~ y el vértice ~p_1 = 1~ es ~1~, el cual no es mayor que ~h_1 = 1~. Así, el vértice ~5~ está resguardado.

Entrada de ejemplo 2

3 0 1
2 3

Salida de ejemplo 2

1
2

Explicación ejemplo 2

El grafo dado puede no tener aristas.

Entrada de ejemplo 3

10 10 2
2 1
5 1
6 1
2 4
2 5
2 10
8 5
8 6
9 6
7 9
3 4
8 2

Salida de ejemplo 3

7
1 2 3 5 6 8 9