Problema C - Síntese de Proteínas

Nos laboratórios das ONI estudam-se vários tópicos de várias áreas. Recentemente tem havido um grande interesse em sintetizar proteínas. Uma proteína é dada por um conjunto de aminoácidos que contêm ligações entre pares de aminoácidos. Uma proteína tem ainda de ser conexa, ou seja, para cada par de aminoácidos existe uma sequência de ligações que os junta.

Um grau de liberdade de uma proteína é um conjunto de aminoácidos (possivelmente vazio) tal que não existe nenhuma ligação entre quaisquer dois aminoácidos desse conjunto.

Por exemplo, consideremos uma proteína com 4 aminoácidos numerados de 1 a 4, com ligações entre os aminoácidos (1, 2), (2, 3), e (3, 4). A imagem a baixo representa esta proteína.

Então esta proteína tem 8 graus de liberdade, dados pelos seguintes conjuntos: {}, {1}, {2}, {3}, {4}, {1, 3}, {1, 4}, {2, 4}. A imagem a baixo representa estas configurações.

Parte I

Queremos sintetizar uma proteína de tipo X. Estas proteínas podem ter qualquer número de aminoácidos entre 1 e 1 000 e qualquer número de ligações, mas um aminoácido só pode estar ligado a no máximo dois outros aminoácidos.

Serão dados Q pedidos de sintetizar uma proteína do tipo X. Cada pedido consiste num inteiro K_i e para cada um deves produzir uma proteína de tipo X com exatamente K_i graus de liberdade ou indicar que não é possível.

Exemplo

Se Q = 2 e tivermos os seguintes pedidos:

• K₁ = 9
• K₂ = 8

Para o primeiro pedido não existe nenhum tipo de proteína de tipo X com 9 graus de liberdade. Para o segundo pedido o exemplo anterior satisfaz este critério e é do tipo X.

Restrições:

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

Os casos de teste desta parte do problema estão organizados em dois grupos:

Parte II

Queremos sintetizar uma proteína de tipo Z. Estas proteínas podem ter qualquer número de aminoácidos entre 1 e 1 000 e qualquer número de ligações, mas não podem conter qualquer ciclo, ou seja, não podem conter uma sequência de ligações entre aminoácidos distintos que começa e termina no mesmo aminoácido.

Serão dados Q pedidos de sintetizar uma proteína do tipo X. Cada pedido consiste num inteiro K_i e para cada um deves produzir uma proteína de tipo Z com exatamente K_i graus de liberdade ou indicar que não é possível.

Exemplo

Se Q = 2 e tivermos os seguintes pedidos:

• K₁ = 7
• K₂ = 8

Para o primeiro pedido não existe nenhum tipo de proteína de tipo Z com 7 graus de liberdade. Para o segundo pedido o exemplo anterior satisfaz este critério e é do tipo Z.

Restrições:

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

Os casos de teste desta parte do problema estão organizados em dois grupos:

Sumário de subtarefas

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

Input

A primeira linha contém um inteiro P, que representa a parte que o caso de teste representa. Se for 1, então o caso de teste refere-se à Parte I, se for 2 então refere-se à Parte II.

Segue-se uma linha com um inteiro Q, representando o número de pedidos.

Seguem-se Q linhas, cada uma contendo um inteiro K_i, que representa o número de graus de liberdade pedido.

Output

O output deve conter Q secções.

Para a i-ésima secção, se não existir uma proteína com K_i graus de liberdade (do tipo indicado pela Parte) então a secção deve conter apenas o inteiro -1. Caso contrário, a secção deve conter primeiro dois inteiros N e M, representando o número de aminoácidos e de ligações, respetivamente. Devem seguir-se M linhas, cada uma com um par de inteiros entre 1 e N representando ligações entre dois aminoácidos.

Nota: podem existir vários outputs válidos, todos serão considerados corretos.

Nota: para todos os outputs N deve ser entre 1 e 1 000, caso contrário a resposta será considerada errada.

Input do Exemplo 1

1
2
9
8

Output do Exemplo 1

-1
4 3
1 2
2 3
3 4

Explicação do Exemplo 1

Este exemplo corresponde ao exemplo mencionado na Parte I do enunciado.

Input do Exemplo 2

2
2
7
8

Output do Exemplo 2

-1
4 3
1 2
2 3
3 4

Explicação do Exemplo 2

Este exemplo corresponde ao exemplo mencionado na Parte II do enunciado.