Para efeitos da nota atribuida à resolução de exercícios ao longo do semestre - Submeter até 23:59 de 1 de Junho
(o problema continuará depois disponível para submissão, mas sem contar para a nota)
[para perceber o contexto do problema deve ler o guião da aula #11]

[DAA 042] Clube de livros
(este problema é essencialmente uma tradução/adaptação de um problem do SWERC'2014)

Todos os membros do clube de livros do Porto estão a ferver de excitação com o evento anual de trocas de livros! Todos os anos, cada membro traz o seu livro favorito e tentam descobrir um outro livro que seja de um outro membro disposto a trocar com eles.

O Aniceto já esteve nessa troca de livros antes e definitivamente não quer perder o evento este ano, mas ele acha que o processo de trocas pode ser melhorado. No passado, pares de membros interessados nos livros um do outro simplesmente trocavam: se a pessoa A trazia um livro que a pessoa B gostava, e vice-versa, então A e B trocavam os seus livros.

Foi aí que percebeu que muitos membros ficavam com o mesmo livro com que entravam... Se ao invés de procurarmos por pares, procurarmos por tripletes de membros, poderiamos descobrir mais trocas válidas! Imagina que o membro A apenas gosta do livro de B, enquanto que B apenas gosta do livro de C e que C gosta do livro de A. Estas 3 pessoas podiam trocar os livros num ciclo e todos ficariam contentes!

Mas porquê parar em apenas 3 pessoas? Os ciclos podem ser cada vez maiores! Podes ajudar-me a descobrir se é possível que todos saiam com um novo livro? Tem cuidado, porque os membros não irão dar o seu livro para troca sem receber um outro livro que gostem de volta.

O Problema

Dados os membros de um clube de livros e os livros que eles gostam, consegues descobrir uma maneira de todos receberem um livro que gostem?

Input

O input contém vários casos de teste, sendo que na primeira linha do input vem um inteiro C indicando quantos casos se seguem.

Cada caso de teste começa com uma linha indicando N, o número de pessoas. A segunda linha de cada caso contém M, o número total de "declarações de interesse". Seguem-se M linhas, cada uma com dois inteiros A e B indicando que o membro A gosta do livro que o membro B trouxe (0 ≤ A,B < N, ou seja, os membros são numerados de 0 a N-1). Os números A e B nunca são iguais (um membro nunca gosta do livro que ele próprio trouxe).

Output

Uma linha para cada caso de teste, na mesma ordem em que aparecem no input, contendo YES se podemos encontrar um livro para cada membro e NO caso contrário.

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

Exemplo de Input

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

Exemplo de Output

NO
YES

Desenho e Análise de Algoritmos (CC2001)
DCC/FCUP - Faculdade de Ciências da Universidade do Porto