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

ENTRADA	SAÍDA
4 5 1 2 2 3 2 4 3 4 1 4	Sim Sim Sim Não Não