Problema C - Topografia dos Onimalaias

Há cerca de 2500 anos, o povo dos Onilónios habitava a cordilheira dos Onimalaias: uma fila de N montanhas com alturas entre os 1 e os N metros. Os Onilónios possuíam um vasto conhecimento da topografia da região, mas a sua falta de habilidade a programar impossibilitava-os de utilizar os seus conhecimentos para determinar a altura exata de cada uma das montanhas. Hoje vamos finalmente usar os dados recolhidos pelos Onilónios para fazer isso.

Temos ao nosso dispor um relatório com Q medições, cada uma com um trio de inteiros (A, B) - D, significando isto que as alturas das montanhas nas posições A e B diferem em exatamente D metros, ou seja, ou a montanha B é D metros mais alta do que a montanha A, ou é D metros mais baixa.

Sobre as medições sabemos também que não existem ciclos de medições. Isto é, para todo RN, temos a certeza de que não existem R inteiros A1, A2, ..., AR tais que temos medições sobre cada um dos pares (A1, A2), (A2, A3), ..., e (AR, A1).

Vamos supor que N = 4, Q = 3 e temos as medições (1, 2) - 2, (2, 3) - 1, (3, 4) - 2. Então, as seguintes sequências de alturas são possíveis:

1 3 2 4, 1 3 4 2, 2 4 3 1, 3 1 2 4, 4 2 1 3, 4 2 3 1.

Assim sendo, qualquer uma delas seria uma resposta correta. A imagem seguinte mostra as diferenças entre os valores para cada medição para a primeira sequência:

Se mais do que uma sequência de alturas for consistente com as medições, qualquer uma será aceite, ou seja, podem responder qualquer sequência de alturas que seja consistente (se existir). Se nenhuma sequência de alturas o for, devem apenas imprimir -1.

O Problema

Dados dois inteiros N e Q, representando o número de montanhas e medições, e Q trios de medições da forma Ai Bi Di, pretende-se encontrar uma sequência de N inteiros tal que para cada um dos trios, o valor absoluto da diferença entre o elementos Ai e Bi da sequência é exatamente Di. Se várias sequências cumprirem as medições, a resposta deverá ser qualquer uma dessas sequências. Se nenhuma o fizer, a resposta pretendida é -1.

Input

Nota: este problema contém múltiplos inputs por caso de teste! Isto significa que terás de devolver a resposta para vários conjuntos de medições com o teu programa.

A primeira linha contém um inteiro, T, que representa o número de inputs. Seguem-se T conjuntos de inputs onde cada um tem o seguinte formato:

Primeiro contêm uma linha com dois inteiros separados por espaços, N e Q, representando o número de montanhas/tamanho máximo de cada montanha e o número de medições.

Seguem-se Q linhas, cada uma com três inteiros separados por espaços, Ai Bi Di, representando cada medição.

Notem que não há medições repetidas e não há ciclos nas medições. Por exemplo, (1, 2) - 3, (1, 2) - 1, (2, 1) - 2 são medições repetidas, apenas uma das três pode aparecer num caso de teste.

Output

Para cada um dos T inputs deves imprimir uma linha contendo uma de duas coisas:

Restrições

São garantidos os seguintes limites em todos os casos de teste que irão ser colocados ao programa:

1 ≤ T ≤ 10 Número de inputs por caso de teste
1 ≤ Q < N ≤ 2 000 Número de medições e número de montanhas/tamanho máximo de cada montanha
1 ≤ Ai, Bi ≤ N Índices de medições
0 ≤ Di ≤ N - 1 Distâncias de medições

Os casos de teste deste problema estão organizados em 6 grupos com restrições adicionais diferentes:

Grupo Número de Pontos Restrições adicionais
1 5 N ≤ 8
2 10 Q = 1
3 15 Q = 2
4 20 N ≤ 100, as medições formam uma linha *
5 20 as medições formam uma linha *
6 30 -

* As restrições formarem uma linha significa que existem R inteiros A1, A2, ..., AR tais que as medições são da forma (A1, A2), (A2, A3), ..., e (AR-1, AR). Equivalentemente, todos os índices estão em duas ou zero medições exceto dois índices que estão em apenas uma medição.

Input do Exemplo 1

1
4 3
1 2 2
2 3 1
3 4 2

Output do Exemplo 1

1 3 2 4

Explicação do Exemplo 1

Este exemplo corresponde ao mencionado no enunciado. Notem que, 1 3 4 2, 2 4 3 1, 3 1 2 4, 4 2 1 3, 4 2 3 1 também seriam soluções válidas.

Input do Exemplo 2

4
4 2
2 3 1
3 4 2
4 1
1 4 3
4 1
1 2 0
4 3
1 2 3
2 3 2
3 4 3     

Output do Exemplo 2

1 1 2 4
4 2 2 1
1 1 1 1
-1

Explicação do Exemplo 2

Notem que existem mais soluções válidas para os 3 inputs onde é a reposta é uma sequência.


Final Nacional das ONI'2019
Centro de Congressos da Alfândega do Porto
(1 de Abril de 2019)