Problem:


Score : 500 points

Problem Statement

Rng has a connected undirected graph with N vertices.
Currently, there are M edges in the graph, and the i-th edge connects Vertices A_i and B_i.

Rng will add new edges to the graph by repeating the following operation:

Operation: Choose u and v (u \neq v) such that Vertex v can be reached by traversing exactly three edges from Vertex u, and add an edge connecting Vertices u and v. It is not allowed to add an edge if there is already an edge connecting Vertices u and v.

Find the maximum possible number of edges that can be added.

Constraints

2 \leq N \leq 10^5

1 \leq M \leq 10^5

1 \leq A_i,B_i \leq N

The graph has no self-loops or multiple edges.

The graph is connected.

Input

Input is given from Standard Input in the following format:

N M
A_1 B_1
A_2 B_2
:
A_M B_M

Output

Find the maximum possible number of edges that can be added.

Sample Input 1

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

Sample Output 1

4

If we add edges as shown below, four edges can be added, and no more.

Sample Input 2

5 5
1 2
2 3
3 1
5 4
5 1

Sample Output 2

5

Five edges can be added, for example, as follows:

Add an edge connecting Vertex 5 and Vertex 3.

Add an edge connecting Vertex 5 and Vertex 2.

Add an edge connecting Vertex 4 and Vertex 1.

Add an edge connecting Vertex 4 and Vertex 2.

Add an edge connecting Vertex 4 and Vertex 3.



Sample input:
6 5
1 2
2 3
3 4
4 5
5 6


Sample output:
4

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
edges=[[] for i in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  edges[a-1]+=[b-1]
  edges[b-1]+=[a-1]
#print(edges)
ans=0
#奇数へいろを検出する0から(N//2)*2+1ステップ進んだ時, 0に戻れたらアウト
m=(N//2)*2+1
plist=[[] for i in range(m+1)]
plist[0]=[0]
for i in range(m):#iはステップ数
  for label in plist[i]:
    plist[i+1]+=edges[label]
  plist[i+1]=list(set(plist[i+1]))
print(plist,plist[m])
if 0 in plist[m]:
  print((N*(N-1))//2-M)#奇数要素の閉路があった場合は全ての頂点を結べる. 
else:
  if N%2==0:
    n=N//2
    print(n,n*(n-1)-M)
  else:
    n1=N//2
    n2=N//2+1
    print(n1,n2)
    print((n1*(n1-1))//2+(n2*(n2-1))//2-M)

Submission status: Wrong Answer

Solution code:
#!usr/bim/python
#! -*- coding: utf-8 -*-

nm = raw_input()
nm = nm.split()
n,m = map(int,nm)

tree = []
for i in range(n):
    tree.append([])

for i in range(m):
    ab = raw_input()
    ab = ab.split()
    a,b = map(int,ab)
    a -= 1
    b -= 1
    tree[a].append(b)
    tree[b].append(a)

status = 0
x = []
y = []

x.append(0)
for j in tree[0]:
    y.append(j)

while 1:
    flag = 0
    for i in range(n):
        if i in x:
            for b in tree[i]:
                if b in x:
                    status = 1
                    break
                elif b in y:
                    pass
                else:
                    y.append(b)
        elif i in y:
            for b in tree[i]:
                if b in y:
                    status = 1
                    break
                elif b in x:
                    pass
                else:
                    x.append(b)
        else:
            pass
            flag = 1
    if flag == 0:
        break
    else:
        pass

#print x
#print y
#print status,flag

p = n**2/4
q = n*(n-1)/2

if status == 0:
    print p - m
else:
    print q - m

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
edges=[[] for i in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  edges[a-1]+=[b-1]
  edges[b-1]+=[a-1]
for i in range(N): edges[i]+=[i]
#print(edges)
ans=0
#奇数へいろを検出する0から(N//2)*2+1ステップ進んだ時, 0に戻れたらアウト
m=(N//2)*2+1
plist=[[] for i in range(m+1)]
plist[0]=[0]
for i in range(m):#2はステップ数
  for label in plist[i]:
    plist[i+1]+=edges[label]
  plist[i+1]=list(set(plist[i+1]))
#print(plist,plist[m])
#頂点kから出発する. list[0]=[k]. list[i]を頂点0からiステップで行ける場所を表し, 
#i-jが奇数となるとき, list[i]とlist[j]に含まれる頂点を繋ぐか判定する. 
if 0 in plist[m]:
  print((N*(N-1))//2-M)#奇数要素の閉路があった場合は全ての頂点を結べる.

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
edges=[[] for i in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  edges[a-1]+=[b-1]
  edges[b-1]+=[a-1]
for i in range(N): edges[i]+=[i]
#print(edges)
ans=0
#頂点kから出発する. list[0]=[k]. list[i]を頂点0からiステップで行ける場所を表し, 
#i-jが奇数となるとき, list[i]とlist[j]に含まれる頂点を繋ぐか判定する. 
print((N*(N-1))//2-M)

Submission status: Wrong Answer

Solution code:
#c.py
data = input().split()
N = int(data[0])
M = int(data[1])
graph = [[0 for x in range(N)] for y in range(N)]

for i in range(M):
    array = input().split()
    a = int(array[0])-1
    b = int(array[1])-1
    graph[a][b] = 1
    graph[b][a] = 1
    
answer = 0
ii = []
for i in range(N):
    for j in range(N):
        if(graph[i][j]==1):
            ii.append(j)
    jj = []
    for j in ii:
        for k in range(N):
            if(graph[j][k]==1):
                jj.append(k)
        kk = []
        for l in range(N):
            if(graph[k][l]==1 and graph[i][l]!=1):
                graph[i][l]=1
                graph[l][i]=1
                answer+=1

print(answer)

Submission status: Wrong Answer

Solution code:
N, M = map(int, input().split())
for _ in range(M):
    A, B = map(int, input().split())
    
print(N*(N-1) // 2 - M)

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
N ,M  =list(map(int,input().split()))
AB =[ [int(x)-1 for x in input().split()] for _ in range(M)]

d =defaultdict(list)

for a,b in AB:
    d[a].append(b)
    d[b].append(a)



def check(i):
    dists = [-1 for _  in range(N)]
    dists[i]=0
    #q = deque([ (1,val)for val in d[i]])
    visited = [False for _ in range(N)]
    visited[i]=True
    q= deque([(0,i)])
    while q:
        #print(dists,q)
        dist,now = q.popleft()
        #visited[now]=True
        if dists[now]==-1:
            dists[now]= dist
        for val in d[now]:
            if not visited[val]:
                q.append((dist+1,val))
                visited[val]=True
            else:
                #check loop
                if dists[val] %2 != (dist+1)%2:
                    return True
    #print(dists)
    odds = []
    evens = []
    for i,_d in enumerate(dists):
        if _d%2 ==0:
            odds.append(i)
        else:
            evens.append(i)
    return odds,evens

res = check(0)
if res is True:
    print(N*(N-1)//2 -M)
else:
    odds,evens = res
    ans =0
    print( len(odds)*(len(odds)-1)//2
          +len(evens)*(len(evens)-1)//2 - (M-N+1)- (N-1)//2 )

    """
    for i in odds:
        ans += len(odds) -sum(  val in evens for val in d[i])
    for i in evens:
        ans += len(evens) - sum(val in odds for val in d[i])
    print(ans//2)
    """

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
N ,M  =list(map(int,input().split()))
AB =[ [int(x)-1 for x in input().split()] for _ in range(M)]

d =defaultdict(list)

for a,b in AB:
    d[a].append(b)
    d[b].append(a)



def check(i):
    dists = [-1 for _  in range(N)]
    dists[i]=0
    #q = deque([ (1,val)for val in d[i]])
    visited = [False for _ in range(N)]
    visited[i]=True
    q= deque([(0,i)])
    while q:
        #print(dists,q)
        dist,now = q.popleft()
        #visited[now]=True
        if dists[now]==-1:
            dists[now]= dist
        for val in d[now]:
            if not visited[val]:
                q.append((dist+1,val))
                visited[val]=True
            else:
                #check loop
                if dists[val] %2 != (dist+1)%2:
                    return True
    #print(dists)
    odds = []
    evens = []
    for i,_d in enumerate(dists):
        if _d%2 ==0:
            odds.append(i)
        else:
            evens.append(i)
    return odds,evens

res = check(0)
if res is True:
    print(N*(N-1)//2 -M)
else:
    odds,evens = res
    ans =0
    print( len(odds)*(len(odds)-1)//2
          +len(evens)*(len(evens)-1)//2 - (N-1)//2 )

    """
    for i in odds:
        ans += len(odds) -sum(  val in evens for val in d[i])
    for i in evens:
        ans += len(evens) - sum(val in odds for val in d[i])
    print(ans//2)
    """

Submission status: Wrong Answer

Solution code:
import collections

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

E = collections.defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)

count = 0

for u in range(1, N + 1):
    S = set()
    for t in E[u]:
        S.add(t)

    SS = set()
    for t in S:
        SS |= set(E[t])

    V = set()
    for t in SS:
        V |= set(E[t])

    for v in V:
        if v == u or v == u + 1:
            continue
        if v not in E[u]:
            E[u].append(v)
            E[v].append(u)
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
N,M=map(int,input().split())
edges=[[] for i in range(N)]
for i in range(M):
  a,b = map(int,input().split())
  edges[a-1]+=[b-1]
  edges[b-1]+=[a-1]
for i in range(N): edges[i]+=[i]
#print(edges)
ans=0
#頂点kから出発する. list[0]=[k]. list[i]を頂点0からiステップで行ける場所を表し, 
#i-jが奇数となるとき, list[i]とlist[j]に含まれる頂点を繋ぐか判定する. 
for j in range(N):#jは繰り返しの回数
  for k in range(N):
    plist=[[] for i in range(4)]
    plist[0]=[k]
    for i in range(3):#2はステップ数
      for label in plist[i]:
        plist[i+1]+=edges[label]
      plist[i+1]=list(set(plist[i+1]))
    #plist[3]は頂点k から３ステップで行ける頂点
    for edge in plist[3]:
      if edge not in edges[k]:
        edges[k]+=[edge]
        edges[edge]+=[k]
        ans+=1
        #print(edge,k,"つないだ")
    #print(plist[3])
print(ans)

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
N ,M  =list(map(int,input().split()))
AB =[ [int(x)-1 for x in input().split()] for _ in range(M)]

d =defaultdict(list)

for a,b in AB:
    d[a].append(b)
    d[b].append(a)



def check(i):
    dists = [-1 for _  in range(N)]
    dists[i]=0
    #q = deque([ (1,val)for val in d[i]])
    visited = [False for _ in range(N)]
    visited[i]=True
    q= deque([(0,i)])
    while q:
        #print(dists,q)
        dist,now = q.popleft()
        #visited[now]=True
        if dists[now]==-1:
            dists[now]= dist
        for val in d[now]:
            if not visited[val]:
                q.append((dist+1,val))
                visited[val]=True
            else:
                #check loop
                if dists[val] %2 != (dist+1)%2:
                    return True
    #print(dists)
    odds = []
    evens = []
    for i,_d in enumerate(dists):
        if _d%2 ==0:
            odds.append(i)
        else:
            evens.append(i)
    return odds,evens

res = check(0)
if res is True:
    print(N*(N-1)//2 -M)
else:
    odds,evens = res
    ans =0
    print(len(odds)*len(evens)//2 - (M-N+1))

    """
    for i in odds:
        ans += len(odds) -sum(  val in evens for val in d[i])
    for i in evens:
        ans += len(evens) - sum(val in odds for val in d[i])
    print(ans//2)
    """

Submission status: Wrong Answer

Solution code:
# encoding:utf-8

def renameNodes(nodes):
	new_nodes = []
	dict_nodes = {}
	for x in nodes:
		if x[0] in dict_nodes:
			frm = dict_nodes[x[0]]
		else:
			frm = len(dict_nodes)
			dict_nodes[x[0]] = frm

		if x[1] in dict_nodes:
			to = dict_nodes[x[1]]
		else:
			to = len(dict_nodes)
			dict_nodes[x[1]] = to
		new_nodes.append([frm, to])
	return new_nodes

def judge(new_nodes):
	for x in new_nodes:
		if x[0] % 2 == x[1] % 2:
			return False
	return True 


def main():
	n, m = list(map(int, input().split()))
	nodes = [list(map(int, input().split())) for _ in range(m)]

	if judge(renameNodes(nodes)):
		ans = (((n + 1) // 2) * ((n // 2 ))) - m
		print(int(ans))
	else:
		ans = (n - 1) * n / 2 - m 
		print(int(ans))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
# encoding:utf-8

def main():
	n, m = list(map(int, input().split()))
	if m == n - 1:
		ans = (((n + 1) // 2) * ((n // 2 )))  - m
		print(int(ans))
	else:
		ans = (n - 1) * n / 2 - m 
		print(int(ans))

if __name__ == '__main__':
	main()

Submission status: Wrong Answer

Solution code:
from collections import deque,defaultdict
N ,M  =list(map(int,input().split()))
AB =[ [int(x)-1 for x in input().split()] for _ in range(M)]

d =defaultdict(list)

for a,b in AB:
    d[a].append(b)
    d[b].append(a)



def check(i):
    dists = [-1 for _  in range(N)]
    dists[i]=0
    q = deque([ (1,val)for val in d[i]])
    visited = [False for _ in range(N)]

    while q:
        #print(dists,q)
        dist,now = q.popleft()
        visited[now]=True
        if dists[now]==-1:
            dists[now]= dist
        for val in d[now]:
            if not visited[val]:
                q.append((dist+1,val))
            else:
                #check loop
                if dists[val] %2 != (dist+1)%2:
                    return True
    #print(dists)
    odds = []
    evens = []
    for i,_d in enumerate(dists):
        if _d%2 ==0:
            odds.append(i)
        else:
            evens.append(i)
    return odds,evens

res = check(0)

if res is True:
    print(N*(N-1)//2 -M)
else:
    odds,evens = res
    ans =0
    for i in odds:
        ans += len(odds) -sum(  val in evens for val in d[i])
    for i in evens:
        ans += len(evens) - sum(val in odds for val in d[i])
    print(ans//2)

Submission status: Wrong Answer

Solution code:
import collections

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

E = collections.defaultdict(list)
for i in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)

count = 0

for u in range(1, N + 1):
    S = set()
    for t in E[u]:
        S.add(t)

    SS = set()
    for t in S:
        SS |= set(E[t])

    V = set()
    for t in SS:
        V |= set(E[t])

    for v in V:
        if v == u:
            continue
        if v not in E[u]:
            E[u].append(v)
            E[v].append(u)
            count += 1

print(count)

Submission status: Wrong Answer

Solution code:
def bfs3(root, depth, closed, result):
    if root in closed:
        return
    if depth == 3:
        result.append(root)
        return
    closed.add(root)
    for v in edges[root]:
        bfs3(v, depth + 1, closed, result)

n, m = tuple(map(int, input().split()))
edges = {}
for i in range(m):
    a, b = tuple(map(int, input().split()))
    if a not in edges:
        edges[a] = set([b])
    else:
        edges[a].add(b)

    if b not in edges:
        edges[b] = set([a])
    else:
        edges[b].add(a)

total = 0
while True:
    changed = False
    for v in edges.keys():
        v3 = []
        bfs3(v, 0, set(), v3)
        for v3v in v3:
            if v3v not in edges[v]:
                edges[v].add(v3v)
                edges[v3v].add(v)
                total += 1
                changed = True
    if not changed:
        break

print(total)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
graph=[[] for _ in range(N)]
table=[[0]*N for _ in range(N)]

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

def steps(a,b,cnt=0):
    global flag
    global ans
    if cnt==3:
        if a!=b and not table[a][b]: 
            graph[a].append(b)
            graph[b].append(a)
            table[a][b]=1
            table[b][a]=1
            flag=True
            ans=ans+1
        return

    for nb in graph[b]:
        steps(a,nb,cnt+1)

flag=True
ans=0
while flag:
    flag=False
    for i in range(N):
        steps(i,i)
print(ans)

Submission status: Time Limit Exceeded

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

for i in range(m):
    a, b = map(int, input().split())
    a-=1; b-=1
    g[a].append(b)
    g[b].append(a)

visited = [False] * n
def dfs(i, src, depth=0):
    global ans
    if depth==3:
        if not i in g[src]:
            g[src].append(i)
            g[i].append(src)
            ans+=1
    else:
        for t in g[i]:
            if visited[t]:
                continue
            else:
                visited[t] = True
                dfs(t, src, depth+1)
                visited[t] = False
    return

ans = 0
for i in range(n):
    visited[i] = True
    dfs(i, i, 0)
    visited[i] = False
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
def is_bipartite(s=0):
    visited = [False] * N
    colors = [-1] * N
    stack = deque([(0, 0)])
    while stack:
        c, v = stack.pop()
        visited[v] = True
        colors[v] = c
        for u in E[v]:
            if visited[u] == True and (c ^ 1) != colors[u]:
                return False, colors
            if visited[u]:
                continue
            stack.append((c ^ 1, u))
    return True, colors

N, M = map(int, input().split())
E = [[] for _ in range(N)]
for _ in range(M):
    a, b = map(int, input().split())
    E[a-1].append(b-1)
    E[b-1].append(a-1)
f, bi = is_bipartite()
if f:
    b = sum(bi)
    w = N - b
    print(b * w - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

N,M = map(int,input().split())
edges = [[] for _ in range(N+1)]
for _ in range(M):
    a,b = map(int,input().split())
    edges[a].append(b)
    edges[b].append(a)
n = len(edges)
colors = [-1]*(n+1)

def paint(v,c):
    if colors[v] == -1:
        colors[v] = c
        nxC = (c+1)%2
        for nxV in edges[v]:
            result = paint(nxV,nxC)
            if result == False:
                return result
    else:
        if colors[v] != c:
            return False
    return True
    
if paint(1,0):
    ans = colors.count(1)*colors.count(0)-M
else:
    def choose(n,k):
        import math
        return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
    ans = choose(N,2)-M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

N,M = map(int,input().split())
edges = [[]for _ in range(N+1)]
for _ in range(M):
    u,v = map(int,input().split())
    edges[u].append(v)
    edges[v].append(u)

colors = [-1]*(N+1)
def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
def dfs(n,c):
    if colors[n] == -1:
        colors[n] = c
        for nx in edges[n]:
            dfs(nx,(c+1)%2)
    else:
        if colors[n] != c:
            print(choose(N,2)-M)
            exit()
dfs(1,0)
white = colors.count(0)
black = N - white
print(white*black-M)

Submission status: Time Limit Exceeded

Solution code:
def main():
    import sys
    input = sys.stdin.readline
    sys.setrecursionlimit(200000)

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

    colors = [-1]*(N+1)
    def paint(n,p,c):
        ret = 1
        if colors[n]!=-1 and colors[n]!=c:
            ret = 0
        else:
            colors[n] = c
            for nx in edges[n]:
                if nx != p:
                    ret = min(ret,paint(nx,n,(c+1)%2))
        return ret

    def choose(n,k):
        import math
        return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))
    res = paint(1,0,1)
    if res == 0:
        ans = choose(N,2)-M
    else:
        ans = colors.count(0)*(N-colors.count(0))-M

    print(ans)

main()

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    
def dfs(v, G, depth):
    if depth == 3:
        if v not in G[u]:
            G[u].append(v)
            G[v].append(u)
            return 1
        else: return 0
        
    seen[v] = True
    
    count = 0
    for next_v in G[v]:
        if seen[next_v] == True:
            continue
        count += dfs(next_v, G, depth+1)
    
    seen[v] = False
    return count

ans = 0
seen = [False for j in range(N)]
for i in range(N):
    u = v = i
    ans += dfs(v, G, 0)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    G[a-1].append(b-1)
    G[b-1].append(a-1)
    
def dfs(v, G, depth):
    if depth == 3:
        if v not in G[u]:
            G[u].append(v)
            G[v].append(u)
            return 1
        else: return 0
        
    seen[v] = True
    
    count = 0
    for next_v in G[v]:
        if seen[next_v] == True:
            continue
        count += dfs(next_v, G, depth+1)
    
    seen[v] = False
    return count

ans = 0
for i in range(N):
    seen = [False for j in range(N)]
    u = v = i
    ans += dfs(v, G, 0)
    
print(ans)

Submission status: Time Limit Exceeded

Solution code:
#!/usr/bin/env python3
import sys
import collections

sys.setrecursionlimit(10 ** 7)

# 1 ✕ N
N, M = list(map(int, input().rstrip().split()))

# N ✕ M
A = list(tuple(map(int, input().rstrip().split())) for _ in range(M))

items = [set() for _ in range(N)]
for i in range(M):
    a, b = A[i]
    items[a - 1].add(b - 1)
    items[b - 1].add(a - 1)

# print(items)

init = 0
for i in items:
    init += len(i)

# print(ans)
while True:
    found = False
    for n in range(N):
        # print("-----")

        t = items[n]
        # print(t)
        k = set()
        for i in t:
            k.update(items[i])

        # print(k)
        k2 = set()
        for i in k:
            k2.update(items[i])

        # print(k2)
        if n in k2:
            k2.remove(n)

        if t != k2:
            items[n] = k2
            found = True

    if not found:
        break

end = 0
for i in items:
    end += len(i)
print(int((end - init) / 2))
# print(len(items))
# print((len(items) - ans) / 2)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
edges = [list(map(int, input().split())) for i in range(M)]

#隣接リストで管理
adj = [[] for j in range(N)]
for edge in edges:
    x, y = edge
    adj[x-1].append(y)
    adj[y-1].append(x)
cnt = 0

def dfs(t, start, past, now):
    global cnt
    if t == 3:
        if not now in adj[start-1] and now != start:
            adj[start-1].append(now)
            adj[now-1].append(start)
            cnt += 1
    else:
        for node in adj[now-1]:
            if node != past:
                dfs(t+1, start, now, node)

for j in range(1,N+1):
    dfs(0, j, j, j)

print(cnt)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(200000)

N,M = map(int,input().split())
edges = [[]for _ in range(N+1)]
for _ in range(M):
    A,B = map(int,input().split())
    edges[A].append(B)
    edges[B].append(A)

def judgeBiGragh(edges):
    n = len(edges)
    colors = [-1]*(n+1)
    def paint(v,c):
        if colors[v] == -1:
            colors[v] = c
            nxC = (c+1)%2
            for nxV in edges[v]:
                result = paint(nxV,nxC)
                if result == False:
                    return result
        else:
            if colors[v] != c:
                return False
        return True
    return paint(1,0),colors.count(1)

def choose(n,k):
    import math
    return math.factorial(n)//(math.factorial(n-k)*math.factorial(k))

res1,res2 = judgeBiGragh(edges)
if res1:
    print(res2*(N-res2) - M)
else:
    print(choose(N,2)-M)

Submission status: Time Limit Exceeded

Solution code:
import sys

sys.setrecursionlimit(1000000)


def dfs(g: {}, v: int, path_list: [], added: {}):
    path_list.append(v)
    for next_v in g[v]:
        # # next_v が探索済だったらスルー
        if next_v in path_list:
            continue
        # 距離３なら追加可能か確認して次へ
        if len(path_list) == 3:
            if path_list[0] not in g[next_v]:
                dic_a = added.setdefault(path_list[0], set())
                dic_a.add(next_v)
                dic_b = added.setdefault(next_v, set())
                dic_b.add(path_list[0])
        # 距離1なら複製して次へ
        elif len(path_list) == 1:
            copied = [v]
            dfs(g, next_v, copied, added)
        # 距離2なら複製して次へ
        elif len(path_list) == 2:
            copied = path_list.copy()
            dfs(g, next_v, copied, added)


def main():
    n, m = map(int, input().split())

    g = {}
    for i in range(m):
        a, b = map(int, input().split())
        dic_a = g.setdefault(a-1, set())
        dic_a.add(b-1)
        dic_b = g.setdefault(b-1, set())
        dic_b.add(a-1)
    count = 0
    while True:
        added = {}
        for i in range(n):
            dfs(g, i, [], added)
        added_cnt = 0
        for _set in added.values():
            added_cnt += len(_set)
        if added_cnt == 0:
            break
        count += added_cnt
        for k, v in added.items():
            dic_a = g.setdefault(k, set())
            for v_item in v:
                dic_a.add(v_item)
    print(int(count/2))



main()

Submission status: Time Limit Exceeded

Solution code:
# 解説AC
N,M = map(int, input().split())
edge = [[] for _ in range(N)]
for _ in range(M):
    a,b = map(int, input().split())
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

color = [0] * N

def is_bipartite():
    """ 二部グラフか判定する """
    stack = [(0,1)]
    while stack:
        v, c = stack.pop()
        color[v] = c
        for w in edge[v]:
            if color[w] == c: return False
            if color[w] == 0:
                stack.append((w, (-1) * c))
    return True

if is_bipartite():
    B = color.count(1)
    W = color.count(-1)
    print(B * W - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
edges = [[] for _ in range(N)]

for _ in range(M):
    fr, to = map(int, input().split())
    fr -= 1
    to -= 1
    edges[fr].append(to)
    edges[to].append(fr)

def isBipartite():
    sign = [-1] * N
    st = [(0, 0)]
    while st:
        now, p = st.pop()
        sign[now] = p

        for to in edges[now]:
            if sign[to] == -1:
                st.append((to, (p + 1) % 2))
                continue
            if sign[to] != (p + 1) % 2:
                return -1

    return sum(sign)

s = isBipartite()

if s == -1:
    print(N * (N - 1) // 2 - M)
else:
    print(s * (N - s) - M)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(1000000)
def input():
    return sys.stdin.readline()
    
n, m = [int(i) for i in input().split()]
e = [[] for _ in range(n)]
for _ in range(m):
    a, b = [int(i) - 1 for i in input().split()]
    e[a].append(b)
    e[b].append(a)

ok = False
tag = [-1] * n


def dfs(i=0, c=0):
    global ok, tag
    if tag[i] != -1:
        if tag[i] != c:
            ok = True
        return
    tag[i] = c
    for j in e[i]:
        dfs(j, (c + 1) % 2)


dfs()

if ok:
    print(n * (n - 1) // 2 - m)
else:
    s = sum(tag)
    print(s * (n - s) - m)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    ans = 0
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    def f(vs):
        if len(vs) == 4:
            u, v = vs[0], vs[-1]
            if u not in g[v]:
                g[u].add(v)
                g[v].add(u)
                return 1
        u = vs[-1]
        r = 0
        for v in list(g[u]):
            if v not in vs:
                vs.append(v)
                r += f(vs)
                vs.pop()
        return r

    ans = 0
    while True:
        prev = ans
        for i in range(1, N+1):
            ans += f([i])
        if ans == prev:
            break

    return ans


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
import bisect
import heapq
import math
import random
import sys
from collections import Counter, defaultdict, deque
from decimal import ROUND_CEILING, ROUND_HALF_UP, Decimal
from functools import lru_cache, reduce
from itertools import combinations, combinations_with_replacement, product, permutations
from operator import add, mul, sub

sys.setrecursionlimit(100000)
input = sys.stdin.readline
INF = 2**62-1

def read_int():
    return int(input())


def read_int_n():
    return list(map(int, input().split()))


def read_float():
    return float(input())


def read_float_n():
    return list(map(float, input().split()))


def read_str():
    return input().strip()


def read_str_n():
    return list(map(str, input().split()))


def error_print(*args):
    print(*args, file=sys.stderr)


def mt(f):
    import time

    def wrap(*args, **kwargs):
        s = time.time()
        ret = f(*args, **kwargs)
        e = time.time()

        error_print(e - s, 'sec')
        return ret

    return wrap


@mt
def slv(N, M, AB):
    ans = 0
    g = defaultdict(set)
    for a, b in AB:
        g[a].add(b)
        g[b].add(a)

    def f(vs):
        if len(vs) == 4:
            return set([(vs[0], vs[-1])])
        u = vs[-1]
        ans = set()
        for v in g[u]:
            if v not in vs:
                vs.append(v)
                ans |= f(vs)
                vs.pop()
        return ans



    update = True
    ans = 0
    while update:
        update = False

        adding = set()
        for i in range(1, N+1):
            adding |= f([i])
        for a, b in adding:
            if b not in g[a]:
                g[a].add(b)
                g[b].add(a)
                update = True
                ans += 1

    return ans


def main():
    N, M = read_int_n()
    AB = [read_int_n() for _ in range(M)]
    print(slv(N, M, AB))


if __name__ == '__main__':
    main()

Submission status: Time Limit Exceeded

Solution code:
def bipartite(g):
    s = [(0, 1)]
    c = [0] * n
    while s:
        v, color = s.pop()
        c[v] = color
        for node in g[v]:
            if c[node] == c[v]:
                return False, None
            if c[node] == 0:
                s.append((node, -color))
    return True, c

n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    g[a - 1].append(b - 1)
    g[b - 1].append(a - 1)
b, colors = bipartite(g)
if b:
    x = colors.count(1)
    print(x * (n - x) - m)
else:
    print(n * (n - 1) // 2 - m)