Problema C - Jogos de Arte

Um móbile é uma escultura cinética muito apreciada em certos ciclos de arte. Podem ver um exemplo na figura à direita.

Este tipo de estrutura consiste num conjunto de arames que seguram algumas peças de forma a formar uma estrutura equilibrada. Definimos um móbile como um conjunto de N peças onde cada uma está segura a outra através de um arame, tirando uma peça especial, que chamamos de raiz, que está segura ao teto. Cada peça de um móbile está identificada por um inteiro distinto de 1 a N, sendo que a raiz é sempre a peça com valor 1. A imagem de baixo representa um possível móbile de tamanho 8 (ou seja, com 8 peças).

Recentemente, a exposição internacional de móbiles chegou a Portugal e o Manuel e o Tiago não puderam perder a oportunidade para a visitar. As obras em si despertam um grande interesse por este duo de rapazes culto, mas na verdade a razão pela qual eles adoram móbiles é porque eles têm um divertido jogo que não podem passar sem jogar.

A ideia do jogo é simples: usando um móbile como tabuleiro, começam por marcar a raiz como a peça inicial. De seguida, o Manuel e o Tiago jogam alternadamente. Cada jogada consiste em selecionar uma das peças que estão seguras à peça atualmente marcada e movimentar a marcação para essa peça. No final, perde quem não puder fazer mais uma jogada (ou seja, quem se encontrar numa peça "solta", que não tem nenhuma outra peça agarrada). Adicionalmente, o Manuel é sempre o primeiro a jogar.

Vejamos um exemplo de um jogo. Usando o móbile da imagem de cima, o Manuel começa a jogar. De seguida escolhe a peça 2 como a próxima peça, que passa a ser a peça marcada. O Tiago, logo sem hesitar, escolhe a peça 6 como próxima peça e esta passa a ser a peça marcada. Infelizmente o Manuel já não tem nenhuma peça para escolher, logo acaba de perder o jogo. A imagem seguinte representa este jogo (as linhas a vermelho representam as jogadas):

Como pudeste ver, o Tiago é um jogador de grande habilidade. Na realidade, o Tiago conhece o jogo mesmo bem, de tal forma que ele joga de forma ótima, ou seja, ele joga sempre a melhor jogada, que é a que lhe garante que será o vencedor (se existir, caso contrário pode jogar uma qualquer). Infelizmente, o Manuel não é assim tão bom, por isso a tua tarefa será ajudá-lo. A tua tarefa tem duas partes (que são incrementais):

O Problema

Parte I

Tens de ajudar o Manuel a ganhar! Ele está sempre a perder...

É indicada a configuração de um móbile que será o tabuleiro do jogo. Sabendo que o Manuel joga primeiro, o teu objetivo é determinar se o Manuel tem alguma jogada que lhe garanta a vitória, ou seja, que independentemente de como o Tiago jogar, o Manuel tem sempre uma forma de ganhar.

Por exemplo, para a imagem em cima, basta o Manuel jogar para a peça 3 no início que ganha o jogo. Logo, nesse tabuleiro o Manuel pode sempre ganhar.

Parte II

Agora que já ajudaste o Manuel a ganhar quando pode, deves ter reparado que há alguns móbiles onde o Manuel, por melhor que jogue, simplesmente não consegue ganhar. Isso é uma chatice! Assim, o teu objetivo será ajudar o Manuel a fazer batota para ganhar.

Analisando o móbile com cuidado, o Manuel reparou que os arames são frágeis e que por isso ele consegue cortar alguns. Ele só pode cortar arames entre duas peças e cada corte faz com que a peça imediatamente abaixo do corte caia (assim como todas as peças penduradas a partir dessa), sendo por isso todas essa peças removidos do móbile e do jogo. Usando só este tipo de operação, é possível transformar um jogo onde o Manuel não conseguia ganhar, num jogo onde ele pode ganhar. A imagem em baixo representa um exemplo de uma situação dessas:

No móbile inicial (na esquerda da imagem), independentemente de onde o Manuel jogar no início, o Tiago consegue sempre ganhar. Porém, se o Manuel cortar o arame que liga a peça 5 à peça 2 (no meio da imagem), no móbile resultante (na direita da imagem) ele já pode ganhar escolhendo a peça 2 no início do jogo. Adicionalmente, ele podia cortar o arame entre a peça 3 e a peça 6 e também teria um tabuleiro onde ele poderia ganhar.

O problema do Manuel é que se ele cortar demasiadas peças, o Tiago pode reparar que o móbile está muito pequeno e perceber que ele fez batota. Assim, o Manuel precisa que determines qual é o menor número de peças que podem ser removidas do móbile (usando apenas operações onde se cortam arames como indicado em cima) de forma a que o Manuel tenha um conjunto de jogadas que lhe garantam a vitória.

Input

NOTA: Este problema tem múltiplo input por cada caso de teste. Isto significa que por cada caso de teste irão receber várias instâncias para resolver.

Na primeira linha vem um único inteiro T, indicando o número de casos de teste a resolver. Seguem-se T casos de teste formados da seguinte forma:

Na primeira linha, de cada caso de teste, vêm dois inteiros: P N. O número P indica qual a tarefa (1 para a parte I indicada acima e 2 para a parte II). N indica o tamanho do móbile que será usado como tabuleiro do jogo.

A segunda linha do móbile contém N - 1 inteiros representando as ligações entre peças. O primeiro número indica a que peça se liga a peça nº2, o segundo número indica a peça onde se liga a peça nº3, o terceiro número indica a peça onde se liga a peça nº4 e assim sucessivamente.

Output

Para cada caso de teste um linha com o seguinte:

Se o caso for uma instância da parte I (indicado P=1), um único inteiro 0 ou 1, onde o 0 indica que o Manuel não tem forma de ganhar um jogo no móbile dado e 1 que o Manuel tem pelo menos uma forma de ganhar, independentemente das jogadas do Tiago.

Se o caso for uma instância da parte II(indicado P=2), um único inteiro que representa o menor número de peças a remover usando operações de corte, tal que no tabuleiro resultante o Manuel possa ganhar o jogo.

Restrições

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

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

Input do Exemplo 1

3
1 8
1 1 1 2 2 4 5
1 9
1 1 2 2 3 4 5 8
1 6
1 1 2 3 4

Output do Exemplo 1

1
0
1

Explicação do Exemplo 1

O primeiro caso de teste do exemplo corresponde ao móbile da primeira imagem. O segundo corresponde ao móbile da esquerda da última imagem. O terceiro corresponde ao móbile da direita da última imagem.

Input do Exemplo 2

2
2 9
1 1 2 2 3 4 5 8
2 18
1 1 2 2 2 3 3 4 5 6 7 8 9 10 11 12 13

Output do Exemplo 2

1
2

Explicação do Exemplo 2

O primeiro caso de teste deste exemplo corresponde ao móbile da última imagem.