Informática - Nível Avançado - Semana 19

Cubra os Caminhos

É dada uma arvore bidirecional e sem pesos, consistindo de n vértices, numeradas de 1 à n. Um total de m caminhos simples são escolhidos nessa árvore, cada caminho sendo descrito como o par de vértices (a_i, b_i), seus pontos de início e fim.

Seja V o conjunto de todas as vértices da árvore. Chamaremos um subconjunto S contido em V de legal se, para cada i dos m caminhos,  ao menos um dos vértices do caminho entre a_i e b_i  esteja contido em S. Chamaremos um subconjunto T, contido em V de muito legal se T for um subconjunto legal, e não existe nenhum subconjunto legal X, tal que o número de elementos de X seja menor que o número de elementos de T

Encontre um subconjunto muito legal de V.

Entrada

A primeira linha contém, um inteiro n, o número de vértices.

Cada  uma das próximas n-1 linhas contém dois inteiros u_i e v_i, indicando que existe uma aresta entre u_i e v_iÉ garantido que essas arestas formam uma árvore.

A próxima linha contém um inteiro m, o número de caminhos escolhidos.

As próximas m linhas contém dois inteiros: a_i e b_i, os extremos do i- ésimo caminho. Podem existir caminhos iguais, e pode existir um caminho j, tal que a_j = b_j.

Saída

A primeira linha da saída deve conter um inteiro k, o tamanho de um subconjunto muito legal.

A segunda linha deve conter k inteiros, os números dos vértices contidos em um subconunto muito legal, em qualquer ordem.

Caso exista mais de um subconjunto muito legal, imprima qualquer um deles.

Restrições:

1 \leq n \leq 10^5

1 \leq m \leq 10^5

1 \leq u_i, v_i, a_i, b_i \leq 10^5

Exemplos:

Entrada Saida
4
1 2
2 3
2 4
2
1 2
4 2
1
2
Entrada Saida
6
1 2
2 3
3 4
5 6
5 2
5
2 1
6 6
1 4
3 4
4 1
3
6 3 1

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