Informática - Nível Intermediário - Semana 39

  1. Galeria de Arte

Em uma galeria de arte, há N espaços conectados por M corredores. Cada espaço é numerado de 1 a N e cada corredor liga dois espaços. Como as artes são muito preciosas, a galeria contratou K seguranças, numerados de 1 a K, para guardarem os espaços. O guarda i está no espaço p_i e consegue vigiar e guardar os espaços a uma distância de até h_i corredores da posição dele. É garantido que os p_i são diferentes para cada segurança i.

A sua tarefa é listar, em ordem crescente, todos os espaços que estão vigiados.

Entrada

A primeira linha contém três inteiros: N, M e K.

Cada uma das próximas M linhas contém dois inteiros a_i e b_i, indicando que há um corredor entre os espaços a_i e b_i.

Em seguida, nas K linhas seguintes, há dois inteiros p_i e h_i, indicando que há um guarda no espaço p_i com alcance de h_i.

Saída

Seu programa deve imprimir um inteiro G, representando a quantidade de espaços vigiados, ou seja, que estão sob a supervisão de um segurança.

Na próxima linha, imprima G inteiros em ordem crescente, representando os espaços vigiados.

Restrições

  • 1 \leq N \leq 200000
  • 0 \leq M \leq min(200000, N(N-1)/2)
  • 1 \leq K \leq N
  • 1 \leq a_i, b_i \leq N
  • 1 \leq p_i \leq N
  • 1 \leq h_i \leq N

Exemplo

Entrada Saída
5 5 2
1 2
2 3
2 4
3 5
1 5
1 1
5 2		 
4
1 2 3 5

Entrada Saída
3 0 1
2 3		 
1
2

Entrada Saída
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		 
7
1 2 3 5 6 8 9

Para submeter a sua solução, use esse link.