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: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-

import sys

def input(): return sys.stdin.readline().strip()
def list2d(a, b, c): return [[c] * b for i in range(a)]
def list3d(a, b, c, d): return [[[d] * c for j in range(b)] for i in range(a)]
def list4d(a, b, c, d, e): return [[[[e] * d for j in range(c)] for j in range(b)] for i in range(a)]
def ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(N=None): return list(MAP()) if N is None else [INT() for i in range(N)]
def Yes(): print('Yes')
def No(): print('No')
def YES(): print('YES')
def NO(): print('NO')
sys.setrecursionlimit(10 ** 9)
INF = float('inf')
MOD = 10 ** 9 + 7

N, M = MAP()
nodes = tuple([] for i in range(N))
for i in range(M):
    a, b = MAP()
    a -= 1
    b -= 1
    nodes[a].append(b)
    nodes[b].append(a)

# 二部グラフ判定
color = [-1] * N
def check(u):
    stack = [(u, -1, 0)]
    while stack:
        u, prev, c = stack.pop()
        if color[u] == -1:
            color[u] = c
        elif color[u] != c:
                return False
        for v in nodes[u]:
            if v != prev:
                stack.append((v, u, 1-c))
    return True

if check(0):
    a = sum(color)
    b = N - a
    ans = a*b - M
else:
    ans = N*(N-1) // 2 - M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
from scipy.sparse.csgraph import floyd_warshall
from collections import deque
import sys
input = sys.stdin.readline
def isbipart(n,graph):  
  colors = [0 for i in range(n)]
  stack = deque([(0,1)])
  while stack:
    v,color = stack.pop()
    colors[v] = color
    for to in graph[v]:
      if colors[to] == color:
        return False
      if colors[to] == 0:
        stack.append((to,-color))
  return colors

def solve():
  n,m  =(int(i) for i in input().split())
  graph = [[] for _ in range(n)]
  for i in range(m):
    a,b = (int(i) for i in input().split())
    graph[a-1].append(b-1)
    graph[b-1].append(a-1)
  colors = isbipart(n,graph)
  if colors:
    b = colors.count(1)
    w = colors.count(-1)
    print(b*w-m)
  else:
    print(n*(n-1)//2-m)
solve()

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict
import sys
sys.setrecursionlimit(10**7)

n, m = map(int, (input().split()))
dic = defaultdict(list)
seen = [False] * (n+1)

for _ in range(m):
    a, b = map(int, input().split())
    dic[a].append(b)
    dic[b].append(a)


def dfs(v, todo,  depth):
    if depth == 3:
        if v not in dic[root]:
            global count
            count += 1
            dic[root].append(v)
            dic[v].append(root)
        return

    for new_v in todo:
        if new_v == root:
            continue
        new_todo = []
        new_todo += dic[new_v]
        new_todo.remove(v)
        dfs(new_v, new_todo, depth+1)


count = 0
for i in range(1, n+1):
    root = i
    todo = dic[i]
    dfs(i, todo, 0)

print(count)

Submission status: Time Limit Exceeded

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

graph = [[None] * N for _ in range(N)]
for x, y in edges:
    graph[x - 1][y - 1] = True
    graph[y - 1][x - 1] = True

def dfs(v, c):
    # c: color = 1 or -1
    node[v] = c
    for i, w in enumerate(graph[v]):
        if not w:
            continue

        if node[i] == c:
            return False
        
        if node[i] == 0 and not dfs(i, -c):
            return False
        
    return True

node = [0] * N
if dfs(0, 1):
    x = sum((v + 1) // 2 for v in node)
    print(x * (N - x) - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Time Limit Exceeded

Solution code:
from collections import defaultdict, deque

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

dic = defaultdict(set)
for _ in range(M):
    A, B = map(int, input().split())
    dic[A].add(B)
    dic[B].add(A)


colors = [0]*(N+1)

def dfs():
    que = deque([(1, 1)])

    while len(que):
        v, color = que.popleft()
        colors[v] = color
        for to in list(dic[v]):
            if (color == colors[to]):
                return False
            if (colors[to] == 0):
                que.append((to, -color))
                
    return True


flag = dfs()
b = colors.count(1)

print(b*(N-b) - M if (flag) else N*(N-1)//2 - M)

Submission status: Time Limit Exceeded

Solution code:
def bipartite():
    color = {v: None for v in V}
    stack = [(V[0], 0)]
    parts = {0: set([]), 1: set([])}
    while stack:
        v, c = stack.pop()
        color[v] = c
        parts[c].add(v)
        for u in E[v]:
            if color[u] is None: # not visited yet
                stack.append((u, c^1)) # paint u with different color from v's one
            elif color[u] != c: # consistent
                continue
            else: # inconsistent
                return (None, None)
    return (parts[0], parts[1])
            
N, M = map(int, input().split())
V = range(1, N+1)
E = {v: [] for v in V}
for _ in range(M):
    a, b = map(int, input().split())
    E[a].append(b)
    E[b].append(a)
p1, p2 = bipartite()
if p1 is None:
    print(N * (N-1) // 2 - M)
else:
    print(len(p1) * len(p2) - M)

Submission status: Time Limit Exceeded

Solution code:
class Graph:
    def __init__(self, V, directed=False):
        self.V = V
        self.directed = directed
        self.adj_list = {i: [] for i in self.V}
        
    def add_edge(self, u, v):
        self.adj_list[u].append(v)
        if not self.directed:
            self.adj_list[v].append(u)

def bipartite(graph):
    color = {v: None for v in graph.V}
    stack = [(graph.V[0], 0)]
    while stack:
        v, c = stack.pop()
        color[v] = c
        for u in graph.adj_list[v]:
            if color[u] is None: # not visited yet
                stack.append((u, c^1)) # paint u with different color from v's one
            elif color[u] != c: # consistent
                continue
            else: # inconsistent
                return (None, None)
    parts = {0: [], 1:[]}
    for v in graph.V:
        parts[color[v]].append(v)
    return (parts[0], parts[1])
            
N, M = map(int, input().split())
g = Graph(range(1, N+1))
for _ in range(M):
    a, b = map(int, input().split())
    g.add_edge(a, b)
p1, p2 = bipartite(g)
if p1 is None:
    print(N * (N-1) // 2 - M)
else:
    print(len(p1) * len(p2) - M)

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(100000)

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

visited = [False]*N
WH = [None]*N

def dfs(curr, is_white):
    if visited[curr]:
        return WH[curr]^is_white
    WH[curr] = is_white
    visited[curr] = True
    ans = False
    for node in edges[curr]:
        ans |= dfs(node, not is_white)
    return ans

if dfs(0, True):
    print((N*(N-1))//2 - M)
else:
    nw = sum(WH)
    print(nw*(N-nw)-sum([WH[a-1]^WH[b-1] for a, b in AB]))

Submission status: Time Limit Exceeded

Solution code:
import sys
sys.setrecursionlimit(10**6)

n, m = map(int, input().split())
adj = [[] for _ in range(n)]
parity = [-1 for _ in range(n)]
valid = True

def dfs(x):
	global valid
	p = parity[x]
	for v in adj[x]:
		if parity[v] < 0:
			parity[v] = 1^p
			dfs(v)
		elif parity[v] == p:
			valid = False
			return
	return

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

parity[0] = 0
dfs(0)
if not valid:
	print((n*(n-1)//2) - m)
else:
	o = sum(parity)
	print(o*(n-o) - m)

Submission status: Time Limit Exceeded

Solution code:
N,M=map(int,input().split())
from collections import defaultdict
branch=defaultdict(set)
for i in range(M):
    a,b=map(int,input().split())
    a-=1
    b-=1
    branch[a]|={b}
    branch[b]|={a}
dist=[-1]*N
dist[0]=0
check={0}
while len(check)>0:
    now=check.pop()
    for nex in branch[now]:
        if dist[nex]==-1:
            dist[nex]=(dist[now]+1)%2
            check|={nex}
        elif dist[nex]!=(dist[now]+1)%2:
            check=set()
            flag=True
            dist=[-1]*N
if dist[0]==-1:
    print(N*(N-1)//2-M)
else:
    odd=dist.count(1)
    even=dist.count(0)
    print(odd*even-M)

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(1000000)
N,M = map(int, input().split())
 
# 隣接リスト
l = [[] for i in range(N+1)]
for i in range(M):
    a,b = map(int, input().split())
    l[a].append(b)
    l[b].append(a)

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}

def func(v,c):
    if nodes_color[v] == c:
        return True
    if nodes_color[v] == -c:
        return False
    
    if nodes_color[v] == 0:
        nodes_color[v] = c
    for node in l[v]:
        if not func(node, -c):
            return False
    
    return True

chk = func(1,1)

if chk:
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter
import sys
sys.setrecursionlimit(1000000)

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

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}
def func(v,c):
    if nodes_color[v] == 0:
        nodes_color[v] = c
    elif nodes_color[v] == -c:
        return False
    else:
        return True
    
    for ab in ab_list:
        if v in ab:
            for a in ab:
                if a==v:
                    continue
                if not func(a, -c):
                    return False
    return True

# def bipartite_graph_check():
#     for i in range(1,N+1):
#         if nodes_color[i] == 0:
#             if not func(i,1):
# #                 print("Not Bipartite graph")
#                 return False
#     return True

if func(1,1):
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))

Submission status: Time Limit Exceeded

Solution code:
from collections import Counter

import sys
sys.setrecursionlimit(1000000)

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

nodes_color = {node:0 for node in range(1, N+1)}#set([a for ab in ab_list for a in ab])}
def func(v,c):
    if nodes_color[v] == 0:
        nodes_color[v] = c
    elif nodes_color[v] == -c:
        return False
    else:
        return True
    
    for ab in ab_list:
        if v in ab:
            for a in ab:
                if a==v:
                    continue
                if not func(a, -c):
                    return False
    return True

def bipartite_graph_check():
    for i in range(1,N+1):
        if nodes_color[i] == 0:
            if not func(i,1):
#                 print("Not Bipartite graph")
                return False
    return True

if bipartite_graph_check():
    b,w = Counter(nodes_color.values()).values()
    print(int(b*w-M))
else:
    print(int(N*(N-1)/2-M))

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

colors = [0 for i in range(N)]

def is_bipartite():
    stack = [(1, 1)]
    while stack != []:
        v, color = stack.pop()
        colors[v] = color
        for to in es[v]:
            if colors[to] == color:
                 return False
            if colors[to] == 0:
                 stack.append((to, -color))
    return True

if is_bipartite():
    b = (sum(colors) + N) // 2
    w = N-b
    print(b*w - M)
else:
    all = N*(N-1) // 2
    print(all - M)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

colors = [0 for i in range(N)]

def is_bipartite():
    stack = [(0, 1)]
    while stack != []:
        v, color = stack.pop()
        colors[v] = color
        for to in es[v]:
            if colors[to] == color:
                 return False
            if colors[to] == 0:
                 stack.append((to, -color))
    return True

if is_bipartite():
    b = (sum(colors) + N) // 2
    w = N-b
    print(b*w - M)
else:
    all = N*(N-1) // 2
    print(all - M)

Submission status: Time Limit Exceeded

Solution code:
from queue import LifoQueue
N,M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

colors = [0 for i in range(N)]

def is_bipartite():
    stack = LifoQueue()
    stack.put((0, 1))
    while not stack.empty():
        v, color = stack.get()
        colors[v] = color
        for to in es[v]:
            if colors[to] == color:
                 return False
            if colors[to] == 0:
                 stack.put((to, -color))
    return True

if is_bipartite():
    b = (sum(colors) + N) // 2
    w = N-b
    print(b*w - M)
else:
    all = N*(N-1) // 2
    print(all - M)

Submission status: Time Limit Exceeded

Solution code:
from queue import LifoQueue
N,M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

colors = [0 for i in range(N)]

def is_bipartite():
    stack = LifoQueue()
    stack.put([0, 1])
    while not stack.empty():
        v, color = stack.get()
        colors[v] = color
        for to in es[v]:
            if colors[to] == color:
                 return False
            if colors[to] == 0:
                 stack.put([to, -color])
    return True

if is_bipartite():
    b = (sum(colors) + N) // 2
    w = N-b
    print(b*w - M)
else:
    all = N*(N-1) // 2
    print(all - M)

Submission status: Time Limit Exceeded

Solution code:
from queue import LifoQueue
N,M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

colors = [0 for i in range(N)]

def is_bipartite():
    stack = LifoQueue()
    stack.put([0, 1])
    while stack:
        v, color = stack.get()
        colors[v] = color
        for to in es[v]:
            if colors[to] == color:
                 return False
            if colors[to] == 0:
                 stack.put([to, -color])
    return True

if is_bipartite():
    b = (sum(colors) + N) // 2
    w = N-b
    print(b*w - M)
else:
    all = N*(N-1) // 2
    print(all - M)

Submission status: Time Limit Exceeded

Solution code:
 
N,M = map(int, input().split())
es = [[] for i in range(N)]
for i in range(M):
    a,b = map(int, input().split())
    a,b = a-1,b-1
    es[a].append(b)
    es[b].append(a)

colors = [0 for i in range(N)]

def is_bipartite():
    stack = [(0,1)]
    while stack:
        v,color = stack.pop()
        colors[v] = color
        for to in es[v]:
            if colors[to] == color:
                 return False
            if colors[to] == 0:
                 stack.append((to, -color))
    return True

if is_bipartite():
    b = (sum(colors) + N) // 2
    w = N-b
    print(b*w - M)
else:
    all = N*(N-1) // 2
    print(all - M)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split()]
data_ls = list()
G = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a, b = [int(i)-1 for i in input().split()]
    G[a][b] = 1
    G[b][a] = 1

colors = [0 for i in range(N)]
def dfs(v, c):
    colors[v] = c
    for i in range(N):
        if G[v][i] != 1:
            continue
        elif colors[i] == c:
            return False
        elif colors[i] == 0 and not dfs(i, -c):
            return False
    return True

if dfs(0,1):
    CNT = len([i for i in colors if i == 1])
    print(CNT * (N - CNT) - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Time Limit Exceeded

Solution code:
N, M = [int(i) for i in input().split()]
data_ls = list()
G = [[0 for i in range(N)] for j in range(N)]
for i in range(M):
    a, b = [int(i)-1 for i in input().split()]
    G[a][b] = 1
    G[b][a] = 1

colors = [0 for i in range(N)]
def dfs(v, c):
    colors[v] = c
    for i in range(N):
        if G[v][i] != 1:
            continue
        elif colors[i] == c:
            return False
        elif colors[i] == 0 and not dfs(i, -c):
            return False
    return True
flg = True
for i in range(N):
    if colors[i] == 0:
        if not dfs(i, 1):
            flg = False
            break
CNT = len([i for i in colors if i == 1])
if flg:
    print(CNT * (N - CNT) - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Time Limit Exceeded

Solution code:
def i1():
 return int(input())
def i2():
 return [int(i) for i in input().split()]

[n,m]=i2()
e=[[] for i in range(n)]
for i in range(m):
 [x,y]=i2()
 e[x-1].append(y-1)
 e[y-1].append(x-1)

import sys
sys.setrecursionlimit(10**6)

d=[-1 for i in range(n)]
d[0]=0
s=0
def dfs(v):
   global s
   for i in range(len(e[v])):
      if d[e[v][i]]==-1:
         
         d[e[v][i]]=(d[v]+1)%2
         dfs(e[v][i])
      elif d[e[v][i]]!=(d[v]+1)%2:
          s=1
dfs(0)
if s==0:
  t=sum(d)
  print(t*(n-t)-m)
else:
  print(int(n*(n-1)/2-m))

Submission status: Time Limit Exceeded

Solution code:
def inpl(): return [int(i) for i in input().split()]
from collections import defaultdict

N,M = inpl()
edge = defaultdict(lambda: [])
for _ in range(M):
    a, b = inpl()
    edge[a-1].append(b-1)
    edge[b-1].append(a-1)

Qu = [0] 
ctr = 1
color = [0 for _ in range(N)]
color[0] = -1
while ctr < N:
    st = Qu.pop()
    for i in edge[st]:
        if color[st] == -color[i]:
            Qu.append(i)
            continue
        if color[i] == 0:
            color[i] = -color[st]
            Qu.append(i)
            ctr += 1
sumc = sum(color)
ans =(N**2-sumc**2)//4-M
for i in range(N):
    for j in edge[i]:
        if color[i] == color[j]:
            ans = N*(N-1)//2-M
            break
    else:
        continue
    break
print(ans)

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
#E = [sorted(list(map(int, input().split()))) for i in range(M)]
V = [[] for i in range(N+1)]
for i in range(M):
    A, B = map(int, input().split())
    V[A].append(B)
    V[B].append(A)

L = [-1]*(N+1)
L[1] = 0
al = False

from collections import deque
Open = deque()
Open.append(1)
Close = set()
while len(Open)>0:
    v = Open.pop()
    Close.add(v)
    for v2 in V[v]:
        if v2 not in Close:
            Open.append(v2)
        if L[v2] == -1:
            L[v2] = 1-L[v]
        elif L[v] + L[v2] != 1:
            al = True
            break
    if al:
        break

#print(V, L, al)
if al:
    print(N*(N-1)//2-M)
else:
    c = L.count(1)
    print(c*(N-c)-M)

Submission status: Time Limit Exceeded

Solution code:
from collections import deque
N,M=map(int,input().split())
Table=[[] for i in range(N)]
for i in range(M):
    a,b = map(int,input().split())
    Table[a-1].append(b-1)
    Table[b-1].append(a-1)
visit=[False]*N
iro=[-1]*N
kei=deque()
def nibu():
    kei.append(0)
    iro[0]=0
    while kei:
        x = kei.pop()
        visit[x]=True
        for i in Table[x]:
            if visit[i] and iro[i] == iro[x]:
                return False
            elif not visit[i]:
                kei.append(i)
                iro[i]=(iro[x]+1)%2
    return True
if nibu():
    B = iro.count(0)
    W = iro.count(1)
    ans = B*W-M
else:
    ans = (N*(N-1))//2 -M
print(ans)

Submission status: Time Limit Exceeded

Solution code:
n, m = map(int, input().split())

graph = [[0 for i in range(n)] for j in range(n)]

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

memo = [0 for i in range(n)]
color = [-1 for i in range(n)]
black = 0
white = 0
flag = 0


def search(v):
    for i in range(n):
        if graph[v][i] == 1:
            if memo[i] == 0:
                memo[i] = 1
                color[i] = (color[v]+1) % 2
                if color[i] == 0:
                    global black
                    black += 1
                else:
                    global white
                    white += 1
                search(i)
            else:
                if color[v] == color[i]:
                    global flag
                    flag = 1

memo[0] = 1
color[0] = 0
black += 1
search(0)

if flag == 1:
    print(n*(n-1)//2 - m)
else:
    print(black * white - m)

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N,M=list(map(int,raw_input().split()))

nl=[[0]*(N+1) for i in range(N+1)]
a=[0]*M
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x][y]=1
	nl[y][x]=1	
#print nl

def dfs(v,p):
	#print v,p,color
	global bip_graph
	F[v]=1

	for j in range(N+1):

		#色塗り
		if nl[v][j]!=0:
			#print v,j,color
			if color[v]=="w" and color[j]==0:
				color[j]="b"
			elif color[v]=="b" and color[j]==0:
				color[j]="w"				
			elif color[v]==color[j]:
				#二分木ではない
				bip_graph="NO"


		#頂点 v に隣接しているかつ未訪問
		if bip_graph!="NO" and nl[v][j]!=0 and F[j]==0:
			#DFS(次の頂点i, 次に親となる頂点v, d+ 頂点vと頂点iの間の辺のコスト)
			
			dfs(j,v)


bip_graph="YES"
color=[0]*(N+1)
F=[0]*(N+1)
color[1]="b"
dfs(1,-1)
#print bip_graph
#print color

if bip_graph=="YES":
	print color.count("b")*color.count("w")-M
elif bip_graph=="NO":
	print N*(N-1)/2-M

Submission status: Time Limit Exceeded

Solution code:
# -*- coding: utf-8 -*-
N,M=list(map(int,raw_input().split()))

nl=[[0]*(N+1) for i in range(N+1)]
a=[0]*M
for i in range(M):
	x,y=map(int,raw_input().split())
	nl[x][y]=1
	nl[y][x]=1	
#print nl

def dfs(v,p):
	global bip_graph
	F[v]=1

	for j in range(N+1):

		#色塗り
		if nl[v][j]!=0:
			#print v,j,color
			if color[v]=="w" and color[j]==0:
				color[j]="b"
			elif color[v]=="b" and color[j]==0:
				color[j]="w"				
			elif color[v]==color[j]:
				#二分木ではない
				bip_graph="NO"


		#頂点 v に隣接しているかつ未訪問
		if nl[v][j]!=0 and F[j]==0:
			#DFS(次の頂点i, 次に親となる頂点v, d+ 頂点vと頂点iの間の辺のコスト)
			
			dfs(j,v)


bip_graph="YES"
color=[0]*(N+1)
F=[0]*(N+1)
color[1]="b"
dfs(1,-1)
#print bip_graph
#print color

if bip_graph=="YES":
	print color.count("b")*color.count("w")-M
elif bip_graph=="NO":
	print N*(N-1)/2-M

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,raw_input().split())
es = [[] for i in range(N)]
for i in range(M):
  a,b = map(int,raw_input().split())
  a,b = a-1,b-1
  es[a].append(b)
  es[b].append(a)

colors = [0 for i in range(N)]

def is_bipartite():
  stack = [(0,1)]
  while stack:
    v,color = stack.pop()
    colors[v] = color
    for to in es[v]:
      if colors[to] == color:
        return False
      if colors[to] == 0:
        stack.append((to, -color))
  return True

if is_bipartite():
  b = (sum(colors) + N) // 2
  w = N-b
  print(b*w - M)
else:
  all = N*(N-1) // 2
  print(all - M)

Submission status: Time Limit Exceeded

Solution code:
import sys

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

i = 0
ret = 0
while i < len(E0):
    a, b = E0[i]
    print(i, a, b, file=sys.stderr)
    for p in E1[a]:
        for q in E1[b]:
            if p == q or p in E1[q]:
                continue
            ret += 1
            E0.append((p, q))
            E1[p].add(q)
            E1[q].add(p)
    i += 1

print(ret)

Submission status: Time Limit Exceeded

Solution code:
N,M = map(int,input().split())

graph = {}
for i in range(M):
    x,y = map(int,input().split())
    try:
        graph[x].add(y)
    except:
        graph[x] = {y}

    try:
        graph[y].add(x)
    except:
        graph[y] = {x}

# BFS function here
def BFS(graph,N):
    new_nodes = True
    total_new_edges = 0
    
    while new_nodes:
        new_nodes = False
        for start in range(1,N+1):
            queue = [(start,0)]
            seen = {start}

            index = 0
            
            while index < len(queue):
                current = queue[index]
                if current[1] < 3:
                    for i in graph[current[0]]:
                        if i not in seen:
                            queue.append((i,current[1]+1))
                else:
                    if current[0] not in graph[start] and start not in graph[current[0]]:
                        graph[start].add(current[0])
                        graph[current[0]].add(start)
                        new_nodes = True
                        total_new_edges += 1
                    
                seen.add(current[0])
                index += 1
    return total_new_edges

print(BFS(graph,N))

Submission status: Time Limit Exceeded

Solution code:
N, M = map(int, input().split())
DIS = [[-1] * N for _ in range(N)]
for _ in range(M):
  a, b = map(int, input().split())
  DIS[a-1][b-1]=DIS[b-1][a-1]=1

stack = []
co = 0
searched = set()

def se(li, hoge=0):
  global stack
  global DIS
  global co
  global searched
  for n in range(N):
    if n in stack[hoge:]:
      continue
    if DIS[li][n] == 1 and n not in stack[hoge:]:
      stack.append(n)
      if len(stack) == 4 + hoge and DIS[stack[hoge]][n] != 1:
        DIS[stack[hoge]][n] = 1
        DIS[n][stack[hoge]] = 1
        searched.add(stack[hoge])
        se(n, hoge + 1)
        stack.pop()
        co += 1
      else:
        se(n)
        stack.pop()

for outer in range(N):
  if outer in searched:
    continue
  stack.append(outer)
  for inner in range(N):
    stack.append(inner)
    if DIS[outer][inner] == 1:
      se(inner)
    stack.pop()
  stack.pop()

print(co)

Submission status: Time Limit Exceeded

Solution code:
inputs = input().split()

N = int(inputs[0])
M = int(inputs[1])

p = [[] for x in range(N)]

for i in range(M):
    inputs = input().split()
    s = int(inputs[0]) - 1
    g = int(inputs[1]) - 1
    if g not in p[s]:
        p[s].append(g)
    if s not in p[g]:
        p[g].append(s)

ans = 0

for i in range(N):
    for v1 in p[i]:
        if v1 == i:
            continue
        for v2 in p[v1]:
            if v2 == v1 or v2 == i:
                continue
            for v3 in p[v2]:
                if v3 == v2 or v3 == v1 or v3 == i:
                    continue
                if v3 not in p[i] and v3 != i:
                    p[i].append(v3)
                    p[v3].append(i)
                    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
inputs = input().split()

N = int(inputs[0])
M = int(inputs[1])

p = [[] for x in range(N)]

for i in range(M):
    inputs = input().split()
    s = int(inputs[0]) - 1
    g = int(inputs[1]) - 1
    if g not in p[s]:
        p[s].append(g)
    if s not in p[g]:
        p[g].append(s)

ans = 0

for i in range(N):
    for v1 in p[i]:
        for v2 in p[v1]:
            if v2 == v1 or v2 == i:
                continue
            for v3 in p[v2]:
                if v3 == v2 or v3 == v1 or v3 == i:
                    continue
                if v3 not in p[i] and v3 != i:
                    p[i].append(v3)
                    p[v3].append(i)
                    ans += 1

print(ans)

Submission status: Time Limit Exceeded

Solution code:
inputs = input().split()

N = int(inputs[0])
M = int(inputs[1])

p = [[] for x in range(N)]

for i in range(M):
    inputs = input().split()
    s = int(inputs[0]) - 1
    g = int(inputs[1]) - 1
    if g not in p[s]:
        p[s].append(g)
    if s not in p[g]:
        p[g].append(s)

ans = 0

for i in range(N):
    for v1 in p[i]:
        for v2 in p[v1]:
            if v2 == v1:
                continue
            for v3 in p[v2]:
                if v3 == v2:
                    continue
                if v3 not in p[i] and v3 != i:
                    p[i].append(v3)
                    p[v3].append(i)
                    ans += 1

print(ans)

Submission status: Time Limit Exceeded

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

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

WHITE = 0
BLACK = WHITE + 1
color = [[WHITE for _ in range(N)] for _ in range(N)]

add_e = 0
def searchV(tmp_u, depth):
    global color, u, add_e
    if depth==3:
        if color[u][tmp_u] == WHITE and C[u][tmp_u] == 0 and tmp_u!=u:
            C[u][tmp_u] = 1
            C[tmp_u][u] = 1
            add_e += 1
            color[u][tmp_u] = BLACK
            color[tmp_u][u] = BLACK
            return
        else:
            return

    for tmp_v in range(N):
        if C[tmp_u][tmp_v]==1 and tmp_u!=tmp_v:
            searchV(tmp_v, depth+1)
        else:
            continue

for u in range(N):
    searchV(u, 0)

print(add_e)

Submission status: Time Limit Exceeded

Solution code:
n, m = tuple(int(i) for i in input().split())
a_b = [input() for i in range(m)]
al = {}
for i in a_b:
    a, b = map(int, i.split())

    if a in al:
        al[a].append(b)
    else:
        al[a] = [b]

    if b in al:
        al[b].append(a)
    else:
        al[b] = [a]

ans = 0
for k, v in al.items():
    s = []
    s.append(k)
    for i in al[s[-1]]:
        s.append(i)
        for j in al[s[-1]]:
            s.append(j)
            for k in al[s[-1]]:
                s.append(k)

                if s[0] not in al[s[-1]] and s[0] != s[-1]:
                    ans += 1
                    al[s[0]].append(s[-1])
                    al[s[-1]].append(s[0])

print(ans)