Bipartido ou não?

É dado um grafo não-direcionado composto por $$N$$ vértices e $$M$$ arestas. Se for possível dividir os vértices do grafo em dois conjuntos disjuntos $$A$$ e $$B$$ tal que cada aresta liga apenas vértices do conjunto $$A$$ para vértices do conjunto $$B$$, é dito que o grafo é bipartido. Thiaguinho está estudando sobre grafos bipartidos, e por isso, quer descobrir se ao adicionar uma aresta ao grafo, ele será bipartido ou não. Ajude Thiaguinho a determinar, para cada $$i \leq M$$, se ao adicionar apenas as arestas com índice menor ou igual a $$i$$ no grafo, ele será bipartido ou não.

Entrada

A primeira linha da entrada consiste de dois inteiros $$N$$ ($$1 \leq N \leq 10^5$$) e $$M$$ ($$1 \leq M \leq min(\frac{N(N-1)}{2}, 10^5)$$), representando, respectivamente, a quantidade de vértices e arestas do grafo. As próximas $$M$$ linhas contém dois inteiros, $$U_i$$ e $$V_i$$ ($$1 \leq U_i, V_i \leq N$$), os dois vértices sendo ligados pela aresta $$i$$.

Saída

Para cada uma das $$M$$ arestas, seu programa deve imprimir “Sim” se o grafo for bipartido considerando apenas as arestas até o momento atual, ou “Não”, caso contrário.

Exemplo