Submission #1498542

---

Source Code Expand

import sys

class TailRecurseException:
	def __init__(self, args, kwargs):
		self.args = args
		self.kwargs = kwargs

def tail_call_optimized(g):
	def func(*args, **kwargs):
		f = sys._getframe()
		if f.f_back and f.f_back.f_back and f.f_back.f_back.f_code == f.f_code:
			raise TailRecurseException(args, kwargs)
		else:
			while 1:
				try:
					return g(*args, **kwargs)
				except TailRecurseException, e:
					args = e.args
					kwargs = e.kwargs
	func.__doc__ = g.__doc__
	return func

n,m=map(int,raw_input().split())
vis,ci,cb,cc=[0]*(n+1),0,0,0
g=[[] for i in range(n+1)]
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,raw_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