Cubra os Caminhos
É dada uma arvore bidirecional e sem pesos, consistindo de vértices, numeradas de à . Um total de caminhos simples são escolhidos nessa árvore, cada caminho sendo descrito como o par de vértices , seus pontos de início e fim.
Seja o conjunto de todas as vértices da árvore. Chamaremos um subconjunto contido em de se, para cada dos caminhos, ao menos um dos vértices do caminho entre e esteja contido em . Chamaremos um subconjunto , contido em de se for um subconjunto , e não existe nenhum subconjunto , tal que o número de elementos de seja menor que o número de elementos de
Encontre um subconjunto de .
Entrada
A primeira linha contém, um inteiro , o número de vértices.
Cada uma das próximas linhas contém dois inteiros e , indicando que existe uma aresta entre e . É garantido que essas arestas formam uma árvore.
A próxima linha contém um inteiro , o número de caminhos escolhidos.
As próximas linhas contém dois inteiros: e , os extremos do - ésimo caminho. Podem existir caminhos iguais, e pode existir um caminho , tal que .
Saída
A primeira linha da saída deve conter um inteiro , o tamanho de um subconjunto .
A segunda linha deve conter inteiros, os números dos vértices contidos em um subconunto , em qualquer ordem.
Caso exista mais de um subconjunto , imprima qualquer um deles.
Restrições:
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.