F. Bipartite Checking
time limit per test

6 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

You are given an undirected graph consisting of n vertices. Initially there are no edges in the graph. Also you are given q queries, each query either adds one undirected edge to the graph or removes it. After each query you have to check if the resulting graph is bipartite (that is, you can paint all vertices of the graph into two colors so that there is no edge connecting two vertices of the same color).

Input

The first line contains two integers n and q (2 ≤ n, q ≤ 100000).

Then q lines follow. ith line contains two numbers xi and yi (1 ≤ xi < yi ≤ n). These numbers describe ith query: if there is an edge between vertices xi and yi, then remove it, otherwise add it.

Output

Print q lines. ith line must contain YES if the graph is bipartite after ith query, and NO otherwise.

Example

input

Copy

output

同bzoj4025 但我原来的方法不会搞了 所以选择学习了下icefox巨佬的方法

还是维护一颗最大生成树 树的权值是 这条边消失的时间 记录mark表示判断该边是否属于奇环或者偶环 或者仅仅是树边 每次如果新边消失时间更长则替换树上原有的边 每次有一个奇环就计数器+1 如果该操作是删除就正常处理 注意需要删除树边

 

分类: LCT-link cut tree

elijahqi

辣鸡蒟蒻一枚qwq 欢迎加qq qwq 2922945330

发表评论