#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;
using vc = vector<char>;
using vvc = vector<vc>;
using pll = pair<ll, ll>;
using stkll = vector<pll>;
const ll INF = 1LL << 60;
const ll MOD = 1e9 + 7;
#define rep(i, n) for (ll i = 0; i < (n); i++)
template<typename T1,typename T2> inline void chmin(T1 &a,T2 b){if(a>b) a=b;}
template<typename T1,typename T2> inline void chmax(T1 &a,T2 b){if(a<b) a=b;}
#ifndef ONLINE_JUDGE
    #define debug(x) cerr << #x << ": " << x << endl;
#else
    #define debug(x)
#endif

vvll g;
vll color(110000, 0);
bool dfs(ll x, ll p = -1, ll c = 0) {
    color[x] = c;
    for(auto nx : g[x]) {
        if(color[nx] == c) return false;
        if(color[nx] ==0 && !dfs(nx, x, -c)) return false;
    }
    return true;
}


int main() {
    cin.tie(0);
    ios::sync_with_stdio(false);
    cout << fixed << setprecision(20);

    ll n, m;
    cin >> n >> m;
    g = vvll(n);
    rep(i,m) {
        ll a, b;
        cin >> a >> b;
        a--, b--;
        g[a].push_back(b);
        g[b].push_back(a);
    }
    bool is_bipartite = dfs(0, -1, 1);
    if(is_bipartite) {
        ll cw = 0, cb = 0;
        rep(i, n) {
            if(color[i] == 1) cw++;
            else cb++;
        }
        cout << cw * cb - m << endl;
    }
    else cout << n * (n-1) / 2 - m << endl;
}

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define mod 1000000007
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { cerr << (itr) << " "; }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

int main() {
  int n, m;
  cin >> n >> m;
  vector<int> a(n-1+m), b(n-1+m), in(n);
  vector<vector<int>> G(n);
  for (int i = 0; i < n+m-1; ++i) {
    cin >> a[i] >> b[i];
    a[i] --, b[i] --;
    G[a[i]].push_back(b[i]);
    in[b[i]] ++;
  }

  int root = -1;
  int edge = n+m-1;
  for (int i = 0; i < n; ++i) {
    if (in[i] == 0) {
      root = i;
      break;
    }
  }

  queue<int> que;
  que.push(root);
  vector<int> dist(n);

  while (!que.empty()) {
    auto now = que.front();
    que.pop();

    for (auto to : G[now]) {
      chmax(dist[to], dist[now] + 1);
      in[to] --;
      if (in[to] == 0) {
        // 根の子の入次数は1だから必ずここには入る
        // 親に対しても有向辺を貼る可能性はないので途中で探索が終わることもない
        que.push(to);
      }
    }
  }

  vector<int> ans(n, 0);
  for (int i = 0; i < n; ++i) {
    for (auto&& to : G[i]) {
      if (dist[to] - dist[i] == 1) {
        ans[to] = i+1;
      }
    }
  }

  for (auto it : ans) {
    cout << it << endl;
  }
}