Grover e Seus Caminhos Especiais
Grover é um cientista da computação indo-americano que quer propor um algoritmo de busca quântica que oferece uma aceleração quadrática em relação aos algoritmos de busca clássicos para bancos de dados não estruturados. Para isso, ele precisa resolver um problema em árvores que faz parte de sua pesquisa para desenvolver o seu algoritmo.
Grover tem uma árvore com $N$ vértices e $N − 1$ arestas não direcionadas, e tem como objetivo atribuir para cada vértice um valor vi satisfazendo algumas restrições:
- 1 ≤ $v_i$ ≤ 5
- Existem exatamente $cnt_x$ vértices com o valor $v_i = x$, para $1 ≤ x ≤ 5$
- Para cada vértice $i$ existe um conjunto de valores que o valor de $v_i$ pode assumir
- Além disso, nessa árvore existem $P$ caminhos especiais para Grover, um caminho especial é representado por um par de vértices $(X_i , Y_i )$ (os caminhos podem ter intersecção e um caminho pode aparecer mais de uma vez na entrada) e para esses caminhos os valores atribuídos aos vértices no caminho (na ordem de $X_i$ para $Y_i$ ) têm que formar uma sequência estritamente crescente.
Se existir uma solução válida, imprima qualquer uma que satisfaça as restrições impostas por Grover, caso contrário, imprima -1.
Input
A primeira linha da entrada vai conter um inteiro $N$ $(1 ≤ N ≤ 5·10^4 )$, a quantidade de vértices da árvore. A segunda linha da entrada vai conter 5 números inteiros, os valores de $cnt_1 , cnt_2 , cnt_3 , cnt_4 , cnt_5$ respectivamente. É garantido que a soma $cnt_1 + cnt_2 + cnt_3 + cnt_4 + cnt_5 = N$.
As próximas $N$ linhas da entrada começam com um número inteiro $M_i$ $(1 ≤ M_i ≤ 5)$, seguidos de $M_i$ inteiros distintos entre 1 e 5, indicando os valores que o i-ésimo vértice pode assumir. Seguem $N − 1$ linhas, cada uma com dois números $U, V$ $(1 ≤ U, V ≤ N )$ indicando uma aresta da árvore.
Em seguida, haverá uma linha com um único número inteiro $P$ $(1 ≤ P ≤ 5)$, indicando a quantidade de caminhos especiais. Por fim, as próximas $P$ linhas da entrada vão conter dois números $X_i , Y_i$ $(1 ≤ X_i , Y_i ≤ N )$, indicando os caminhos especiais.
Output
Caso exista solução imprima $N$ inteiros $v_1 , v_2 , ..., v_n$ indicando uma solução válida para o problema.
Caso contrário, imprima -1. Se existirem múltiplas respostas válidas, qualquer uma será aceita.
10 1 1 4 2 2 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 6 5 4 5 3 5 8 3 10 10 9 9 1 3 7 10 2 5 7 1 3 10 10 2 5 6 7 6
5 4 2 3 3 5 1 3 4 3
6 1 1 1 1 2 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 5 1 2 3 4 5 1 2 2 3 3 4 4 5 5 6 1 1 6
-1
1 0 0 0 0 1 4 1 2 3 4 1 1 1
-1
10 2 1 4 1 2 5 1 2 3 4 5 4 1 2 3 5 1 3 3 2 4 5 2 4 5 1 3 5 1 2 3 4 5 3 1 2 3 1 4 2 1 5 8 5 5 2 8 9 9 10 8 4 4 1 1 6 9 3 4 7 4 7 10 1 4 6 6 7 10
1 3 3 2 5 3 1 3 4 5