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

Solution (Python):
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()

Solution (Python):
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)



cnt1 = 0
for v in range(n):
    if uf.get_size(v) == 1:
        cnt1 += 1


cnt_bi = 0

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)

Solution (Python):
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)

Solution (Python):
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)


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)

    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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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  
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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)

Solution (Python):
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:
        
        answer += N
    elif not bl:
        
        
        answer += (n_component - n_point) + s*n_point
    else:
        
        
        answer += (n_component - n_point) + n_bipartitle + s*n_point

print(answer)

Solution (Python):
'''
写経
https://youtu.be/cJ-WjtA34GQ?t=1899
https://atcoder.jp/contests/agc011/submissions/1157055
http://noshi91.hatenablog.com/entry/2018/04/17/183132
https://camypaper.bitbucket.io/2016/12/18/adc2016/
'''


class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]  

    def find(self, x):  
        if self.v[x] < 0:  
            return x
        else:  
            self.v[x] = self.find(self.v[x])  
            return self.v[x]

    def unite(self, x, y):  
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:  
            x, y = y, x  
        self.v[x] += self.v[y]  
        self.v[y] = x  

    def root(self, x):
        return self.v[x] < 0  

    def same(self, x, y):
        return self.find(x) == self.find(y)  

    def size(self, x):
        return -self.v[self.find(x)]  


N, M = map(int, input().split())
uf = UnionFind(2 * N)  
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    uf.unite(u, N + v)  
    uf.unite(N + u, v)  

    

alone = 0
bi = 0
unko = 0

for u in range(N):
    if uf.root(u) or uf.root(N + u): 
        if uf.size(u) == 1: 
            alone += 1
        elif uf.same(u, N + u):  
            unko += 1
        else:
            bi += 1  

ans = 0
ans += alone * N
ans += N * alone
ans -= alone * alone
ans += bi * bi * 2
ans += bi * unko
ans += unko * bi
ans += unko * unko

print(ans)

Solution (Python):



class UnionFind:
    def __init__(self, n):
        self.v = [-1 for _ in range(n)]

    def find(self, x):
        if self.v[x] < 0:
            return x
        else:
            self.v[x] = self.find(self.v[x])
            return self.v[x]

    def unite(self, x, y):
        x = self.find(x)
        y = self.find(y)
        if x == y:
            return
        if -self.v[x] < -self.v[y]:
            x, y = y, x
        self.v[x] += self.v[y]
        self.v[y] = x

    def root(self, x):
        return self.v[x] < 0

    def same(self, x, y):
        return self.find(x) == self.find(y)

    def size(self, x):
        return -self.v[self.find(x)]


N, M = map(int, input().split())
uf = UnionFind(2 * N)
for _ in range(M):
    u, v = map(int, input().split())
    u -= 1
    v -= 1
    uf.unite(u, N + v)
    uf.unite(N + u, v)

alone = 0
bi = 0
unko = 0

for u in range(N):
    if uf.root(u) or uf.root(N + u):
        if uf.size(u) == 1:
            alone += 1
        elif uf.same(u, N + u):
            unko += 1
        else:
            bi += 1

ans = 0
ans += alone * N
ans += N * alone
ans -= alone * alone
ans += bi * bi * 2
ans += bi * unko
ans += unko * bi
ans += unko * unko

print(ans)

Solution (Python):
import sys
n, m=map(int, raw_input().split())
sys.setrecursionlimit(n+1000)
adj=[[] for i in range(n+1)]
for i in range(m):
	u, v=map(int, raw_input().split())
	adj[u].append(v)
	adj[v].append(u)
isolated_cnt=0
bipartite_cnt=0
other_cnt=0
color=[0]*(n+1)
def dfs(cur):
	global ok
	for to in adj[cur]:
		if not color[to]:
			color[to]=3-color[cur]
			dfs(to)
		else:
			if color[to]!=3-color[cur]:
				ok=False
for i in range(1, n+1):
	if adj[i]:
		if not color[i]:
			color[i]=1
			ok=True
			dfs(i)
			if ok:
				bipartite_cnt+=1
			else:
				other_cnt+=1
	else:
		isolated_cnt+=1
print>>sys.stderr, isolated_cnt, bipartite_cnt, other_cnt
print isolated_cnt*n*2-isolated_cnt*isolated_cnt+bipartite_cnt*(bipartite_cnt*2+other_cnt)+other_cnt*(bipartite_cnt+other_cnt)

Solution (Python):
n,m=map(int,input().split())
vis,ci,cb,cc=[0]*(n+1),0,0,0
g=[[] for i in range(n+1)]
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:
			s,f=[(i,1)],True
			while len(s):
				u,col=s.pop()		
				if vis[u]:
					f&=(vis[u]==col)
					continue
				vis[u]=col
				for i in g[u]:
					s+=[(i,3-col)]
			cb+=f
			cc+=f^1
print(ci*ci+2*ci*(n-ci)+cc*cc+2*cb*cc+2*cb*cb)

Solution (Python):
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)

Solution (Python):
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] = 3 - done[x]
                    pu(z)
                    nu.append(z)
                y = xt[y]
        sd = 0
        pa = 0
        for x in nu:
            sd += deg[x]
            y = la[x]
            while y is not None:
                z = dat[y]
                if done[x] == done[z]:
                    pa = 1
                y = xt[y]
        if sd == 0:
            so += 1
        elif pa:
            lo += 1
        else:
            tr += 1
    print lo * lo + lo * tr * 2 + tr * tr * 2 + so * n * 2 - so * so
main()