Mesa

Retirada de SPOJ

Já comentamos as festas da Sra. Montagny à beira do Lake Louise em Banff. Nas suas festas ela se compromete a resolver um outro problema que faz tremer organizadores de jantares em todo o mundo: onde sentar os convidados. A magnata simplifica bastante o problema pedindo aos convidados, no mesmo questionário já comentado, que anote na lista dos convidados aqueles que desejariam ter à sua frente na mesa do jantar. A idéia é ter seus amigos sempre à sua frente, para que a conversa possa fluir melhor. A habilidade da socialite é tamanha que ela foi contratada pelo Fairmont Banff Springs hotel (hotel em que vão ocorrer as finais mundiais do ICPC em 2008: Hotel) para trabalhar no arranjo de mesas de banquete.

Sua tarefa neste problema é auxiliar novamente a magnata. Dados os desejos dos convidados, seu programa deve decidir se é possível dispô-los numa mesa de forma que cada convidado tenha todos os seus amigos no lado oposto da mesa.

Entrada

A primeira linha de cada instância contém dois inteiros $n$ $(1 \leq n \leq 100)$ e $m$ $(0 \leq m \leq \frac{n \cdot (n-1)}{2})$, onde $n$ é o número de convidados e $m$ é o número de relações de amizade. Cada uma das $m$ linhas seguintes contém dois inteiros $u$ e $v$ indicando que $u$ é amigo de $v$ e $v$ é amigo de $u$, onde $1 \leq u, v \leq n$.

Saída

Para cada caso de teste imprima sim se é possível e nao caso contrário.

3 3
1 2
2 3
1 3

nao

4 3
1 2
1 3
1 4