- 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 |