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: Runtime Error

Solution code:
n,m=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
depth=[-1 for i in range(n)]
def check(i,h):
    depth[i]=h
    for j in edge[i]:
        if depth[j]==-1:
            check(j,(h+1)%2)
        elif depth[j]==depth[i]:
            return False
    return True
if check(0,0):
    blk=0
    whi=0
    for i in range(n):
        if depth[i]==0:
            blk+=1
        else:
            whi+=1
    print(b*w-m)
else:
    print(n*(n-1)//2-m)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
depth=[-1 for i in range(n)]
def check(i,h):
    depth[i]=h
    for j in edge[i]:
        if depth[j]==-1:
            check(j,h+1)
        elif depth[j]%2==depth[i]%2:
            return False
    return True
if check(0,0):
    blk=0
    whi=0
    for i in range(n):
        if depth[i]%2==0:
            blk+=1
        else:
            whi+=1
    ret=0
    for i in range(n):
        if depth[i]%2==0:
            ret+=whi-len(edge[i])
        else:
            ret+=blk-len(edge[i])
    print(ret//2)
else:
    print(n*(n-1)//2-m)

Submission status: Runtime Error

Solution code:
n,m=map(int,input().split())
edge=[[] for i in range(n)]
for i in range(m):
    a,b=map(int,input().split())
    a-=1
    b-=1
    edge[a].append(b)
    edge[b].append(a)
depth=[-1 for i in range(n)]
def check(i,h):
    depth[i]=h
    for j in edge[i]:
        if depth[j]==-1:
            check(j,h+1)
        elif depth[j]%2==depth[i]%2:
            return False
    return True
if check(0,0):
    blk=0
    whi=0
    for i in range(n):
        if depth[i]%2==0:
            blk+=1
        else:
            whi+=1
    ret=0
    for i in range(n):
        if depth[i]%2==0:
            ret+=blk-len(edge[i])
        else:
            ret+=whi-len(edge[i])
    print(ret//2)
else:
    print(n*(n-1)//2-m)

Submission status: Runtime Error

Solution code:
from collections import Counter
from collections import defaultdict 

N,M = map(int,input().split())
dict = defaultdict(set)

for i in range(M):
    a,b = list(map(int,input().split()))  
    
    dict[a].add(b)
    dict[b].add(a)



color = [0 for i in range(N+1)]
res = True

def dfs(v,c,queue=[]):
    u'''
    v : 現在のグラフの頂点
    c : 現在参照するフラグ,1=>-1=>1と使うので渡す必要がある
    queue : 探索したグラフの頂点を入れていく
    res : global変数を使いたくないが,再帰のreturnがよくわからないのでとりあえず
    '''

    global color
    global res 
    queue.append(v)
    
    for i in list(dict[v]):
        if color[i] == c:#隣の頂点が同じ値を与えられている際Falseを返す
            res = False
        elif i not in queue:#探索済みでなければ再帰する

            color[i] = c*-1#0ならcとは異なる値を格納
            dfs(i,-c,queue)#引数に-cとすることで,cが1=>-1=>1を繰り返す


color[1] = 1#始点色分けする
dfs(1,1)

if res:
    counter = Counter(color)
    B = counter[1]
    W = counter[-1]
    print(B*W-M)

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

Submission status: Runtime Error

Solution code:
from collections import deque


def dfs(v, c):
    flgs[v] = c
    for i in range(len(G[v])):
        if flgs[G[v][i]] == c:
            return False
        if flgs[G[v][i]] == 0 and not dfs(G[v][i], -c):
            return False

    return True


if __name__ == '__main__':
    N, M = map(int, input().split())
    G = [[] for _ in range(N + 1)]
    for i in range(M):
        a, b = map(int, input().split())
        G[a].append(b)
        G[b].append(a)

    # 二部グラフ判定をする
    bi_flg = True
    flgs = [0 for _ in range(N + 1)]
    for i in range(1, N + 1):
        if flgs[i] == 0:
            if not dfs(i, 1):
                bi_flg = False

    if bi_flg:
        # 二部グラフならBW-M
        print(flgs.count(1) * flgs.count(-1) - M)
    else:
        # 二部グラフでないなら全辺-M
        print((N * (N - 1) // 2) - M)

Submission status: Runtime Error

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 dfs(v,color):
  colors[v] = color
  for to in es[v]:
    if colors[to] == color:
      return False
    if colors[to] == 0 and not dfs(to, -color):
      return False
  return True

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

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: Runtime Error

Solution code:
#!/usr/bin/env python3

import sys


# 再帰深度の制限
REC_LIMIT = 10000

# 頂点の色
UNDEF = 0
WHITE = 1
BLACK = -WHITE


# 所与のグラフが二部グラフならば，(True, color[])を返す
# さもなければ，(False, None)を返す
# 参考：『プログラミングコンテストチャレンジブック』（第2版）p.94
def is_bipartite_graph(adj_list):
    n = len(adj_list)  # 頂点数
    color = [UNDEF] * n

    # 頂点をWHITEとBLACKで塗っていく
    def dfs(v, c):
        color[v] = c
        for u in adj_list[v]:
            if color[u] == c:
                # 隣接頂点が同色で塗られていたら不可
                return False
            if color[u] == UNDEF and not dfs(u, -c):
                # 隣接頂点が未彩色なら，反対の色で塗れるか
                return False
        return True  # すべて色を塗れた
    for i in range(n):
        if color[i] == 0:
            # 未彩色なら，WHITEで塗ってみる
            if not dfs(i, WHITE):
                return (False, None)
    return (True, color)


def compute_max_additional_edges(n, m, adj_list):
    is_bi, color = is_bipartite_graph(adj_list)
    if not is_bi:
        # 二部グラフではない場合
        return n * (n - 1) // 2 - m
    else:
        # 二部グラフである場合
        w = sum(c == WHITE for c in color)
        b = sum(c == BLACK for c in color)
        return w * b - m


def main():
    # 最大再帰深度の再設定
    sys.setrecursionlimit(REC_LIMIT)
    # 入力の読み込み
    n, m = (int(x) for x in input().split())
    adj_list = [set() for _ in range(n)]
    for _ in range(m):
        a, b = (int(x) - 1 for x in input().split())
        adj_list[a].add(b)
        adj_list[b].add(a)
    res = compute_max_additional_edges(n, m, adj_list)
    print(res)


if __name__ == '__main__':
    main()

Submission status: Runtime Error

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:
    raise
    odds,evens = res
    ans =0
    print( len(odds)*(len(evens)) -M
           )

    """
    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: Runtime Error

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
if N>7:
  print((N*(N-1))//2-M)#奇数要素の閉路があった場合は全ての頂点を結べる. 
else:
  a=0/0

Submission status: Runtime Error

Solution code:
n, m = map(int, input().split())
sus = [[] for i in range(n)]
eq = [1 for i in range(n)]
for i in range(m):
    a, b = map(int, input().split())
    sus[a - 1].append(b - 1)
    sus[b - 1].append(a - 1)

valid = [True for i in range(n)]

def dfs(x):
    ret = 1
    valid[x] = False
    for y in sus[x]:
        if valid[y]:
            valid[y] = False
            ret += dfs(y)
    return ret

color = [-1 for i in range(n)]
sol = 0
cnt = [0, 0]

def boji(x):
    global cnt
    cnt[color[x]] += 1
    for y in sus[x]:
        if color[y] == -1:
            color[y] = 1 - color[x]
            if boji(y):
                return True
        elif color[y] == color[x]:
            return True
    return 0

for i in range(n):
    if color[i] == -1 and valid[i]:
        cnt = [0, 0]
        color[i] = 0
        if boji(i) == 0:
            sol += cnt[0] * cnt[1]
        else:
            d = dfs(i)
            sol += d * (d - 1) // 2
print(sol - m)

Submission status: Runtime Error

Solution code:
#include <algorithm>
#include <bitset>
#include <cassert>
#include <cmath>
#include <complex>
#include <cstdint>
#include <cstdio>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using i64 = int64_t;

const int INF = 1 << 29;

int N, M; 

vector<int> graph[101010];

set<pair<int, int>> edges;

int main() {
    cin >> N >> M;
    for (int j = 0; j < M; ++j) {
        int a, b;
        cin >> a >> b;
        --a; --b;
        graph[a].push_back(b);
        graph[b].push_back(a);

        if (a > b) swap(a, b);
        edges.emplace(a, b);
    }

    int dist[101010];
    fill(dist, dist+N, INF);
    dist[0] = 0;

    queue<pair<int, int>> q;
    q.emplace(0, 0);
    int v, d;
    while (!q.empty()) {
        tie(v, d) = q.front();
        q.pop();

        for (const int w : graph[v]) {
            if (dist[w] == INF) {
                dist[w] = d+1;
                q.emplace(w, d+1);
            }
        }
    }

    bool f = false;
    for (pair<int, int> e: edges) {
        if (dist[e.first] == dist[e.second]) {
            f = true;
            break;
        }
    }

    if (f) {
        assert(false);
        cout << (N*(N-1)/2-M) << endl;
        return 0;
    }

    int re[101010], ss[101010];
    fill(re, re+101010, 0);
    for (int j = 0; j < N; ++j) {
        ++re[dist[j]];
    }

    for (int j = N; j >= 0; --j) {
        ss[j] = re[j] + ss[j+2];
    }

    i64 ans = -M;
    for (int j = 0; j < N; ++j) {
        ans += re[j] * (re[j+1] + ss[j+3]);
    }
    cout << ans << endl;


    return 0;
}

Submission status: Runtime Error

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[0]=True
    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)
raise
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: Runtime Error

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)
raise
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: Runtime Error

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)
    raise
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: Runtime Error

Solution code:
import networkx as nx

print("a")