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

4
1 2 3 5

1
2

7
1 2 3 5 6 8 9

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