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: Accepted

Solution code:
from collections import deque

n, m = map(int, input().split())

e = [set() for _ in range(n)]
for _ in range(m):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    e[a].add(b)
    e[b].add(a)

dq = deque()
dq.append(0)

p = [None] * n
p[0] = 0

is_bipartite = True
while dq:
    v = dq.popleft()
    for u in e[v]:
        if p[u] is None:
            p[u] = 1 ^ p[v]
            dq.append(u)
        elif p[u] == p[v]:
            is_bipartite = False
            break
        else:
            # p[u] == p[v] ^ 1
            pass

if is_bipartite:
    # 同じ色の頂点には辺を張らない
    sp = sum(p)
    print(sp * (n - sp) - m)
else:
    # 全ての頂点間に辺を張る
    print(n * (n - 1) // 2 - m)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

AB = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

# 二部グラフかどうかを判定する
color = [None] * (N+1)
color[1] = 0
q = [1]
while q:
    x = q.pop()
    for y in graph[x]:
        if color[y] is None:
            color[y] = 1 - color[x]
            q.append(y)

bl = all(color[a] != color[b] for a,b in AB)

if bl:
    # 完全二部グラフにする
    x = sum(color[1:])
    y = N - x
    answer = x*y - M
else:
    # 完全グラフにする
    answer = N*(N-1)//2 - M

print(answer)

Submission status: Accepted

Solution code:
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10 ** 7)

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

AB = [[int(x) for x in input().split()] for _ in range(M)]

graph = [[] for _ in range(N+1)]
for a,b in AB:
    graph[a].append(b)
    graph[b].append(a)

# 二部グラフかどうかを判定する
color = [None] * (N+1)
color[1] = 0
q = [1]
while q:
    x = q.pop()
    for y in graph[x]:
        if color[y] is None:
            color[y] = 1 - color[x]
            q.append(y)

bl = all(color[a] != color[b] for a,b in AB)

if bl:
    # 完全二部グラフにする
    x = sum(color[1:])
    y = N - x
    answer = x*y - M
else:
    # 完全グラフにする
    answer = N*(N-1)//2 - M

print(answer)

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

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


def dfs(v, todo, color):
    if seen[v] == color:  # 同じ色で戻ってくる = 偶サイクル
        return
    elif seen[v] == 1-color:  # 異なる色で戻ってくる = 奇サイクル
        ans = 0.5 * n * (n-1) - m
        print(int(ans))
        sys.exit()

    seen[v] = color
    for new_v in todo:
        new_todo = dic[new_v]
        dfs(new_v, new_todo, 1-color)


dfs(1, dic[1], 0)
black = seen.count(0)
white = seen.count(1)
ans = black * white - m

print(int(ans))

Submission status: Accepted

Solution code:
from collections import defaultdict
import sys
input = sys.stdin.readline
sys.setrecursionlimit(10**7)

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

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


def dfs(v, todo, color):
    if seen[v] == color:  # 同じ色で戻ってくる = 偶サイクル
        return
    elif seen[v] == 1-color:  # 異なる色で戻ってくる = 奇サイクル
        global odd_cycle
        odd_cycle = True
        return

    seen[v] = color
    for new_v in todo:
        new_todo = dic[new_v]
        dfs(new_v, new_todo, 1-color)


odd_cycle = False
dfs(1, dic[1], 0)
if odd_cycle:
    ans = 0.5 * n * (n-1) - m
else:
    black = seen.count(0)
    white = seen.count(1)
    ans = black * white - m

print(int(ans))

Submission status: Accepted

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

E = [[] for _ in [0]*N]
for u,v in AB:
    E[u-1].append(v-1)
    E[v-1].append(u-1)

def dist_bfs(N,E,start):
    d = [-1]*N
    d[start] = 0
    q = [start]
    while q:
        qq = []
        for i in q:
            di = d[i]
            for j in E[i]:
                if d[j]!=-1:continue
                d[j] = di+1
                q.append(j)
        q = qq
    return d

d = dist_bfs(N,E,0)

co = sum(c%2 for c in d)
ce = N - co
check = False
for a,b in AB:
    a-=1
    b-=1
    if (d[a]+d[b])%2==0:
        check = True
        break
if check:
    ans = N*(N-1)//2 - M
else:
    ans = co*ce - M
print(ans)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
A, B = (
    zip(*(map(int, input().split()) for _ in range(M))) if M else
    ((), ())
)

# グラフが二部グラフならば二集合間に辺を張れる
# そうでなければ完全グラフになるように辺を張れる
G = [set() for _ in range(N + 1)]
for x, y in zip(A, B):
    G[x].add(y)
    G[y].add(x)
dp = [0 for _ in range(N + 1)]
q = []
q.append(1)
dp[1] = 1
is_bi = True
while q:
    i = q.pop()
    for j in G[i]:
        if dp[j] == 0:
            dp[j] = -dp[i]
            q.append(j)
        else:
            is_bi &= dp[j] == -dp[i]
ans = (
    sum(x == 1 for x in dp) * sum(x == -1 for x in dp) - M if is_bi else
    N * (N - 1) // 2 - M
)

print(ans)

Submission status: Accepted

Solution code:
class UnionFindTree():
    def __init__(self, N):
        self.__parent_of = [None] * N
        self.__rank_of = [0] * N
        self.__size = [1] * N

    def root(self, value):
        if self.__parent_of[value] is None:
            return value
        else:
            self.__parent_of[value] = self.root(self.__parent_of[value])
            return self.__parent_of[value]

    def unite(self, a, b):
        r1 = self.root(a)
        r2 = self.root(b)
        if r1 != r2:
            if self.__rank_of[r1] < self.__rank_of[r2]:
                self.__parent_of[r1] = r2
                self.__size[r2] += self.__size[r1]
            else:
                self.__parent_of[r2] = r1
                self.__size[r1] += self.__size[r2]
                if self.__rank_of[r1] == self.__rank_of[r2]:
                    self.__rank_of[r1] += 1

    def is_same(self, a, b):
        return self.root(a) == self.root(b)

    def size(self, a):
        return self.__size[self.root(a)]

    def groups(self):
        groups = {}
        for k in range(len(self.__parent_of)):
            r = self.root(k)
            if r not in groups:
                groups[r] = []
            groups[r].append(k)
        return [groups[x] for x in groups]


def main():
    N, M = map(int, input().split())
    adj = [set() for _ in range(N)]
    for _ in range(M):
        A, B = map(int, input().split())
        adj[A-1].add(B-1)
        adj[B-1].add(A-1)
    uft = UnionFindTree(N)
    for i in range(N):
        adji = list(adj[i])
        x = adji[0]
        for y in adji[1:]:
            uft.unite(x, y)
    groups = uft.groups()
    if len(groups) == 1:
        print(N * (N-1) // 2 - M)
    else:
        print(len(groups[0]) * len(groups[1]) - M)


if __name__ == "__main__":
    main()

Submission status: Accepted

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

graph = [[] for _ in range(N)]
for x, y in edges:
    graph[x - 1].append(y - 1)
    graph[y - 1].append(x - 1)

def dfs(s, c):
    q = deque()
    q.append(s)
    visited[s] = True
    color[s] = c
    
    while len(q) > 0:
        v = q.pop()
        for i in graph[v]:
            if visited[i] and color[i] == color[v]:
                return False
            
            if not visited[i]:
                visited[i] = True
                color[i] = -color[v]
                q.append(i)
                
    return True

visited = [False] * N
color = [0] * N

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

Submission status: Accepted

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

graph = [[] for _ in range(N)]
for x, y in edges:
    graph[x - 1].append(y - 1)
    graph[y - 1].append(x - 1)

def dfs(v, c):
    # c: color = 1 or -1
    node[v] = c
    for i in graph[v]:
        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 for v in node) // 2
    print(x * (N - x) - M)
else:
    print(N * (N - 1) // 2 - M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
from operator import mul
from functools import reduce

def comb(n,r):
    r = min(n-r,r)
    if r == 0: return 1
    over = reduce(mul, range(n, n - r, -1))
    under = reduce(mul, range(1,r + 1))
    return over // under


def dfs(v, cur):
    color[v] = cur
    
    for next_v in Graph[v]:
        if color[next_v] != -1:
            if color[next_v] != cur:
                continue
            else:
                return False
        elif not dfs(next_v, 1-cur):
            return False
    return True
        


N, M = map(int, input().split())
AB = [[int(_) for _ in input().split()] for _ in range(M)]
Graph = [[] for _ in range(N)]
color = [-1]*N

for i in AB:
    Graph[i[0]-1].append(i[1]-1)
    Graph[i[1]-1].append(i[0]-1)

if dfs(0, 0):
    black = color.count(0)
    white = N - black
    print(black*white-M)
else:
    print(comb(N, 2)-M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10 ** 6)
input = sys.stdin.readline
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)

col = [-1] * N


def dfs(u, p, k):
    if col[u] != -1:
        if col[u] == k:
            return
        else:
            print(N * (N - 1) // 2 - M)
            exit()
    col[u] = k
    for w in G[u]:
        if w == p:
            continue
        dfs(w, u, k ^ 1)


dfs(0, -1, 0)
n, m = 0, 0
for i in range(N):
    if col[i] == 1:
        n += 1
    else:
        m += 1

print(n * m - M)

Submission status: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = float("inf")
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

N,M = map(int,input().split())
G = defaultdict(set)
for i in range(M):
    a,b = map(int,input().split())
    G[a-1].add(b-1)
    G[b-1].add(a-1)
color = [0 for i in range(len(G))]
color[0]=1
#二部グラフであるかの判定
def Isbipartite(G):
    """
    color = [[0] for i in range(len(G))]
    color[0]=1
    """
    que=deque([0])
    bipartite = True
    while que:
        p = que.popleft()
        for q in list(G[p]):
            if color[q]==0:
                color[q] = -color[p]
                que.append(q)
            elif color[q] == color[p]:
                bipartite = False
                break
    return bipartite


if Isbipartite(G):
    print(color.count(1)*color.count(-1)-M)
else:
    print(N*(N-1)//2-M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**6)
n,m=map(int,input().split())
s=[[]for i in range(n+1)]
c=[0]*(n+1)
for i in range(m):
    a,b=map(int,input().split())
    s[a].append(b)
    s[b].append(a)
def dfs(v,t):
    c[v]=t
    for i in s[v]:
        if c[i]==t:
            return False
        if c[i]==0 and not dfs(i,-t):
            return False
    else:
        return True
if dfs(1,1):
    q=c.count(1)
    print((n-q)*q-m)
else:
    print((n*(n-1)//2)-m)

Submission status: Accepted

Solution code:
def bipartite():
    color = {v: None for v in V}
    stack = [(V[0], 0)]
    parts = {0: [], 1:[]}
    while stack:
        v, c = stack.pop()
        if color[v] is not None: # consistent
            continue
        color[v] = c
        parts[c].append(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: Accepted

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)

colors = [None]*N
def dfs(curr, c):
    colors[curr] = c
    for node in edges[curr]:
        if colors[node] == colors[curr]:
            return False
        if colors[node] is None and not dfs(node, not c):
            return False
    return True

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

Submission status: Accepted

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)

colors = [0]*N
def dfs(curr, c):
    colors[curr] = c
    for node in edges[curr]:
        if colors[node] == colors[curr]:
            return False
        if colors[node]== 0 and not dfs(node, -c):
            return False
    return True

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

Submission status: Accepted

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((n*(n-1)//2) - m - (o*(o-1)//2) - ((n-o)*(n-o-1)//2))

Submission status: Accepted

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}
flag=False
while len(check)>0:
    if flag:
        break
    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
            break
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: Accepted

Solution code:
from itertools import*
from math import*
from collections import*
from heapq import*
from bisect import bisect_left,bisect_right
from copy import deepcopy
inf = 10**18
mod = 10**9+7
from functools import reduce
import sys
sys.setrecursionlimit(10**7)

#s,t間に奇数長のパスが存在したならば必ずs,t間には辺が張られる
#グラフが二部グラフでないならば奇数長のサイクルが存在して任意の(s,t)間に奇数長パスが作れる
#グラフが二部グラフであるならば異なるカラーグループ間の頂点には必ず辺が張られる
n,m = map(int,input().split())
G = defaultdict(set)
color = [0 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    G[a-1].add(b-1)
    G[b-1].add(a-1)
#二部グラフ判定
color[0]=1
que = deque([0])
bipartite = True
while len(que):
    p = que.popleft()
    for q in list(G[p]):
        if color[q] == 0:
            color[q] = -color[p]
            que.append(q)
        elif color[q] == color[p]:
            bipartite = False
            break
if bipartite:
    print(color.count(1)*color.count(-1)-m)
else:
    print(n*(n-1)//2-m)

Submission status: Accepted

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 = list(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])}

nibu = True
stack = [1]

nodes_color[1] = 1

while stack:
    node = stack.pop()
    for next_node in l[node]:
        if nodes_color[next_node]==0:
            stack.append(next_node)
            nodes_color[next_node] = - nodes_color[node]
        else:
            if nodes_color[next_node]==nodes_color[node]:
                nibu = False
                break
    if not nibu:
        break

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

Submission status: Accepted

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

# 隣接リスト
l = [[] for i in range(n)]
for i in range(m):
    a,b = map(int, input().split())
    a-=1
    b-=1
    l[a].append(b)
    l[b].append(a)

# 二部グラフ判定
nibu = True
stack = [0]
col = [-1 for i in range(n)]
col[0]=0
while stack:
    p = stack.pop()
    for x in l[p]:
        if col[x]==-1:
            stack.append(x)
            if col[p]==0:
                col[x]=1
            else:
                col[x]=0
        else:
            if col[x]==col[p]:
                nibu = False
                break
    if not nibu:
        break

if nibu:
    print(col.count(1)*col.count(0)-m)
else:
    print(n*(n-1)//2-m)

Submission status: Accepted

Solution code:
from collections import deque

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)
color=[0]*N
color[0]=1
que=deque()
que.append(0)
nibu=True
bla=1
whi=0
while(que):
    x=que.pop()
    for i in G[x]:
        if color[i]==color[x]:
            nibu=False
            break
        if color[i]==-color[x]:
            continue
        if color[i]==0:
            color[i]=-color[x]
            if color[i]==1:
                bla+=1
            else:
                whi+=1
            que.append(i)
            continue

if not nibu:
    print(N*(N-1)//2-M)
if nibu:
    print(bla*whi-M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(10**7)
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)
color=[-1]*N  
def dfs(x):
  for i in G[x]:
    if color[i]==-1:
      color[i]=1^color[x]
      dfs(i)
    elif color[i]==color[x]:
      print((N*(N-1))//2-M)
      exit()
color[0]=0
dfs(0)
b=0
for i in range(N):
  b+=color[i]
print(b*(N-b)-M)

Submission status: Accepted

Solution code:
from collections import deque
N, M = map(int, input().split())
G = [[] for i in range(N)]
for m in range(M):
    a, b = map(int, input().split())
    a -= 1
    b -= 1
    G[a].append(b)
    G[b].append(a)

color = [-1 for i in range(N)]
visits = [False for i in range(N)]
paths = deque()


def Bipartial():
    paths.append(0)
    color[0] = 0
    while paths:
        x = paths.pop()
        visits[x] = True
        for g in G[x]:
            if visits[g] and color[g] == color[x]:
                return False
            elif not visits[g]:
                paths.append(g)
                color[g] = (color[x]+1) % 2
    return True


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

Submission status: Accepted

Solution code:
import sys
input=sys.stdin.readline
sys.setrecursionlimit(10**9)
n,m=map(int,input().split())
Edges=[[] for _ in range(n)]
for _ in range(m):
    a,b=map(int,input().split())
    a-=1; b-=1
    Edges[a].append(b)
    Edges[b].append(a)
Colors=[0]*n

def dfs(v,color):
    Colors[v]=color
    for to in Edges[v]:
        if Colors[to]==color:
            return False
        if Colors[to]==0 and not dfs(to,-color):
            return False
    return True

def isbipartite():
    return dfs(0,1)

if isbipartite():
    black=(sum(Colors)+n)//2
    white=n-black
    print(black*white-m)
else:
    print(n*(n-1)//2-m)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
F = sys.stdin
N, M = map(int, F.readline().strip("\n").split())
Edge = [[] for _ in range(N)]
for _ in range(M):
    A, B = map(int, F.readline().strip("\n").split())
    Edge[A-1].append(B-1)
    Edge[B-1].append(A-1)

Color = [0] * N


def dfs(v, c):
    Color[v] = c
    for next in Edge[v]:
        if Color[next] == c: return False
        if Color[next] == 0:
            if not dfs(next, -c): return False
    return True

Bipartite = dfs(0, 1)
if Bipartite:
    black = Color.count(1)
    print(black * (N-black) - M)
else:
    print(N * (N - 1)//2 - M)

Submission status: Accepted

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

import sys
from collections import Counter

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 ceil(x, y=1): return int(-(-x // y))
def INT(): return int(input())
def MAP(): return map(int, input().split())
def LIST(): return list(map(int, input().split()))
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=[[] for i in range(N)]
for i in range(M):
    a,b=MAP()
    nodes[a-1].append(b-1)
    nodes[b-1].append(a-1)

visited=[False]*N
team=['']*N

def rec(u):
    if visited[u]:
        return True
    visited[u]=True
    for v in nodes[u]:
        if team[u]==team[v]:
            return False
        if team[u]=='a':
            team[v]='b'
        elif team[u]=='b':
            team[v]='a'
        if not rec(v):
            return False
    return True

# 1からnまでの等差数列の和
def get_sum(n):
    return (1+n)*n//2

team[0]='a'
if rec(0):
    C=Counter(team)
    ans=C['a']*C['b']-M
else:
    ans=get_sum(N-1)-M
print(ans)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000000)

n,m =  map(int,input().split())

visited = [-1 for i in range(n)]

edge = [[]for i in range(n)]

flag = True


def dfs(p,color):
    global flag
    if visited[p] == -1:
        visited[p] = color
        for next in edge[p]:
            dfs(next,color^1)
    elif visited[p] != color:
        flag = False




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

dfs(0,0)


if(flag):
    cnt = 0
    for i in range(n):
        if(visited[i] == 1): cnt += 1
    print(cnt*(n-cnt)-m)

else:
    print(n*(n-1)//2 - m)

Submission status: Accepted

Solution code:
# 忘れないように
import sys
sys.setrecursionlimit(10**9)
N, M = map(int, input().split())
G = [[] for i in range(N)]
for i in range(M):
    a, b = map(int, input().split())
    a, b = a - 1, b - 1
    G[a].append(b)
    G[b].append(a)


# 0は未着色を表す
color = [0] * N


# 二部グラフ判定dfs
def dfs(v, c):
    color[v] = c
    for to in G[v]:
        if color[to] == c:
            return False

        if color[to] == 0 and not dfs(to, -c):
            return False

    return True


Bipartite = dfs(0, 1)

if Bipartite:
    White = color.count(1)
    Black = color.count(-1)
    print(White * Black - M)

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

Submission status: Accepted

Solution code:
# coding: utf-8
import sys
sys.setrecursionlimit(1000000)
n,m=map(int,input().split())
g=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a,b=a-1,b-1
    g[a].append(b)
    g[b].append(a)
color=[0 for i in range(n)]
def check(v,c):
    color[v]=c
    for i in range(len(g[v])):
        if color[g[v][i]]==c:
            return False
        if color[g[v][i]]==0 and not check(g[v][i],-c):
            return False
    return True

for i in range(n):
    if color[i]==0:
        if not check(i,1):
            print(int((n-1)/2*n)-m)
            break
else:
    x,y=0,0
    for i in range(n):
        if color[i]==1:
            x+=1
        else:
            y+=1
    print(x*y-m)
    exit()

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(200000)
input = sys.stdin.readline
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)
kyo = [-1]*n
def dfs(x,y,z):
        for i in g[x]:
                if i == y: continue
                if kyo[i] == -1:
                        kyo[i] = (z+1)%2
                        dfs(i,x,z+1)
                else:
                        if kyo[i] !=  (z+1)%2:
                                print(n*(n-1)//2-m)
                                exit()
                
kyo[0] = 0
dfs(0,0,0)
ki = 0
gu = 0
for i in kyo:
        if i %2 == 0:
                gu += 1
        else:
                ki += 1
print(gu*ki-m)

Submission status: Accepted

Solution code:
N,M=map(int,input().split())
G=[set() for i in range(N)]
a=[0 for i in range(M)]
b=[0 for i in range(M)]
for i in range(M):
    a[i],b[i]=map(int,input().split())
    a[i]-=1;b[i]-=1
    G[a[i]].add(b[i])
    G[b[i]].add(a[i])
q=[0]
reached=[0 for i in range(N)];reached[0]=1
color=[0 for i in range(N)];color[0]=1
while(len(q)>0):
    r=q.pop()
    for p in G[r]:
        if reached[p]==1:
            continue
        reached[p]=1
        color[p]=-color[r]
        q.append(p)
flag=1
for i in range(M):
    if color[a[i]]+color[b[i]]!=0:
        flag=0
        break
if flag==1:
    X=0
    Y=0
    for i in range(N):
        if color[i]==1:
            X+=1
        else:
            Y+=1
    print(X*Y-M)
else:
    print(-M+(N*(N-1))//2)

Submission status: Accepted

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]:
            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: Accepted

Solution code:
# time complexity: O(N + M)
# space complexity: O(N)

import sys
sys.setrecursionlimit(100000)
fin = sys.stdin.readline

N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(elem) - 1 for elem in fin().split()]
    adj[a].append(b)
    adj[b].append(a)


def judge_bipartite(adj, v, color, colors):
    colors[v] = color
    for neighbor in adj[v]:
        if colors[neighbor] is None:
            if not judge_bipartite(adj, neighbor, 1 - color, colors):
                return False
        else:
            if colors[neighbor] == color:
                return False
    else:
        return True

colors = [None] * N
bipartite = judge_bipartite(adj, 0, 0, colors)

if not bipartite:
    print(N * (N - 1) // 2 - M)
else:
    num_b = sum([v == 0 for v in colors])
    num_w = N - num_b
    print(num_b * num_w - M)

Submission status: Accepted

Solution code:
import sys
sys.setrecursionlimit(100000)
fin = sys.stdin.readline

N, M = [int(elem) for elem in fin().split()]
adj = [[] for _ in range(N)]
for _ in range(M):
    a, b = [int(elem) - 1 for elem in fin().split()]
    adj[a].append(b)
    adj[b].append(a)


def judge_bipartite(adj, v, color, colors):
    colors[v] = color
    for neighbor in adj[v]:
        if colors[neighbor] is None:
            if not judge_bipartite(adj, neighbor, 1 - color, colors):
                return False
        else:
            if colors[neighbor] == color:
                return False
    else:
        return True

colors = [None] * N
bipartite = judge_bipartite(adj, 0, 0, colors)

if not bipartite:
    print(N * (N - 1) // 2 - M)
else:
    num_b = sum([v == 0 for v in colors])
    num_w = N - num_b
    print(num_b * num_w - M)

Submission status: Accepted

Solution code:
N, M = map(int, input().split())
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

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

Submission status: Accepted

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

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

# 0は未着色を表す
color = [0] * N


# 二部グラフ判定dfs
def dfs(v, c):
    color[v] = c
    for to in G[v]:
        if color[to] == c:
            return False

        if color[to] == 0 and not dfs(to, -c):
            return False

    return True


print(N * (N - 1) // 2 - M if not dfs(0, 1) else color.count(1) * color.count(-1) - M)