Problem:


Score : 800 points

Problem Statement

Takahashi has received an undirected graph with N vertices, numbered 1, 2, ..., N.
The edges in this graph are represented by (u_i, v_i).
There are no self-loops and multiple edges in this graph.

Based on this graph, Takahashi is now constructing a new graph with N^2 vertices, where each vertex is labeled with a pair of integers (a, b) (1 \leq a \leq N, 1 \leq b \leq N).
The edges in this new graph are generated by the following rule:

Span an edge between vertices (a, b) and (a', b') if and only if both of the following two edges exist in the original graph: an edge between vertices a and a', and an edge between vertices b and b'.

How many connected components are there in this new graph?

Constraints

2 \leq N \leq 100,000

0 \leq M \leq 200,000

1 \leq u_i < v_i \leq N

There exists no pair of distinct integers i and j such that u_i = u_j and v_i = v_j.

Input

The input is given from Standard Input in the following format:

N M
u_1 v_1
u_2 v_2
:
u_M v_M

Output

Print the number of the connected components in the graph constructed by Takahashi.

Sample Input 1

3 1
1 2

Sample Output 1

7

The graph constructed by Takahashi is as follows.

Sample Input 2

7 5
1 2
3 4
3 5
4 5
2 6

Sample Output 2

18



Sample input:
3 1
1 2


Sample output:
7

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ns[a].add(b)
    ns[b].add(a)

# 二部グラフ判定 bipertite
cs = [None]*n
def is_bip(u):
    q = [start]
    cs[start] = 1
    v1 = 1
    v0 = 0
    while q:
        u = q.pop()
        c = cs[u]
        cc = int(not c)
        bip = True
        for v in ns[u]:
            if cs[v] is None:
                cs[v] = cc
                if cc==0:
                    v0 += 1
                else:
                    v1 += 1
                q.append(v)
            elif cs[v]==c:
                bip = False
    if bip:
        return True, v0, v1
    else:
        return False, v0+v1, 0
types = []
vals = []
ans = 0
n0 = 0
n1 = 0
n2 = 0
nv = 0
for start in range(n):
    if cs[start] is not None:
        continue
    res, v0, v1 = is_bip(start)
#     print(res, v0,v1)
    if v0+v1==1:
        # 孤立点
        n0 += 1
    elif res:
        # 二部グラフ
        nv += (v0+v1)
        n1 += 1
    else:
        nv += (v0+v1)
        n2 += 1
ans += n0*nv*2
ans += n0**2
ans += (n1+n2)**2 + n1**2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ns[a].add(b)
    ns[b].add(a)

# 二部グラフ判定 bipertite
cs = [None]*n
def is_bip(u):
    q = [start]
    cs[start] = 1
    v1 = 1
    v0 = 0
    while q:
        u = q.pop()
        c = cs[u]
        cc = int(not c)
        bip = True
        for v in ns[u]:
            if cs[v] is None:
                cs[v] = cc
                if cc==0:
                    v0 += 1
                else:
                    v1 += 1
                q.append(v)
            elif cs[v]==c:
                bip = False
    if bip:
        return True, v0, v1
    else:
        return False, v0+v1, 0
types = []
vals = []
ans = 0
n0 = 0
n1 = 0
n2 = 0
nv = 0
for start in range(n):
    if cs[start] is not None:
        continue
    res, v0, v1 = is_bip(start)
#     print(res, v0,v1)
    if v0+v1==1:
        # 孤立点
        n0 += 1
        ans += 1
    elif res:
        # 二部グラフ
        nv += (v0+v1)
        n1 += 1
    else:
        nv += (v0+v1)
        n2 += 1
ans += n0*nv*2
ans += (n1+n2)**2 + n1**2
print(ans)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

def check(s, Edge):
    stack = [s]
    col[s] = False
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf in used:
                if col[vn] == col[vf]:
                    return False
            else:
                col[vf] = not col[vn]
                used.add(vf)
                stack.append(vf)
    return True

N, M = map(int, readline().split())

Edge = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)


bip = 0
nb = 0
po = 0
used = set()
col = [None]*N
for i in range(N):
    if i in used:
        continue
    used.add(i)
    if not Edge[i]:
        po += 1
        continue
    if check(i, Edge):
        bip += 1
    else:
        nb = 1
print(2*bip**2+2*nb*bip+nb**2+N**2-(N-po)**2)

Submission status: Wrong Answer

Solution code:
import sys
readline = sys.stdin.readline

def check(s, Edge):
    stack = [s]
    col = [0]*N
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf in used:
                if col[vn] == col[vf]:
                    return False
            else:
                col[vf] = not col[vn]
                used.add(vf)
                stack.append(vf)
    return True

N, M = map(int, readline().split())

Edge = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)


bip = 0
nb = 0
po = 0
used = set()
for i in range(N):
    if i in used:
        continue
    used.add(i)
    if not Edge[i]:
        po += 1
        continue
    if check(i, Edge):
        bip += 1
    else:
        nb = 1
print(2*bip**2+2*nb*bip+nb**2+N**2-(N-po)**2)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
	u, v = map(int, input().split())
	adj[u-1].append(v-1)
	adj[v-1].append(u-1)

visited = [False for _ in range(n)]
tree, loop = 0, 0

def dfs(start):
	global tree, loop
	is_tree = True
	stack = [(start, -1)]
	while stack:
		x, p = stack.pop()
		for v in adj[x]:
			if v == p:
				continue
			elif visited[v]:
				is_tree = False
			else:
				visited[v] = True
				stack.append((v, x))
	if is_tree:
		tree += 1
	else:
		loop += 1
	return

for i in range(n):
	if not visited[i] and adj[i]:
		visited[i] = True
		dfs(i)

alone = n - sum(visited)
ans = 2*tree + loop + 2*tree*(tree-1) + 2*tree*loop + loop*(loop-1)
ans += alone*(2*n-alone)

print(ans)

Submission status: Wrong Answer

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
	u, v = map(int, input().split())
	adj[u-1].append(v-1)
	adj[v-1].append(u-1)

visited = [False for _ in range(n)]
tree, loop = 0, 0

def dfs(start):
	global tree, loop
	is_tree = True
	stack = [(start, -1)]
	while stack:
		x, p = stack.pop()
		for v in adj[x]:
			if v == p:
				continue
			elif visited[v]:
				is_tree = False
			else:
				visited[v] = True
				stack.append((v, x))
	if is_tree:
		tree += 1
	else:
		loop += 1
	return

for i in range(n):
	if not visited[i] and adj[i]:
		visited[i] = True
		dfs(i)

alone = n - sum(visited)
ans = 2*tree + loop + 2*tree*(tree-1) + 2*tree*loop + loop*(loop-1)//2
ans += alone*(2*n-alone)

print(ans)

Submission status: Wrong Answer

Solution code:
n,m = list(map(int, input().split()))
uv = []
for i in range(m):
    uv.append(tuple(map(int, input().split())))

# print(uv)
print(n**2-m*2)

Submission status: Wrong Answer

Solution code:
from sys import stdin
from itertools import repeat
from collections import deque
def main():
    n, m = map(int, stdin.readline().split())
    dat = map(int, stdin.read().split(), repeat(10, 2 * m))
    deg = [0] * n
    la = [None] * n
    xt = [0] * (2 * m)
    for i in xrange(m):
        ui = i * 2
        vi = i * 2 + 1
        dat[ui] -= 1
        dat[vi] -= 1
        u = dat[ui]
        v = dat[vi]
        deg[u] += 1
        deg[v] += 1
        xt[vi] = la[u]
        la[u] = vi
        xt[ui] = la[v]
        la[v] = ui
    so = tr = lo = 0
    q = deque()
    done = [0] * n
    pu = q.append
    po = q.popleft
    for i in xrange(n):
        if done[i]:
            continue
        pu(i)
        done[i] = 1
        nu = [i]
        while q:
            x = po()
            y = la[x]
            while y is not None:
                z = dat[y]
                if not done[z]:
                    done[z] = 1
                    pu(z)
                    nu.append(z)
                y = xt[y]
        sd = 0
        for x in nu:
            sd += deg[x]
        if sd == 0:
            so += 1
        elif sd == len(nu) * 2 - 2:
            tr += 1
        else:
            lo += 1
    print lo * lo + lo * tr * 2 + tr * tr * 2 + so * n * 2 - so * so
main()

Submission status: Time Limit Exceeded

Solution code:
import queue
n,m=map(int,input().split())
vis,ci,cb,cc=[0]*(n+1),0,0,0
g=[[] for i in range(n+1)]
def dfs(x):
	stk,flag=queue.LifoQueue(),True
	stk.put((x,1))
	while not stk.empty():
		u,col=stk.get()
		if vis[u]:
			flag&=(vis[u]==col)
			continue
		vis[u]=col
		for i in g[u]:
			stk.put((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):
				cb+=1
			else:
				cc+=1
print(ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb)

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

###depth first search
def dfs(u, cid, C, G):
    S = []
    C[u] = cid
    S.append(u)
    while len(S):
        u = S.pop()
        for i in range(len(G[u])):
            v = G[u][i]
            if C[v]==0:
                C[v] = cid
                S.append(v)

def dfs4count(u, cid, C, G, F):
    pop_num =0
    S = []
    C[u] = cid
    S.append(u)
    while len(S):
        u = S.pop()
        for i in range(len(G[u])):
            v = G[u][i]
            if v in F:
                # print v, F
                F.pop(F.index(v))
                pop_num += 1

            if C[v]==0:
                C[v] = cid
                S.append(v)
    return pop_num
###get inputs
N, M = map(lambda x:int(x), raw_input().split())
G0 = np.zeros((N,0)).tolist()

for i in range(M):
    u, v = map(lambda x:int(x)-1, raw_input().split())
    G0[u].append(v)
    G0[v].append(u)

###assign colors for raw graph
C0 = np.zeros(N, np.int).tolist()
cid = 0
for u in range(N):
    if C0[u] == 0:
        cid += 1
        dfs(u, cid, C0, G0)
#print C0

###make subgraphs
NUM_C0 = max(C0)
SubGraphs = np.zeros((NUM_C0,0)).tolist()
for cid in range(1,NUM_C0+1):
    indices = np.where(np.asarray(C0)==cid)[0]
    n = indices.shape[0]
    sg=[]
    #sg = np.zeros((n,n), np.int)
    for i in range(n):
        for j in range(n):
            if indices[j] in G0[indices[i]]:###tonariai
                sg.append([indices[i],indices[j]])
                #sg[i,j]=1
    SubGraphs[cid-1]=sg
#print SubGraphs

Gmain = np.zeros((N*N,0)).tolist()
for i in range(NUM_C0):
    for j in range(NUM_C0):
        Gl = SubGraphs[i]
        Gr = SubGraphs[j]
        for gl in Gl:
            for gr in Gr:
                Gmain[gl[0]*N+gr[0]].append(gl[1]*N+gr[1])
                #Gmain[gl[0]*N+gl[1]].append(gr[1]*N+gr[0])
                    
#print Gmain

Cmain = np.zeros(N*N, np.int).tolist()
cid = 0
F = range(N*N)
#for u in F:
while len(F):
    u = F.pop(0)
    #print 'u', u
    if Cmain[u] == 0:
        cid += 1
        tmp = dfs4count(u, cid, Cmain, Gmain, F)
    
print cid


"""
3 1
1 2
"""

"""
7 5
1 2
3 4
3 5
4 5
2 6
"""

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

###depth first search
def dfs(u, cid, C, G):
    S = []
    C[u] = cid
    S.append(u)
    while len(S):
        u = S.pop()
        for i in range(len(G[u])):
            v = G[u][i]
            if C[v]==0:
                C[v] = cid
                S.append(v)

def dfs4count(u, cid, C, G, F):
    pop_num =0
    S = []
    C[u] = cid
    S.append(u)
    while len(S):
        u = S.pop()
        for i in range(len(G[u])):
            v = G[u][i]
            if C[v]==0:
                C[v] = cid
                if v in F:
                    #print v, F
                    F.pop(F.index(v))
                    pop_num+=1
                S.append(v)
    return pop_num
###get inputs
N, M = map(lambda x:int(x), raw_input().split())
G0 = np.zeros((N,0)).tolist()

for i in range(M):
    u, v = map(lambda x:int(x)-1, raw_input().split())
    G0[u].append(v)
    G0[v].append(u)

###assign colors for raw graph
C0 = np.zeros(N, np.int).tolist()
cid = 0
for u in range(N):
    if C0[u] == 0:
        cid += 1
        dfs(u, cid, C0, G0)
#print C0

###make subgraphs
NUM_C0 = max(C0)
SubGraphs = np.zeros((NUM_C0,0)).tolist()
for cid in range(1,NUM_C0+1):
    indices = np.where(np.asarray(C0)==cid)[0]
    n = indices.shape[0]
    sg=[]
    #sg = np.zeros((n,n), np.int)
    for i in range(n):
        for j in range(n):
            if indices[j] in G0[indices[i]]:###tonariai
                sg.append([indices[i],indices[j]])
                #sg[i,j]=1
    SubGraphs[cid-1]=sg
#print SubGraphs

Gmain = np.zeros((N*N,0)).tolist()
for i in range(NUM_C0):
    for j in range(NUM_C0):
        Gl = SubGraphs[i]
        Gr = SubGraphs[j]
        for gl in Gl:
            for gr in Gr:
                Gmain[gl[0]*N+gr[0]].append(gl[1]*N+gr[1])
                #Gmain[gl[0]*N+gl[1]].append(gr[1]*N+gr[0])
                    
#print Gmain

Cmain = np.zeros(N*N, np.int).tolist()
cid = 0
F = range(N*N)
#for u in F:
while len(F):
    u = F.pop(0)
    #print 'u', u
    if Cmain[u] == 0:
        cid += 1
        tmp = dfs4count(u, cid, Cmain, Gmain, F)
    
print cid


"""
3 1
1 2
"""

"""
7 5
1 2
3 4
3 5
4 5
2 6
"""

Submission status: Time Limit Exceeded

Solution code:
import numpy as np

###depth first search
def dfs(u, cid, C, G):
    S = []
    C[u] = cid
    S.append(u)
    while len(S):
        u = S.pop()
        for i in range(len(G[u])):
            v = G[u][i]
            if C[v]==0:
                C[v] = cid
                S.append(v)

###get inputs
N, M = map(lambda x:int(x), raw_input().split())
G0 = np.zeros((N,0)).tolist()

for i in range(M):
    u, v = map(lambda x:int(x)-1, raw_input().split())
    G0[u].append(v)
    G0[v].append(u)

###assign colors for raw graph
C0 = np.zeros(N, np.int).tolist()
cid = 0
for u in range(N):
    if C0[u] == 0:
        cid += 1
        dfs(u, cid, C0, G0)
#print C0

###make subgraphs
NUM_C0 = max(C0)
SubGraphs = np.zeros((NUM_C0,0)).tolist()
for cid in range(1,NUM_C0+1):
    indices = np.where(np.asarray(C0)==cid)[0]
    n = indices.shape[0]
    sg=[]
    #sg = np.zeros((n,n), np.int)
    for i in range(n):
        for j in range(n):
            if indices[j] in G0[indices[i]]:###tonariai
                sg.append([indices[i],indices[j]])
                #sg[i,j]=1
    SubGraphs[cid-1]=sg
#print SubGraphs

Gmain = np.zeros((N*N,0)).tolist()
for i in range(NUM_C0):
    for j in range(NUM_C0):
        Gl = SubGraphs[i]
        Gr = SubGraphs[j]
        for gl in Gl:
            for gr in Gr:
                Gmain[gl[0]*N+gr[0]].append(gl[1]*N+gr[1])
                #Gmain[gl[0]*N+gl[1]].append(gr[1]*N+gr[0])
                    
#print Gmain
Cmain = np.zeros(N*N, np.int).tolist()
cid = 0
for u in range(N*N):
    if Cmain[u] == 0:
        cid += 1
        dfs(u, cid, Cmain, Gmain)
print max(Cmain)


"""
3 1
1 2
"""

"""
7 5
1 2
3 4
3 5
4 5
2 6
"""

Submission status: Accepted

Solution code:
mod = 1000000007
eps = 10**-9


def main():
    import sys
    from collections import deque
    input = sys.stdin.buffer.readline

    N, M = map(int, input().split())
    adj = [[] for _ in range(N+1)]
    for _ in range(M):
        a, b = map(int, input().split())
        adj[a].append(b)
        adj[b].append(a)

    seen = [0] * (N+1)
    single = 0
    bipartite = 0
    not_bipartite = 0
    for v0 in range(1, N+1):
        if seen[v0] != 0:
            continue
        flg = 1
        que = deque()
        que.append(v0)
        seen[v0] = 1
        cnt = 0
        while que:
            v = que.popleft()
            cnt += 1
            for u in adj[v]:
                if seen[u] == 0:
                    seen[u] = -seen[v]
                    que.append(u)
                else:
                    if seen[u] == seen[v]:
                        flg = 0
        if cnt == 1:
            single += 1
        else:
            if flg:
                bipartite += 1
            else:
                not_bipartite += 1
    ans = N ** 2 - (N - single) ** 2
    ans += (bipartite + not_bipartite) ** 2
    ans += bipartite ** 2
    print(ans)


if __name__ == '__main__':
    main()

Submission status: Accepted

Solution code:
class UnionFind:
    """素集合を木構造として管理する"""
    def __init__(self, n):
        self.parent = [-1] * n
        self.cnt = n

    def root(self, x):
        """要素xの根を求める"""
        if self.parent[x] < 0:
            return x
        else:
            self.parent[x] = self.root(self.parent[x])
            return self.parent[x]

    def merge(self, x, y):
        """要素xを含む集合と要素yを含む集合を統合する"""
        x = self.root(x)
        y = self.root(y)
        if x == y:
            return
        if self.parent[x] > self.parent[y]:
            x, y = y, x
        self.parent[x] += self.parent[y]
        self.parent[y] = x
        self.cnt -= 1

    def is_same(self, x, y):
        """要素x, yが同じ集合に属するかどうかを求める"""
        return self.root(x) == self.root(y)

    def get_size(self, x):
        """要素xを含む集合の要素数を求める"""
        return -self.parent[self.root(x)]

    def get_cnt(self):
        """集合の個数を求める"""
        return self.cnt


def is_bipartite(graph, s):
    """頂点sを含むgraphが二部グラフかどうかを判定する"""
    n = len(graph)
    stack = [s]
    visited[s] = 0
    is_bi = True
    while stack:
        v = stack.pop()
        for nxt_v in graph[v]:
            if visited[nxt_v] == -1:
                visited[nxt_v] = visited[v] ^ 1
                stack.append(nxt_v)
            elif visited[nxt_v] ^ visited[v] == 0:
                is_bi = False
    return is_bi


n, m = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(m)]


uf = UnionFind(n)
graph = [[] for i in range(n)]
for a, b in edges:
    a -= 1
    b -= 1
    uf.merge(a, b)
    graph[a].append(b)
    graph[b].append(a)


# 連結成分1の要素数
cnt1 = 0
for v in range(n):
    if uf.get_size(v) == 1:
        cnt1 += 1

# 連結成分が1ではない連結成分で二部グラフをなす個数
cnt_bi = 0
# 連結成分が1ではない連結成分で二部グラフをなさない個数
cnt_not_bi = 0

visited = [-1] * n
for v in range(n):
    if visited[v] == -1:
        flag = is_bipartite(graph, v)
        if uf.get_size(v) == 1:
            continue
        if flag:
            cnt_bi += 1
        else:
            cnt_not_bi += 1

ans = n ** 2 - (n - cnt1) ** 2
cnt = cnt_bi + cnt_not_bi
ans += 2 * (cnt_bi ** 2) + (cnt ** 2) - (cnt_bi ** 2)
print(ans)

Submission status: Accepted

Solution code:
import sys


def check_bipartite(s, links, visited):
    q = [(s, 0)]
    is_bipartite = True
    count = 0
    while q:
        v, color = q.pop()
        if visited[v] != -1:
            if visited[v] != color:
                is_bipartite = False
            continue
        visited[v] = color
        count += 1
        new_color = color ^ 1
        for u in links[v]:
            if visited[u] != -1:
                if visited[u] != new_color:
                    is_bipartite = False
                continue
            q.append((u, new_color))
    return is_bipartite, count


n, m = map(int, sys.stdin.buffer.readline().split())
links = [set() for _ in range(n)]
mp = map(int, sys.stdin.buffer.read().split())
for u, v in zip(mp, mp):
    u -= 1
    v -= 1
    links[u].add(v)
    links[v].add(u)

visited = [-1] * n
count_bipartite = 0
count_non_bipartite = 0
count_isolated = 0
ans = 0
for v in range(n):
    if visited[v] != -1:
        continue
    is_bipartite, count = check_bipartite(v, links, visited)
    if count == 1:
        count_isolated += 1
    elif is_bipartite:
        count_bipartite += 1
    else:
        count_non_bipartite += 1

ans = count_isolated * (n * 2 - count_isolated)
ans += count_non_bipartite * (count_non_bipartite + count_bipartite * 2)
ans += count_bipartite ** 2 * 2

print(ans)

Submission status: Accepted

Solution code:
import sys
input = lambda : sys.stdin.readline().rstrip()
sys.setrecursionlimit(max(1000, 10**9))
write = lambda x: sys.stdout.write(x+"\n")


n,m = list(map(int, input().split()))
from collections import defaultdict
ns = defaultdict(set)
for i in range(m):
    a,b = map(int, input().split())
    a -= 1
    b -= 1
    ns[a].add(b)
    ns[b].add(a)

# 二部グラフ判定 bipertite
cs = [None]*n
def is_bip(u):
    q = [start]
    cs[start] = 1
    v1 = 1
    v0 = 0
    bip = True
    while q:
        u = q.pop()
        c = cs[u]
        cc = int(not c)
        for v in ns[u]:
            if cs[v] is None:
                cs[v] = cc
                if cc==0:
                    v0 += 1
                else:
                    v1 += 1
                q.append(v)
            elif cs[v]==c:
                bip = False
    if bip:
        return True, v0, v1
    else:
        return False, v0+v1, 0
types = []
vals = []
ans = 0
n0 = 0
n1 = 0
n2 = 0
nv = 0
for start in range(n):
    if cs[start] is not None:
        continue
    res, v0, v1 = is_bip(start)
#     print(res, v0,v1)
    if v0+v1==1:
        # 孤立点
        n0 += 1
    elif res:
        # 二部グラフ
        nv += (v0+v1)
        n1 += 1
    else:
        nv += (v0+v1)
        n2 += 1
ans += n0*nv*2
ans += n0**2
ans += (n1+n2)**2 + n1**2
print(ans)

Submission status: Accepted

Solution code:
import sys
input =  sys.stdin.readline

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  G[u].append(v)
  G[v].append(u)
seen = [-1]*n
p, q, r = 0, 0, 0
def dfs(v):
  stack = [(v, 0)]
  seen[v] = 0
  f = False
  while stack:
    v, c = stack.pop()
    for nv in G[v]:
      if seen[nv] == -1:
        seen[nv] = c^1
        stack.append((nv, c^1))
      else:
        if seen[nv]^c == 0:
          f = True
  return f
for v in range(n):
  if seen[v] != -1:
    continue
  if not G[v]:
    r += 1
  else:
    if dfs(v):
      p += 1
    else:
      q += 1
ans = r*(2*n-r) + (p+q)*(p+q) + q*q
print(ans)

Submission status: Accepted

Solution code:
import sys
input =  sys.stdin.readline

n, m = map(int, input().split())
G = [[] for _ in range(n)]
for _ in range(m):
  u, v = map(int, input().split())
  u -= 1
  v -= 1
  G[u].append(v)
  G[v].append(u)
seen = [-1]*n
p, q, r = 0, 0, 0
def dfs(v):
  global p, q
  stack = [(v, 0)]
  seen[v] = 0
  f = False
  while stack:
    v, c = stack.pop()
    for nv in G[v]:
      if seen[nv] == -1:
        seen[nv] = c^1
        stack.append((nv, c^1))
      else:
        if seen[nv]^c == 0:
          f = True
  if f:
    p += 1
  else:
    q += 1
for v in range(n):
  if seen[v] != -1:
    continue
  if not G[v]:
    r += 1
  else:
    dfs(v)
ans = r*(2*n-r) + (p+q)*(p+q) + q*q
print(ans)

Submission status: Accepted

Solution code:
import sys

read = sys.stdin.buffer.read
readline = sys.stdin.buffer.readline
readlines = sys.stdin.buffer.readlines

N, M = map(int, readline().split())
m = map(int, read().split())
G = [[] for _ in range(N + 1)]
for a, b in zip(m, m):
    G[a].append(b)
    G[b].append(a)

comp = [0] * (N + 1)
comp_size = [0] * (N + 1)
is_bipartite = [1] * (N + 1)
color = [0] * (N + 1)

for r in range(1, N + 1):
    if comp[r]:
        continue
    comp[r] = r
    comp_size[r] = 1
    stack = [r]
    while stack:
        v = stack.pop()
        for w in G[v]:
            if comp[w]:
                if color[v] == color[w]:
                    is_bipartite[r] = 0
                continue
            comp[w] = r
            comp_size[r] += 1
            color[w] = 1 ^ color[v]
            stack.append(w)

a, b, c = 0, 0, 0  # point,odd,even
for r in range(1, N + 1):
    if r != comp[r]:
        continue
    if comp_size[r] == 1:
        a += 1
    elif is_bipartite[r]:
        c += 1
    else:
        b += 1

x = 2 * a * N - a * a + b * b + 2 * b * c + 2 * c * c
print(x)

Submission status: Accepted

Solution code:
import sys

input=sys.stdin.readline

N,M=map(int,input().split())
edge=[[] for i in range(N)]
for i in range(M):
    u,v=map(int,input().split())
    edge[u-1].append(v-1)
    edge[v-1].append(u-1)

def is_bipartgraph():
    color=[0]*N
    used=[False]*N
    b=0
    nb=0
    for i in range(N):
        if not used[i]:
            flag=True
            stack=[(i,1)]
            black=0
            white=0
            while stack:
                v,c=stack.pop()
                if not used[v]:
                    color[v]=c
                    black+=(c==1)
                    white+=(c==-1)
                    used[v]=True
                    for nv in edge[v]:
                        if color[nv]==color[v]:
                            flag=False
                        elif color[nv]==0:
                            stack.append((nv,-c))
            b+=flag
            nb+=(not flag)
    return (b,nb)

a=0
for i in range(N):
    if not edge[i]:
        a+=1

b,nb=is_bipartgraph()
rest=N-(b+nb)
b-=a
print(a*N+nb*(a+nb+b)+b*(a+nb+2*b)+rest*a)

Submission status: Accepted

Solution code:
n,m = map(int,input().split())
ab = [list(map(int,input().split())) for i in range(m)]
graph = [[] for i in range(n+1)]
for a,b in ab:
  graph[a].append(b)
  graph[b].append(a)
l,s,c = 0,0,0
vis = [-1]*(n+1)
stack = []
for i in range(1,n+1):
  if vis[i] == -1:
    stack.append(i)
    flg = 0
    vis[i] = 1
    while stack:
      x = stack.pop()
      if not graph[x]:
        flg = 2
      for y in graph[x]:
        if vis[y] == -1:
          vis[y] = vis[x]+1
          stack.append(y)
        elif vis[y]%2 == vis[x]%2:
          flg = 1
    if flg == 0:
      s += 1
    if flg == 1:
      c += 1
    if flg == 2:
      l += 1
print(2*n*l-l**2+2*s*s+(s+c)**2-s**2)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N, M = map(int, input().split())
graph = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)

D = [-1]*N
def bfs(s):
    isBi = True
    q = [s]
    D[s] = 0
    d = 0
    while q:
        qq = []
        d ^= 1
        for p in q:
            for np in graph[p]:
                if D[np] == -1:
                    D[np] = d
                    qq.append(np)
                elif D[np] != d:
                    isBi = False
        q = qq
    return isBi

a = 0
b = 0
c = 0
for n in range(N):
    if D[n] == -1:
        if len(graph[n]) == 0:
            c += 1
        elif bfs(n):
            a += 1
        else:
            b += 1

ans = 2*a**2 + 2*a*b + b**2 + 2*N*c - c**2
print(ans)

Submission status: Accepted

Solution code:
import sys
readline = sys.stdin.readline

def check(s, Edge):
    stack = [s]
    col[s] = False
    res = True
    while stack:
        vn = stack.pop()
        for vf in Edge[vn]:
            if vf in used:
                if col[vn] == col[vf]:
                    res = False
            else:
                col[vf] = not col[vn]
                used.add(vf)
                stack.append(vf)
    return res

N, M = map(int, readline().split())

Edge = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, readline().split())
    a -= 1
    b -= 1
    Edge[a].append(b)
    Edge[b].append(a)


bip = 0
nb = 0
po = 0
used = set()
col = [None]*N
for i in range(N):
    if i in used:
        continue
    used.add(i)
    if not Edge[i]:
        po += 1
        continue
    if check(i, Edge):
        bip += 1
    else:
        nb += 1
print(2*bip**2+2*nb*bip+nb**2+N**2-(N-po)**2)

Submission status: Accepted

Solution code:
import sys
def input():
	return sys.stdin.readline()[:-1]

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
for _ in range(m):
	u, v = map(int, input().split())
	adj[u-1].append(v-1)
	adj[v-1].append(u-1)

visited = [-1 for _ in range(n)]
even, odd = 0, 0

def dfs(start):
	global even, odd
	odd_loop = False
	stack = [(start, -1)]
	while stack:
		x, p = stack.pop()
		for v in adj[x]:
			if v == p:
				continue
			elif visited[v] == -1:
				visited[v] = 1^visited[x]
				stack.append((v, x))
			elif visited[v] != 1^visited[x]:
				odd_loop = True

	if odd_loop:
		odd += 1
	else:
		even += 1
	return

alone = 0
for i in range(n):
	if not adj[i]:
		alone += 1
	elif visited[i] == -1:
		visited[i] = 0
		dfs(i)

ans = 2*even + odd + 2*even*(even-1) + 2*even*odd + odd*(odd-1)
ans += alone*(2*n-alone)

print(ans)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline

N,M = map(int,input().split())
UV = [[int(x) for x in row.split()] for row in sys.stdin.readlines()]

graph = [[] for _ in range(N+1)]
for u,v in UV:
    graph[u].append(v)
    graph[v].append(u)

color = [None] * (N+1)

def calc_comp_data(v):
    c = 0
    q = [v]
    color[v] = 0
    is_bipartite = True
    size = 1
    while q:
        qq = []
        c ^= 1
        for x in q:
            for y in graph[x]:
                if color[y] is None:
                    color[y] = c
                    qq.append(y)
                    size += 1
                elif color[y] == c:
                    continue
                else:
                    is_bipartite = False
        q = qq
    return size,is_bipartite

size = []
is_bipartite = []
for v in range(1,N+1):
    if color[v] is not None:
        continue
    x,y = calc_comp_data(v)
    size.append(x)
    is_bipartite.append(y)

size,is_bipartite

n_point = sum(1 if s == 1 else 0 for s in size)
n_component = len(size)
n_bipartitle = sum(1 if s >= 2 and bl else 0 for s,bl in zip(size,is_bipartite))

answer = 0
for s,bl in zip(size,is_bipartite):
    if s == 1:
        # 第1成分が1点のとき
        answer += N
    elif not bl:
        # 第1成分が2点以上、非二部グラフ
        # 成分の個数が足される
        answer += (n_component - n_point) + s*n_point
    else:
        # 第1成分が2点以上の二部グラフ
        # 相手が2点以上の二部グラフなら、2つできる
        answer += (n_component - n_point) + n_bipartitle + s*n_point

print(answer)