Mesa da Sra. Montagny!
Por XI Maratona de Programação IME-USP, 2007 
Brazil
Por XI Maratona de Programação IME-USP, 2007 Brazil
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 ideia é 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: http://en.wikipedia.org/wiki/Banff Springs 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.
A entrada é composta de diversas instâncias. A primeira linha de cada instância contém dois inteiros n (1 ≤ n ≤ 100) e m (0 ≤ m ≤ 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 ≤ u, v ≤ n.
A entrada termina com final de arquivo.
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 não, caso contrário.
| Exemplo de Entrada | Exemplo de Saída |
|
3 3 |
Instancia 1 nao Instancia 2 sim |