Verificar se o Grafo é Bipartido

Um grafo é considerado bipartido se for possível colorizá-lo com duas cores de forma que nenhum par de vértices adjacentes partilhe a mesma cor.

Determinar se um grafo é bipartido pode ajudar a revelar estruturas e propriedades específicas, permitindo resolver problemas de forma mais eficiente em áreas como planeamento de tarefas, alocação de recursos e resolução de conflitos. Além disso, os grafos bipartidos possibilitam algoritmos mais simples e otimizações em tarefas como emparelhamento máximo (maximum matching) e coloração de grafos (graph coloring).

É fornecido um grafo não dirigido com v vértices e e arestas. É necessário verificar se o grafo é bipartido ou não.

Entrada

A primeira linha da entrada contém dois inteiros v (1 ≤ v ≤ 100 000) e e (1 ≤ e ≤ 100 000).

As seguintes e linhas contêm pares de inteiros v1 e v2 (1 ≤ v1, v2 ≤ v), indicando que o vértice v1 está ligado ao vértice v2 e vice-versa.

Saída

O programa deve imprimir Yes se o grafo for bipartido e No caso contrário.

Exemplos