I always use long long *as* bitset.

The cycles are irrelevant. You can block what's on the cycles in any way you want.

Oh, I see why now. I used map instead of unordered_map. Silly me XD. Thanks for the code.

Sqrt(N) = 700?)

You need O(1) acces to cnt[v[st]] , not O(log n) with map

Perhaps, you got TLE with map/unordered_map, too? Could you show your code?

He meant that all connected components in the graph are cliques. The solution is indeed correct(i got it accepted, probably he had bug in his code). The solution is easily provable to be correct.

If we denote number of clicks(where a click toggles the edges and their complement) on a node as A_node then for some 3 nodes x, y, z if there is an edge already present A_x + A_y should be even, otherwise odd(similarly for A_x + A_z and A_y + A_z). It is easy to see this only satisfies when either A_x + A_y, A_x + A_z, A_y + A_z are all even or 1 of them is even while other two are odd. This corresponds to the clique condition.

#include <iostream>
#include <cstdio>
#include <vector>
using namespace std;

const int maxn = int(1e3)+5;

int n, in[maxn];
bool G[maxn][maxn];

void dfs(int node, int comp)
{
	in[node] = comp;
	for(int i = 0;i < n;i++)
	{
		if(!in[i] && G[node][i])
		{
			dfs(i, comp);
		}
	}
}

int main(void)
{
	int m, u, v;
	scanf("%d%d", &n, &m);
	for(int i = 0;i < n;i++) G[i][i] = 1;

	if(!m)
	{
		printf("NE\n");
		return 0;
	}
	while(m--)
	{
		scanf("%d%d", &u, &v);
		u--; v--;
		G[u][v] = G[v][u] = 1;
	}

	int ctr = 1;
	for(int i = 0;i < n;i++)
	{
		if(!in[i])
		{
			dfs(i, ctr++);
		}
	}

	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < n;j++)
		{
			if(in[i] == in[j] && !G[i][j])
			{
				printf("NE\n");
				return 0;
			}
		}
	}
	printf("DA\n");
}

EDIT: sorry for errors, i didnt pay attention while typing.

Sorry, I should've explained better. I marked connected components based on the edges that existed in the beginning, but the edges I checked whether they had endpoints in the same connected component were the non-existing ones, the ones you were supposed to create. So for N = 3, M = 1, e ={ 1, 2 }, the edges I looked at were {1, 3} and {2, 3}.

I noticed that if you flipped the node x, you'd also have to flip every node it's currently connected to, so you could get that edge back after destroying it, so basically, you'd have to flip the entire connected component. The problem arises when two nodes that aren't directly connected are in the same connected component, let's say nodes w and y. After flipping w, you'd create the edge {_w, y_}, but you'd have to flip y too, therefore destroying the edge. The only thing I'm not sure about, and only based on my gut feeling is that each node will be flipped at most once.

My approach: 
problem: how many numbers in a segment that appears exactly 2 times!
PREREQUISITE : loj - 1188; i wrote an editorial there.
Solution : off-line solve, segment tree.

okay lets jump into it with an example (given array):

8
1 1 1 2 3 5 1 2

first lets solve the problem if the query always starts from 0th index and ends at any index. how to approach that? using this array: 0 1 -1 0 0 0 0 1 (and make cumulative sum array of course!)

query [0-7] ans = 1. correct.

query [0-1] ans = 1. correct.

okay let me explain how i made this array here. we marked the index where x has appeared 2nd time as 1, meaning: till this index, there is an answer.

then, as we need numbers who are present EXACTLY 2 times, we marked the the index where x has appeared 3rd time as -1, which crosses out index where x appeared 2nd time, meaning: till this point there is no answer! i hope the making of the array is clear now!

now the next part, what happens when the starting index of query is not 0th index? this is where off-line solve comes into play!

we will use this array still:

0 1 -1 0 0 0 0 1

but how do we get the answer when the query is lets say [1,2] using current array if we try to find the answer then the answer will be 0, which is wrong! so how do we find it? think about it! if we make the 1st index 0, 2nd index 1 and 6th index -1 then we can answer any query starting from 1st index! :D and the array is :

0 0 1 0 0 0 -1 1

can you say why we specifically updated the 1st,2nd,6th index? because those are the places where 1 is present. and we changed the positions where 1 is present, why? because 1 is 0th index, which is the previous 1st index.

so for example if the query is [2-7] the we would have to do the same for 0th index value, 1st index value. and the array will be like:

0 0 0 0 0 0 1 1

and the answer is 2!

we simple used segment tree to update and find the query.

CODE

PS: sorry for my bad English and the way i wrote, i usually do not post in codeforces :S

Thanks!! I love you. I'll try it.