Submission #1498515

---

Source Code Expand

n,m=map(int,input().split())
vis,ci,cb,cc=[0]*(n+5),0,0,0
g=[[] for i in range(n+5)]
def dfs(x,col):
	if vis[x]:
		return vis[x]==col
	vis[x],flag=col,True
	for i in g[x]:
		flag&=dfs(i,3-col)
	return flag
for i in range(m):
	u,v=map(int,input().split())
	g[u]+=[v]
	g[v]+=[u]
for i in range(1,n+1):
	if vis[i]==0:
		if len(g[i])==0:
			ci+=1
		else:
			if dfs(i,1):
				cb+=1
			else:
				cc+=1
print(ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb)

Submission Info

Judge Result