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.