Os países A e B têm más relações. A quer descobrir a rede ferroviária de B para invadi-lo. Enviou espiões várias vezes, mas eles sempre foram capturados antes de obter informações relevantes. Assim, A sabe apenas o seguinte.

• A rede de B consiste em $N$ estações, numeradas de $1$ a $N$.

• Quaisquer duas estações distintas estão conectadas diretamente por um trilho ou por outras estações conectadas por trilhos.

• Entre quaisquer duas estações existe exatamente um caminho.

• Nenhum trilho conecta diretamente uma estação a si mesma.

Percebendo as limitações da espionagem, A pretende subornar um alto executivo da companhia ferroviária de B para obter um desenho da rede. Enviá-lo diretamente revelaria o traidor, portanto ele modificará o desenho como segue antes de enviá-lo a A.

• Desenhe $K$ trilhos falsos. Escolha estações distintas $a$ e $b$ que não estejam diretamente conectadas no desenho e conecte-as com um trilho falso. Repita isso $K$ vezes.

• Coloque uma marca especial em uma estação.

• Por fim, apague todos os números das estações.

O traidor transmite o desenho resultante a A. Como essas informações por si só dificultam reconhecer a rede de B, ninguém saberá que informações secretas foram vazadas.

Para o plano dar certo, os seguintes problemas precisam ser resolvidos.

• O desenho recebido não tem números de estações nem indica quais trilhos são reais ou falsos. A sabe apenas qual estação está marcada e que foram adicionados exatamente $K$ trilhos falsos.

• O remetente deve escolher adequadamente os trilhos falsos e a estação marcada para que o destinatário distinga os trilhos reais dos falsos apenas pelo desenho.

• O destinatário deve entender como o desenho foi modificado e recuperar o desenho da rede original.

São necessárias duas funções: uma para modificar o desenho e outra para recuperar a rede real. A quer confiar esse trabalho a você.

Detalhes de implementação

Implemente as duas funções a seguir.

vector< pair<int, int> > encode_map(int N, int K, int &X,
                                            vector< pair<int, int> > E)

• O argumento inteiro N é o número $N$ de estações de B. Cada estação é representada por um inteiro de $1$ a $N$, inclusive.

• O argumento inteiro K é o número $K$ de trilhos falsos a adicionar.

• O argumento X registra o número da estação a marcar. Ao terminar a função, deve conter um inteiro positivo de $1$ a $N$, inclusive.

• O vetor E tem tamanho $N-1$ e representa a rede de B. Um par $(a,b)$ em E indica um trilho direto entre as estações $a$ e $b$.

• Retorne um vetor com $K$ pares $(a,b)$ indicando trilhos falsos entre estações distintas $a$ e $b$. Não adicione um trilho falso entre $a$ e $b$ se elas já estiverem conectadas por um trilho real ou falso.

vector< pair<int, int> > decode_map(int N, int K, int X,
                                            vector< pair<int, int> > E)

• O argumento inteiro N é o número $N$ de estações de B. As estações são representadas por inteiros de $1$ a $N$, inclusive. Como os números foram apagados ao enviar o desenho, os usados aqui podem diferir dos reais. São obtidos aplicando alguma bijeção aos números usados em encode_map.

• O argumento inteiro K é o número $K$ de trilhos falsos adicionados.

• O argumento inteiro X é o número da estação com a marca especial.

• O vetor E tem tamanho $N+K-1$ e representa o desenho entregue a A. Um par $(a,b)$ significa que as estações $a$ e $b$ estão diretamente conectadas por um trilho real ou falso no desenho. A ordem dos elementos de E não tem significado.

• Esta função recupera o desenho original a partir daquele produzido por encode_map. Retorne um vetor de $N-1$ pares $(a,b)$ que contenha a rede de B.

Não chame funções de entrada ou saída em nenhuma parte do código enviado.

Cada caso de teste contém um ou mais cenários independentes. Para um caso com $T$ cenários, o programa que chama as funções é executado exatamente duas vezes, como segue.

Na primeira execução:

• encode_map é chamada $T$ vezes.

• O sistema de avaliação armazena os resultados de encode_map.

• decode_map não é chamada.

Na segunda execução:

• decode_map é chamada várias vezes. A cada chamada, um cenário arbitrário é escolhido e o desenho produzido por encode_map para ele é usado como entrada de decode_map.

• encode_map não é chamada.

O tempo de execução e o uso de memória são calculados combinando as duas execuções.

Restrições

• $1 \le T \le 200$

• $3 \le N \le 200$

• $1 \le K < \frac{N}{2}$

Subtarefas

1. ($4$ pontos) $N \le 4$.

2. ($13$ pontos) $K=1$.

3. ($11$ pontos) Cada estação está conectada a no máximo dois trilhos.

4. ($29$ pontos) Qualquer estação pode alcançar qualquer outra percorrendo no máximo $\lfloor N/2 \rfloor$ trilhos.

5. ($43$ pontos) Sem restrições adicionais.

Subtarefas

Um teste só é considerado correto se encode_map produzir um desenho válido e decode_map identificar corretamente a rede. Se o vetor retornado por decode_map contiver sequer um trilho falso, a pontuação desse teste será $0$. A ordem dos elementos dos vetores retornados pelas duas funções não importa.

A pontuação de uma subtarefa é a menor pontuação entre todos os seus testes.

Exemplos

• Considere $N=6$, $K=1$ e os trilhos $E=[(1,2),(1,3),(1,4),(4,5),(4,6)]$.

O avaliador chama a função a seguir.

encode_map(6, 1, X, [(1, 2), (1, 3), (1, 4), (4, 5), (4, 6)])

O desenho à esquerda mostra a rede de B. Adicionar o trilho falso $(4,2)$ e marcar a estação $1$ produz o desenho à direita. Nesse caso, encode_map retorna [(4, 2)] e armazena $1$ em X. Outras respostas podem existir.

Em seguida, o avaliador chama a função abaixo. A ordem dos elementos do vetor fornecido no último argumento pode variar.

decode_map(6, 1, 2, [(1, 5), (2, 3), (2, 4), (2, 5), (3, 5), (5, 6)])

O desenho representado pela entrada é mostrado abaixo. Os números das estações diferem dos usados em encode_map.

A função retorna [(3, 2), (4, 2), (5, 6), (1, 5), (5, 2)]. A ordem dos elementos pode variar.

Este exemplo satisfaz as condições das subtarefas $2$, $4$ e $5$.

Avaliador de exemplo

O avaliador de exemplo aceita entrada no formato a seguir.

• Linha $1$: $T$

Em seguida vêm $T$ blocos, cada um representando um cenário. Cada bloco tem o formato a seguir.

• Linha $1$: $N\ K$

• Linha $1+i$ ($1 \le i \le N-1$): $a_i\ b_i$

O par $a_i,b_i$ indica um trilho que conecta as estações $a_i$ e $b_i$.

Para cada cenário, o avaliador de exemplo imprime o seguinte.

• Linha $1$: o vetor retornado por encode_map.

• Linha $2$: o vetor retornado por decode_map.

O avaliador de exemplo pode diferir daquele usado na avaliação real.