WS – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

const
  fi = '';
var
  a : array[1..50000] of longint;
  val,valmax,rem : array[1..200000] of longint;
  n,k,m : longint;
 
 
procedure enter;
  var
    i,j,tmp : longint;
  begin
    n := 0;
    readln(k,m);
    i := 1;
    for j := 1 to k do
      begin
        read(tmp);
        a[i] := 1;
        inc(i,tmp);
        inc(n,tmp);
      end;
    readln;
  end;
 
procedure init(s,l,r : longint);
  var
    mid : longint;
  begin
    if l = r then
      begin
        valmax[s] := 1;
        exit;
      end;
    mid := (l + r) div 2;
    init(2*s,l,mid);
    init(2*s+1,mid+1,r);
    valmax[s] := valmax[2*s] + valmax[2*s+1];
  end;
 
procedure init2(s,l,r : longint);
  var
    mid : longint;
  begin
    if l = r then
      begin
        inc(val[s],a[l]);
        exit;
      end;
    mid := (l + r) div 2;
    init2(2*s,l,mid);
    init2(2*s+1,mid+1,r);
    val[s] := val[2*s] + val[2*s+1];
  end;
 
procedure trans(s,l,r : longint);
  var
    mid : longint;
  begin
    if (s = 0) or (l = r) then exit;
    mid := (l + r) div 2;
    inc(val[2*s],rem[s]*(mid-l+1));
    inc(val[2*s+1],rem[s]*(r-mid));
    inc(rem[2*s],rem[s]);
    inc(rem[2*s+1],rem[s]);
    rem[s] := 0;
  end;
 
procedure Jupdate(s,l,r,u,v : longint);
  var
    mid : longint;
  begin
    if (r < u) or (v < l) then exit;
    if (u <= l) and (r <= v) then
      begin
        if val[s] = valmax[s] then
          begin
            dec(val[s],r-l+1);
            dec(rem[s]);
            exit;
          end;
        if val[s] = 0 then exit;
      end;
    trans(s,l,r);
    mid := (l + r) div 2;
    Jupdate(2*s,l,mid,u,v);
    Jupdate(2*s+1,mid+1,r,u,v);
    val[s] := val[2*s] + val[2*s+1];
  end;
 
procedure Dupdate(s,l,r,u,v : longint);
  var
    mid : longint;
  begin
    if (r < u) or (v < l) then exit;
    if (u <= l) and (r <= v) then
      begin
        if val[s] = 0 then
          begin
            inc(val[s],r-l+1);
            inc(rem[s]);
            exit;
          end;
        if val[s] = valmax[s] then exit;
      end;
    trans(s,l,r);
    mid := (l + r) div 2;
    Dupdate(2*s,l,mid,u,v);
    Dupdate(2*s+1,mid+1,r,u,v);
    val[s] := val[2*s] + val[2*s+1];
  end;
 
procedure query(c : char; u,v : longint);
  begin
    if c = 'J' then Jupdate(1,1,n,u+1,v)
    else Dupdate(1,1,n,u+1,v);
  end;
 
procedure main;
  var
    i,u,v : longint;
    c : char;
  begin
    init(1,1,n);
    init2(1,1,n);
    for i := 1 to m do
      begin
        read(c);
        if c = 'C' then
          begin
            writeln(val[1]);
            readln;
          end
        else
          begin
            readln(u,v);
            query(c,u,v);
          end;
      end;
  end;
 
 
begin
  assign(input,fi);
  reset(input);
  enter;
  main;
  close(input);
end.

TRAKA – spoj

Đề bài:

Tóm tắt đề

Có N người thợ, M chiếc xe. Người thứ i hoàn thành việc sửa bộ phận xe mình phụ trách với tốc độ T[i]. Xe thứ j có độ rắc rối là F[j]. Thời gian người thứ i cửa xong bộ phận người i phụ trách trên xe j trong thời gian T[i] * F[j]. Các công việc được thực hiện theo thứ tự từ người 1 -> n. Người i làm việc liên tục ko đc dừng lại(tức là sửa xong xe i thì đến xe i + 1). Với mỗi thời điểm t, mỗi chiếc xe chỉ được sửa bởi tối đa 1 người. Tính thời điểm bé nhất để n người sửa xong m chiếc xe.

Dữ Liệu:

  • Dòng đầu gồm 2 số nguyên N (1 <= N <= 100 000) – số người thợ, M (1 <= M <= 100 000) – số chiếc xe cần sửa.
  • Dòng thứ i trong n dòng tiếp theo là T[i] – tốc độ sửa xong bộ phận người i phụ trách.
  • Dòng thứ j trong m dòng tiếp theo là F[j] – độ rắc rối của chiếc xe thứ j.

Kết quả:

  • Gồm 1 dòng là kết quả của bài toán.

Ví dụ:

Input:

3 3
2
1
1
2
1
1

Output:

11

Thuật toán:

Ở bài toán này thì thời điểm kết thúc công việc của người n là kết quả bài toán. Vì mỗi người thợ sẽ làm việc liên tục ko nghỉ nên ta cần tìm thời điểm bắt đầu thực hiện công việc của người n.
Gọi q[i] là tổng độ phức tạp của các chiếc xe từ 1 -> i.

Xét:
Người thứ u bắt đầu công việc từ thời điểm 0, tốc độ C. Thời điểm người u hoàn thành xe i là q[i] * C, hoàn thành xe i + 1 là q[i + 1] * c.
Người thứ v bắt đầu công việc ngay sau u, tốc độ D. Có thời điểm hoàn thành xe i là q[i] * D.
=> Để người v sửa xe i + 1 thì v cần chờ 1 khoảng thời gian là q[i + 1] * C – q[i] * D. Ta cần tìm min(q[i + 1] * C – q[i] * D).
Từ đây, ta để tính được thời điểm bắt đầu làm việc của người n là delta.
Kết quả bài toán là: delta + q[m] * t[n].

Nhận thấy độ phức tạp của thuật toán trâu bò là O(n * m) không đem lại thuật toán đủ tốt để giải bài toán. Nên ta cần tìm cách giảm độ phức tạp xuống.

Vậy, chúng ta nên làm thế nào ?? 😀 ??

Nhìn vào biểu thức q[i + 1] * C – q[i] * D có j đặc biệt ? Đây là biểu thức tích chéo của 2 vector (C; D) * (q[i]; q[i + 1]).

Coi (q[i]; q[i + 1]) là 1 điểm trên mặt phẳng tọa độ Oxy, và ta có vector u = (C; D).
Ta cần tìm điểm A(x, y) sao cho vector OA * u bé nhất. Nhận thấy điểm A cần tìm nằm trên đường lồi.

Trong hình vẽ bên dưới, đường thẳng màu xanh là đường lồi.

traka-yeulaptrinh.pw

Nhận thấy, các điểm trên đường lồi có tích chéo với (C; D) có giá trị theo hình parabol. Đến đây ta có thể áp dụng kĩ thuật chặt nhị phân hoặc tam phân để tìm đỉnh có tích chéo bé nhất.

Độ phức tạp là: O(m * log(n)).

Code:

#include <bits/stdc++.h>
using namespace std;
 
typedef pair <long long, long long> ii;
 
const int N = 1e5 + 10;
 
int n, m, k;
ii A[N], p[N];
long long t[N];
 
ii operator - (ii a, ii b) { return  make_pair(b.first - a.first, b.second - a.second); }
long long operator * (ii a, ii b) { return a.first * b.second - a.second * b.first; }
 
bool cw(ii a, ii b, ii c) { return (b - a) * (c - b) < 0; }
 
void load() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) {
        scanf("%d", &t[i]);
        t[i] += t[i - 1];
    }
    for (int i = 1; i <= n; ++i)
        A[i] = make_pair(t[i - 1], t[i]);
}
 
void findConvexLine() {
    k = 0;
    p[k++] = make_pair(0, 0);
    for (int i = 1; i <= n; ++i) {
        while (k > 1 && !cw(p[k - 2], p[k - 1], A[i])) k--;
        p[k++] = A[i];
    }
}
 
long long get(int x, int y) {
    //ii v = make_pair(x, y);
    int l = 0, r = k - 2, cur = 0;
    while (l <= r) { // (l - 1) * v <= 0 && (r + 1) * v > 0
        int mid = (l + r) >> 1;
        if ((p[mid + 1].first - p[mid].first) * y <= (p[mid + 1].second - p[mid].second) * x) {
            l = mid + 1;
            cur = l;
        } else {
            r = mid - 1;
        }
    }
    return make_pair(x, y) * p[cur];
}
 
void process() {
    findConvexLine();
    int x = 0, y = 0;
    long long delay = 0;
    for (int i = 1; i <= m; ++i) {
        scanf("%d", &y);
        delay += get(x, y);
      //  cerr << get(x, y) << "\n";
        x = y;
    }
    long long ans = delay + 1ll * t[n] * x;
    printf("%lld\n", ans);
}
 
int main() {
 
    load();
    process();
 
    return 0;
}

PWALK – spoj

Đề bài:

Thuật toán:

  • DFS để thiết lập thứ tự cha/con rồi với mỗi truy vấn chỉ cần đi ngược lên đến khi gặp cha chung thì dừng.

Code:

#include <iostream>
#include <vector>
using namespace std;
 
struct pack { int u, c; };
typedef vector<vector<pack>> dsk;
 
int d[1001], bac[1001], cha[1001];
 
void dfs(int u, const dsk &ke) {
    for (pack p: ke[u]) if (p.u != cha[u]) {
        int v = p.u, c = p.c;
        d[v] = c;
        cha[v] = u;
        bac[v] = bac[u] + 1;
        dfs(v, ke);
    }
}
 
int solve(int u, int v) {
#define up(u) sum += d[u], u = cha[u]
    int sum = 0;
    while (bac[u] > bac[v]) up(u);
    while (bac[v] > bac[u]) up(v);
    while (u != v) up(u), up(v);
    return sum;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, q; cin >> n >> q;
    dsk ke(n+1);
    for (int i=1; i<n; i++) {
        int u, v, c;
        cin >> u >> v >> c;
        ke[u].push_back({v, c});
        ke[v].push_back({u, c});
    }
    dfs(1, ke);
    while (q--) {
        int u, v; cin >> u >> v;
        cout << solve(u, v) << '\n';
    }
    return 0;
}

DEGREE – spoj

Đề bài:

Thuật toán:

  • (đang cập nhập)

Code:

#include<algorithm>
#include<iostream>
#include<string.h>
#include<stdio.h>
#include<stdlib.h>
using namespace std;
const int INF=0x3f3f3f3f;
const int maxn=100010;
typedef long long ll;
int dp[35][35],base[35],bin[35];
void init()
{
    dp[0][0]=base[0]=1;
    for(int i=1;i<=32;i++)
    {
        dp[i][0]=1;
        base[i]=base[i-1]<<1;
        for(int j=1;j<=i;j++)
            dp[i][j]=dp[i-1][j]+dp[i-1][j-1];
    }
}
int calc(int x,int k)
{
    int i,one=0,ans=0;
    for(i=31;i>=0;i--)
    {
        if(x&base[i])
        {
            if(one>k)
                break;
            ans+=dp[i][k-one];
            one++;
            x-=base[i];
        }
    }
    if(one==k)
        ans++;
    return ans;
}
int getbin(int x,int b)
{
    int ct=0,i,ret=0;
    if(!x)
        return x;
    while(x)
    {
        bin[ct++]=x%b;
        x/=b;
    }
    for(i=ct-1;i>=0;i--)
    {
        if(bin[i]>1)
            break;
        if(bin[i])
            ret=ret<<1|1;
        else
            ret<<=1;
    }
    while(i>=0)
    {
        ret=ret<<1|1;
        i--;
    }
    return ret;
}
int main()
{
    int x,y,k,b;
 
    init();
    while(~scanf("%d%d%d%d",&x,&y,&k,&b))
    {
        y=getbin(y,b);
        x=getbin(x-1,b);
        printf("%d\n",calc(y,k)-calc(x,k));
    }
    return 0;
}

CROSS12 – spoj

Đề bài:


Thuật toán:


Đầu tiên ta cần tính thời gian qua cầu của mỗi người (khi đi một mình). Có thể tính bằng tham lam như cách được sử dụng trong code ở trên hoặc kết hợp quy hoạch động với deque để tìm min trên đoạn tịnh tiến.

Độ phức tạp khi tính là $O(m)$ cho mỗi người, vì $r$ chỉ dao động từ 1 đến 100 nên ta dùng một mảng phụ để cache giá trị đã tính lại.

Sau khi tính xong, gọi thời gian qua cầu của $n$ người là $A(n)$, ta sắp xếp $A$ tăng dần.

Gọi $F(i)$ là thời gian ít nhất để những người từ 1 đến i qua cầu, ta có công thức:

$ F(1) = A(1) \ F(2) = A(2) \ F(i) = min \begin{cases} F(i-2) + A(1) + 2A(2) + A(i) & \quad (1)\ F(i-1) + A(1) + A(i) & \quad (2)\ \end{cases} $

Trong trường hợp $(1)$, ta cho $A(2)$ quay về, sau đó $A(i)$ và $A(i-1)$ qua cầu, sau đó $A(1)$ từ bên kia cầu quay về, $A(1)$ và $A(2)$ cùng qua cầu.

Trong trường hợp $(2)$, $A(1)$ quay về sau đó cùng $A(i)$ qua cầu.

Code:


#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
using namespace std;
 
int time(int r, int m, const char *bridge) {
    int i = 0, res = 1;
    while (i + r <= m) {
        res++;
        i += r;
        while (bridge[i] == '1') i--;
    }
    return res;
}
 
int main() {
    ios::sync_with_stdio(false); cin.tie(0);
    int n, m; cin >> n >> m;
    vector<int> a(n);
    for (auto &x: a) cin >> x;
    string bridge; cin >> bridge;
    bridge = '0' + bridge + '0';
    vector<int> cache(101, 0);
    for (auto &x: a) {
        if (!cache[x]) x = cache[x] = time(x, m, bridge.data());
        else x = cache[x];
    }
    sort(a.begin(), a.end());
    if (n == 1) cout << a[0];
    else if (n == 2) cout << a[1];
    else {
        int f0 = a[0], f1 = a[1];
        for (int i=2; i<n; i++) {
            int f2 = min(f0 + a[0] + 2*a[1] + a[i], f1 + a[0] + a[i]);
            f0 = f1, f1 = f2;
        }
        cout << f1;
    }
    return 0;
}

UPGRANET – spoj

Đề bài:


Thuật toán:


Ta thấy thông lượng truyền tin từ u đến v là giá trị lớn nhất của cạnh nhỏ nhất trên mọi con đường từ u đến v.
Vì vậy, ban đầu, ta sẽ xây dựng cây khung lớn nhất(tương tự như cây khung nhỏ nhất nhưng sort ngược lại).

Gọi dis(u,v) là cạnh có trọng số nhỏ nhất khi đi từ u đến v trên cây vừa tạo. Ta chọn nút 1 làm gốc, duyệt dfs để lưu trữ cạnh nhỏ nhất và các nút cha của u khi đi từ 1 đến u (đều dùng RMQ). Với mỗi 1 cạnh không nằm trong cây khung, ta tìm nút cha chung gần nhất(gọi là p), kết quả cộng thêm một lượng bằng hiệu của min(dis(u, p), dis(v, p)) và rọng số cạnh đang xét.

Code:


#include <bits/stdc++.h>
#define maxn 1000005
#define maxm 10000005
#define maxc 1000000007
#define mp make_pair
#define pb push_back
#define F first
#define S second
#define pii pair<long long, long long>
#define fort(i, a, b) for(int i = (a); i <= (b); i++)
#define ford(i, a, b) for(int i = (a); i >= (b); i--)
#define Task "UPGRANET"
#define fast ios_base::sync_with_stdio(0);cin.tie();cout.tie();
#define stop1 {cout << "-1\n"; return;}
#define stop2 {cout << "0\n"; return;}
#define stop3 {cout << "yes\n"; exit(0);}
#define skip1 {cout << "Yes\n"; continue;}
#define skip2 {cout << "No\n"; continue;}
#define ll long long
 
using namespace std;
 
ll n, m, root[maxn], h[maxn], res;
pii  par[maxn][20];
bool dd[maxn];
vector<pair<ll, ll> > ke[maxn];
struct canh
{
    ll u, v, w;
}ed[maxn];
 
void setup()
{
    cin >> n >> m;
    fort(i, 1, m)
        cin >> ed[i].u >> ed[i].v >> ed[i].w;
}
 
bool cmp(canh p, canh q)
{
    return p.w > q.w;
}
 
ll getroot(ll u)
{
    if(root[u] == 0) return u;
    return root[u] = getroot(root[u]);
}
 
void make_tree()
{
    sort(ed+1, ed+m+1, cmp);
    fort(i, 1, m)
    {
        ll p = getroot(ed[i].u);
        ll q = getroot(ed[i].v);
        if(p == q) continue;
        root[p] = q;
        dd[i] = 1;
        ke[ed[i].u].pb(mp(ed[i].v, ed[i].w));
        ke[ed[i].v].pb(mp(ed[i].u, ed[i].w));
    }
}
 
void dfs(ll u, ll tr)
{
    fort(i, 0, int(ke[u].size()) - 1)
    {
        ll v = ke[u][i].F;
        if(v == tr) continue;
        h[v] = h[u] + 1;
        par[v][0] = mp(u,ke[u][i].S);
        fort(j, 1, 18)
        {
            par[v][j].F = par[par[v][j-1].F][j-1].F;
            par[v][j].S = min(par[par[v][j-1].F][j-1].S, par[v][j-1].S);
        }
        dfs(v, u);
    }
}
 
pii lca(ll u, ll v)
{
    pii p;
    p.S = 1ll* maxc * maxc;
    if( h[u] > h[v])
        swap(u, v);
    ll diff = h[v] - h[u];
    ford(i, 18, 0)
        if((diff >> i) & 1)
        {
            p.S = min(p.S, par[v][i].S);
            v = par[v][i].F;
 
        }
    if(v == u) return mp(u, p.S);
    ford(i, 18, 0)
        if(par[u][i].F != par[v][i].F)
        {
            p.S = min(p.S, min(par[v][i].S, par[u][i].S));
            v = par[v][i].F;
            u = par[u][i].F;
        }
    return mp(par[u][0].F, min(p.S, min(par[u][0].S, par[v][0].S)));
}
 
void work()
{
    make_tree();
    h[1] = 1;
    dfs(1, 0);
    fort(i, 1, m)
        if(!dd[i])
        {
            pii l = lca(ed[i].u, ed[i].v);
            res += max(0ll, l.S - ed[i].w);
        }
    cout << res;
}
 
 
int main()
{
    fast
  //  freopen(Task".inp", "r", stdin);
  //  freopen(Task".out", "w", stdout);
    setup();
    work();
    return 0;
}

Cowboy

REFORM – SPOJ

Đề bài:

Thuật toán:

    Đề trên SPOJ bị thiếu, bài này có giới hạn n<=10^5, m<=2*10^5.

    Ta có thể phát biểu bài toán dưới dạng đồ thị như sau:

    Cho Một đồ thị vô hướng với n đỉnh và m cạnh, mục tiêu của ta là đếm số
    cách khác nhau để thực hiện 2 bước sau:

    • Loại bỏ một cạnh trong m cạnh của đồ thị
    • Thêm một cạnh mới vào đồ thị (cạnh này phải khác m cạnh lúc đầu) sao cho
      đồ thị mới đảm bảo tính liên thông.

    Ta có nhận xét là do chỉ có thể thêm một cạnh vào đồ thị, do đó số lượng
    thành phần liên thông của đồ thị chỉ có thể tối đa là 2. Ta sẽ chia bài
    toán làm 2 trường hợp: Đồ thị gồm 1 thành phần liên thông và đồ thị gồm
    2 thành phần liên thông.

    Trường hợp thứ nhất – trường hợp đơn giản hơn: Đồ thị gồm 2 thành phần liên thông

    Giả sử 2 thành phần liên thông của đồ thị có số đỉnh lần lượt là C1 và C2
    (tất nhiên C1 = n – C2). Do đồ thị có 2 thành phần liên thông, cạnh ta
    thêm vào phải là cạnh từ thành phần liên thông này sang thành phần liên
    thông kia, có nghĩa là có C1 * C2 cách thêm cạnh, và các cạnh này chắc
    chắn khác với m cạnh lúc đầu. Tuy nhiên ta có thêm nhận xét là cạnh bị
    loại đi không được phép là cầu. Từ đó, giả sử số cầu của đồ thị là c,
    kết quả của ta là (m-c) * C1 * C2.

    Trường hợp thứ hai: Đồ thị có duy nhất một thành phần liên thông

    Cố định cạnh bỏ đi (xét từng cạnh trong m cạnh của đồ t), ta sẽ chia bài
    toán làm 2 trường hợp:

    Trường hợp đầu tiên: cạnh bỏ đi không phải là cầu, khi đó đồ thị vẫn tiếp
    tục liên thông. Tức là ta có thể thêm bất cứ cạnh nào miễn sau cạnh đó khác
    m cạnh lúc đầu là được, như vậy lúc này ta có n(n-1) / 2 – m cách thêm
    cạnh mới.

    Trường hợp thứ hai: cạnh bỏ đi là cầu, khi đó đồ thị sẽ bị chia làm 2 thành
    phần liên thông, và cạnh thêm vào chắc chắn phải nối một đỉnh từ thành phần
    liên thông này sang đỉnh thuộc thành phần liên thông kia (để đảm bảo tính
    chất liên thông của đồ thị). Gọi C1 và C2 là số lượng đỉnh trong 2 thành
    phần liên thông sau khi bỏ đi cạnh đang xét, ta sẽ có C1 * C2 – 1 cách thêm
    cạnh mới vào (-1 do trong C1 * C2 cạnh thì có một cạnh trùng với cạnh vừa bỏ
    đi).

    Lấy tổng số cách trong các trường hợp, ta thu được kết quả của bài toán.

    Độ phức tạp: O(m + n)

Code:

#include <bits/stdc++.h>
#define FORE(i, a, b) for(int i = a; i <= b; i++)
#define FORD(i, a, b) for(int i = a; i >= b; i--)
#define FOR(i, a, b) for(int i = a; i < b; i++)
const int MAXN = 1e5 * 5;
const int INF = 1e9 + 7;
 
using namespace std;
 
int n, m;
bool a[50][50];
typedef pair<int, int> ii;
vector< ii > s1, s2;
int dem;
bool Free[50];
 
inline void duyet(int u)
{
    //cout<<u<<endl;
    dem++;
    Free[u] = 0;
    FORE(v, 1, n) if (u != v && a[u][v] && Free[v] > 0){
        duyet(v);
    }
}
 
vector< int > adj[MAXN];
int Low[MAXN], Num[MAXN], Count = 0, Pa[MAXN], C[MAXN];
 
inline void dfs(int u)
{
    Count++;
    Num[u] = Count;
    Low[u] = n + 1;
    C[u] = 1;
    FOR(i, 0, adj[u].size()){
        int v = adj[u][i];
        if (Pa[v] == 0){
            Pa[v] = u;
            dfs(v);
            C[u] += C[v];
            Low[u] = min(Low[u], Low[v]);
        } else
            if (Pa[u] != v) Low[u] = min(Low[u], Num[v]);
    }
}
 
long long sd[3];
int main()
{
    ios::sync_with_stdio(0); cin.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("REFORM.inp", "r", stdin);
    freopen("REFORM.out", "w", stdout);
    #endif //yeulaptrinh.pw
    cin >> n >> m;
 
    if (n <= 20){
        FORE(i, 1, m){
            int x, y;
            cin >> x >> y;
            a[x][y] = 1;
            a[y][x] = 1;
        }
        long long ans = 0;
        FORE(x, 1, n) FORE(y, x + 1, n) if (a[x][y] == 1){
            s2.push_back(ii(x, y));
        } else s1.push_back(ii(x, y));
        FOR(i, 0, s1.size())
        FOR(j, 0, s2.size()){
            int u1 = s1[i].first, v1 = s1[i].second;
            int u2 = s2[j].first, v2 = s2[j].second;
            a[u1][v1] = 1; a[v1][u1] = 1;
            a[u2][v2] = 0; a[v2][u2] = 0;
            memset(Free, 1, sizeof(Free));
            dem = 0;
           // cout<<u1<<" "<<v1<<" "<<u2<<" "<<v2<<endl;
 
            duyet(1);
            if (dem == n) ans++;
            a[u1][v1] = 0; a[v1][u1] = 0;
            a[u2][v2] = 1; a[v2][u2] = 1;
        }
        cout << ans << endl;
    }
    else
 
    {
        int u, v;
        FORE(i, 1, m){
            cin >> u >> v;
            adj[u].push_back(v);
            adj[v].push_back(u);
        }
        int dlt = 0;
        FORE(u, 1, n) if (Pa[u] == 0){
            Pa[u] = -1;
            Count = 0;
            dfs(u);
            dlt++;
            sd[dlt] = Count;
        }
        //cout<<dlt<<"??"<<endl;
        if (dlt > 2){
            cout << 0 << endl;
            return 0;
        }
 
        //FORE(u, 1, n) cout << C[u]<<" ";cout<<endl;
            long long ans = 0, Cau = 0, SZ = 1LL * n * (n - 1) / 2;
            FORE(v, 1, n){
                u = Pa[v];
                if (u == -1 || Low[v] < Num[v]) continue;
                ans += 1LL * C[v] * (n - C[v]) - 1;
                Cau++;
            }
            //cout << Cau<<"??"<<ans<<endl;
            if (dlt == 1){
                ans += 1LL * (m - Cau) * (SZ - m);
                cout << ans;
            } else{
                long long ans = 1LL * sd[1] * sd[2] * (m - Cau);
                cout << ans;
            }
 
    }
    return 0;
}
const   fi='';
        nmax=1000000;
        mmax=400000;
 
type    data=longint;
var
        f:text;
        adj,x,y:array[0..mmax+1] of data;
        head:array[0..nmax+1] of data;
        sl:array[0..nmax+1] of int64;
        low,num,tr:array[0..nmax+1] of data;
        n,m,dinh,lab,sl1,res,khop,cau:int64;
 
procedure docfile;
var     i,j:data;
begin
        assign(f,fi); reset(f);
        read(f,n,m);
        for i:=0 to n+1 do
                head[i]:=0;
        for i:=1 to m do
                begin
                        read(f,x[i],y[i]);
                        inc(head[x[i]]);
                        inc(head[y[i]]);
                end;
        for i:=1 to n+1 do
                head[i]:=head[i-1]+head[i];
        for i:=1 to m do
                begin
                        adj[head[x[i]]]:=y[i];
                        dec(head[x[i]]);
                        adj[head[y[i]]]:=x[i];
                        dec(head[y[i]]);
                end;
        close(f);
 
 
end;
 
function min(a,b:data):data;
begin
        if a<b then exit(a); exit(b);
end;
 
procedure dfs(u:data);
var     v,k,i:data;
        s:boolean;
begin
        inc(lab);
        low[u]:=lab;
        num[u]:=lab;
        k:=0;
        sl[u]:=1;
        s:=false;
        for v:=head[u]+1 to head[u+1] do
                if tr[u]<>adj[v] then
                        begin
                                if num[adj[v]]=0 then
                                        begin
                                                tr[adj[v]]:=u;
                                                inc(k);
                                                dfs(adj[v]);
                                                if low[adj[v]]>=num[u] then
                                                        s:=true;
                                                sl[u]:=sl[adj[v]]+sl[u];
                                                low[u]:=min(low[u],low[adj[v]]);
                                        end
                                else
                                        low[u]:=min(low[u],num[adj[v]]);
                        end;
        if ((s and (tr[u]<>0)) or ((tr[u]=0) and (k>1))) then inc(khop);
        if (Low[u]=num[u]) and (tr[u]<>0) then inc(cau);
end;
 
procedure ddfs(u:data);
var
        v:data;
begin
        inc(dinh);
        num[u]:=1;
        for v:=head[u]+1 to head[u+1] do
                if num[adj[v]]=0 then
                        ddfs(adj[v]);
end;
 
procedure xuli;
var     i,j:data;
        stplt:int64;
begin
        for i:=1 to n do
                num[i]:=0;
        stplt:=0;
        sl1:=0;
        for i:=1 to n do
                if num[i]=0 then
                        begin
                                dinh:=0;
                                ddfs(i);
                                if sl1=0 then
                                        sl1:=dinh;
                                inc(stplt);
                        end;
        if stplt>2 then
                begin
                        writeln('0');
                        exit;
                end;
        for i:=1 to n do
                num[i]:=0;
        tr:=num;
 
        cau:=0;
        khop:=0;
        lab:=0;
        for i:=1 to n do
                if num[i]=0 then
                        dfs(i);
        if stplt=1 then
                begin
                        res:=(m-cau)*((n*(n-1)) div 2 - m);
                        for i:=2 to n do
                                if low[i]=num[i] then
                                        res:=res+int64(sl[i])*(int64(n-sl[i]))-1;
                        writeln(res);
                        exit;
                end;
        if stplt=2 then
                begin
                        res:=(m-cau)*sl1*(n-sl1);
                        writeln(res);
                end;
end;
 
begin
        docfile;
        xuli;
end.