Escrito por Leonardo Paes.
Conhecimento prévio necessário:
Suponha que $$x$$ seja uma folha inicialmente. Isso quer dizer que Ayush, o jogador que joga primeiro, ganha. Caso contrário, $$x$$ não é folha. Se algum movimento tornar $$x$$ em uma folha, esse movimento será ruim para o jogador atual, pois ele dará a vitória para seu oponente. Logo, antes de tornar $$x$$ uma folha, tiraremos todos os outros nós da árvore. Antes do último movimento, o que retirará $$x$$, o grafo será apenas $$x$$ ligado a algum vértice. Logo, o jogador que faz o movimento $$n-2$$ é o vencedor.
Código de Exemplo: