SPOJ Brasil

Sabe-se que certos problemas que são NP-completos para grafos genéricos podem ser resolvidos em tempo polinomial para certas classes especiais de grafos. Um problema importante em computação teórica é identificar quando um grafo pertence a determinada classe, justamente para sabermos quando podemos resolver certo problema em tempo polinomial.

Neste problema, pede-se para verificar se determinado grafo pertence a classe dos grafos cordais. Em grafos cordais, problemas como o do clique máximo podem ser resolvidos em tempo polinomial. Um grafo cordal é um grafo em que qualquer sub-ciclo com mais de 3 vértices possui uma corda, ou seja, uma aresta do grafo que não pertence ao ciclo mas liga dois vértices não adjacentes no ciclo.

Entrada

A entrada contém diversos casos de teste. Após o último caso de teste da entrada teremos uma linha contendo 0 0.

A primeira linha de um caso de teste contém dois inteiros, n e m , indicando o numero de vértices e arestas, respectivamente, 1≤n≤1000. Após isso, segue-se m linhas contendo u (1≤u≤n) e v(1≤v≤n), descrevendo as arestas do grafo.

Saída

Para cada caso de teste, imprima '0', caso o grafo não seja cordal, e '1', caso o grafo seja cordal.

Exemplo

Entrada:
4 4
1 2
2 3
3 4
4 1
3 3
1 2
2 3
3 1
0 0

Saída:
01