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.