MESA – Mesa da Sra Montagny!

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 entrada é composta de diversas instâncias. A primeira linha de cada instância contém dois inteiros $$n$$ $$(1 \leq n \leq 100)$$ e $$m$$ $$(0 \leq m \leq n*(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$$.

A entrada termina com final de arquivo (EOF).

Saída

Para cada instância, você deverá imprimir um identificador $$Instancia$$ $$k$$, onde $$k$$ é o número da instância atual. Na linha seguinte imprima $$sim$$ se é possível e $$nao$$ caso contrário.

Após cada instância imprima uma linha em branco.

Exemplo

Entrada	Saída
3 3 1 2 2 3 1 3 4 3 1 2 1 4	Instancia 1 naoInstancia sim

Enviar solução: SPOJ