#pragma once
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<queue>
#define rep(i,n) for(auto i=0;i<(n);i++)
#define all(vs) (vs).begin(),(vs).end()
#define roundup(A,B) (A)/(B)+((A)%(B)==0?0:1)
#define read(type,name) type name;cin>>name
using namespace std;


/*
  予想と答えをすべて比較するのが最速。O(n)
*/
void A() {
	string s, t;
	cin >> s >> t;
	int answer = 0;
	rep(i, s.length()) {
		if (s[i] == t[i])answer++;
	}
	cout << answer << endl;
}

/*
  タップを使うごとにA-1ずつ増える。Bと1の距離をA-1で割った（切り上げ）のが答え。
  A,Bの値によらないのでO(1)の解法である。
*/
void B() {
	int A, B; cin >> A >> B;
	cout << roundup(B-1, A-1) << endl;
}

/*
  左から走査することで最大長を求めることができる。最大長を0で初期化し、
  左端からスタートする。右に進める限り現在の長さをincrementし、進めなくなったところで最大長を更新する。
  そして止まったところからリセットして再開する。これを繰り返すことで最大長を求めることができる。
  計算量はO(n)、空間量はO(1)となる。
*/
void C() {
	int n; cin >> n;
	int length = 0, max_length = 0;
	int prev = 0, current;
	rep(i, n) {
		cin >> current;
		if (prev >= current) {
			length++;
		} else {
			max_length = max(max_length, length);
			length = 0;
		}
		prev = current;
	}
	max_length = max(max_length, length);
	cout << max_length << endl;
}

/*
　剰余を最大にするのは、MをM+1で割った場合であるから、
 iに対して1つずれた順列を作れば最適である。配列の最後Nについては、
 N+1を用意することはできないので、1で剰余を取る（必ず10になる）。
 このやり方で和を求めた場合は、1からN-1までの和に等しいので(N-1)(N)/2となる。
 　　->これが最大っていうのはどうわかるの?
*/
void D() {
	read(int, n);
	cout << n * (n - 1) / 2 << endl;
}

/*
　総当たりで調べてO(N^2)を試してみよう
*/
struct Player {
	queue<int> versus{};
	bool available{ true };
	bool matchable(int i) {
		return available && versus.front() == i;
	}
};
void E() {
	read(int, n);
	auto ps = vector<Player>(n);
	rep(i, n) {
		rep(j, n - 1) {
			read(int, p);
			ps[i].versus.push(p - 1);
		}
	}
	int days = 0;
	int remains = n;
	while (true) {
		bool matched = false;
		rep(i, ps.size()) {
			if (!ps[i].available||ps[i].versus.empty())continue;
			auto v = ps[i].versus.front();
			if (ps[v].matchable(i)) {
				matched = true;
				ps[i].versus.pop(); ps[i].available = false; if (ps[i].versus.empty()) remains--;
				ps[v].versus.pop(); ps[v].available = false; if (ps[v].versus.empty()) remains--;
			}
		}
		for (auto& p : ps)p.available = !p.versus.empty();
		days++;
		if (remains == 0) {
			cout << days << endl;
			return;
		}
		if (!matched) {
			cout << -1 << endl;
			return;
		}
	}
}

int main() {
	E();
}


#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#include <string>
#include <math.h>
#include <iomanip>
#include <limits>
#include <list>
#include <queue>
#include <tuple>
#include <map>
#include <stack>
#include <set>
#include <bitset>
using namespace std;
#define fast_io ios_base::sync_with_stdio (false) ; cin.tie(0) ; cout.tie(0) ;
#define MOD (long long int)(998244353)
#define ll long long int
#define rep(i,n) for(int i=0; i<(int)(n); i++)
#define reps(i,n) for(int i=1; i<=(int)(n); i++)
#define REP(i,n) for(int i=n-1; i>=0; i--)
#define REPS(i,n) for(int i=n; i>0; i--)
#define INF (int)(1123456789)
#define LINF (long long int)(112345678901234567)
#define chmax(a, b) a = (((a)<(b)) ? (b) : (a))
#define chmin(a, b) a = (((a)>(b)) ? (b) : (a))
#define all(v) v.begin(), v.end()

typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

ll mpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = mpow(a,b/2); return memo*memo%MOD;}
  else return mpow(a,b-1) * a % MOD;
}
ll lpow(ll a, ll b){
  if(b==0) return 1;
  else if(b%2==0){ll memo = lpow(a,b/2); return memo*memo;}
  else return lpow(a,b-1) * a;
}
ll gcd(ll a, ll b){
  if(b==0) return a;
  else return gcd(b, a%b);
}
vector<ll> kaijo_memo;
ll kaijo(ll n){
  if(kaijo_memo.size() > n) return kaijo_memo[n];
  if(kaijo_memo.size() == 0) kaijo_memo.push_back(1);
  while(kaijo_memo.size() <= n) kaijo_memo.push_back(kaijo_memo[kaijo_memo.size()-1] * kaijo_memo.size() % MOD);
  return kaijo_memo[n];
}
vector<ll> gyaku_kaijo_memo;
ll gyaku_kaijo(ll n){
  if(gyaku_kaijo_memo.size() > n) return gyaku_kaijo_memo[n];
  if(gyaku_kaijo_memo.size() == 0) gyaku_kaijo_memo.push_back(1);
  while(gyaku_kaijo_memo.size() <= n) gyaku_kaijo_memo.push_back(gyaku_kaijo_memo[gyaku_kaijo_memo.size()-1] * mpow(gyaku_kaijo_memo.size(), MOD-2) % MOD);
  return gyaku_kaijo_memo[n];
}

ll nCr(ll n, ll r){
  if(n == r) return 1;//0個の丸と-1個の棒みたいな時に時に効く？不安.
  if(n < r || r < 0) return 0;
  ll ret = 1;
  ret *= kaijo(n); ret %= MOD;
  ret *= gyaku_kaijo(r); ret %= MOD;
  ret *= gyaku_kaijo(n-r); ret %= MOD;
  return ret;
}

vector<ll> G[(int)1e5+2];
bool checked[(int)1e5+2];
int color[(int)1e5+2];

bool saiki(int now, int col){
  if(checked[now]){
    return color[now] == col;
  }
  checked[now] = true;
  color[now] = col;
  rep(j, G[now].size()){
    int next = G[now][j];
    if(!saiki(next, (col+1) & 1)){
      return false;
    }
  }

  return true;
}

int main(void){
  fast_io
  cout<<fixed<<setprecision(15);

  ll n,m;
  cin>>n>>m;
  rep(i,m){
    ll a,b;cin>>a>>b;a--;b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }

  if(!saiki(0, 0)){
    cout<< n * (n-1) / 2 - m << endl;
    return 0;
  }

  ll C0 = 0, C1 = 0;
  rep(i,n){
    if(color[i] == 0){
      C0++;
    }else{
      C1++;
    }
  }
  cout<< C0 * C1 - m <<endl;

  return 0;
}