#include<bits/stdc++.h>
#define SORT(v) sort(v.rbegin() , v.rend())
#define si(n) scanf( "%d" , &n)
#define sii(n , m) scanf( "%d %d" , &n , &m)
#define sl(n) scanf( "%lld" , &n)
#define sll(n , m) scanf( "%lld %lld" , &n, &m)
#define ss(cad) scanf( "%s" , cad)
#define sz(x) (int)x.size()
#define PB push_back
#define fst first
#define scn second
#define DBG(x) cerr << #x << " = " << (x) << endl
#define M 1000000007
#define N_MAX 1000010
#define EPS 1e-9

using namespace std;

typedef long long ll;
typedef vector<int> vi;
typedef vector<bool> vb;
typedef vector<ll> vll;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<pi> vp;

void mostrar(set<pi> ls){
	for(auto x: ls)
		printf("(%d, %d) ", x.fst, x.scn);
}

int main(){
	int h, w;
	sii(h, w);
	set<pi> lista;
	multiset<int> num;
	for(int i = 1; i <= w; i++){
		lista.insert({i, 1});
		num.insert(1);
	}
	int cnt = 0;
	while(h--){
		int a, b;
		sii(a, b);
		bool sw = 0;
		auto pt = lista.lower_bound(pi(a, -1));
		auto pt2 = pt;
		pi mitad = {-1, -1};
		pi inicio;
		if(pt != lista.begin()){
			sw = 1;
			pt--;
			mitad = *pt;
			inicio = *pt;
			pt++;
		}
		while(pt != lista.end() && pt->fst <= b){
			pt2 = pt;
			mitad = *pt;
			num.erase(num.lower_bound(mitad.scn));
			pt++;
			lista.erase(pt2);
		}
		pt2 = lista.lower_bound(pi(b+1, -1));
		if(mitad.fst != -1 && b != w){
			if(pt2 != lista.end() && pt2->fst != b+1){
				int val = mitad.scn + b-mitad.fst+1;
				//update(val, 1);
				num.insert(val);
				lista.insert({b+1, val});
			}
			else if(pt2 == lista.end()){
				int val = mitad.scn + b-mitad.fst+1;
				//update(val, 1);
				num.insert(val);
				lista.insert({b+1, val});
			}
		}
		if(sw){
			int val = inicio.scn + a-inicio.fst;
			//update(val, 1);
			num.insert(val);
			lista.insert({a, val});
		}
		if(num.empty())
			printf("-1\n");
		else
			printf("%d\n", *num.begin()+cnt);
		//mostrar(lista);
		//cout << endl;
		cnt++;
	}
    return 0;
}
/*
Though leaves are many , the root is one.
Through all the lying days of my youth
I swayed my leaves and flowers in the sun.
Now I may wither into the truth.
	  	  	- William Butler Yeats
*/
//#pragma GCC optimize("Ofast,no-stack-protector")
//#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx")
//#pragma GCC target("avx,tune=native")
#include<bits/stdc++.h>
#pragma comment("-Wl,--stack=1024000000")
//#include<ext/pb_ds/assoc_container.hpp>
using namespace std;
//using namespace __gnu_pbds;
const int inf=0x3f3f3f3f;
const double eps=1e-6;
const int mod=1000000007;
typedef long long ll;
#ifndef LOCAL
#define cerr if(0)cout
#define eprintf(...) 0
#else
#define eprintf(...) fprintf(stderr, __VA_ARGS__)
#endif
inline string getstr(string &s,int l,int r){string ret="";for(int i=l;i<=r;i++)ret.push_back(s[i]);return ret;}
int modpow(int x,int y,int md=mod){int ret=1;do{if(y&1)ret=(ll)ret*x%md;x=(ll)x*x%md;}while(y>>=1);return ret;}
inline int Rand(){return rand()*32768+rand();}
int n,m,sz,cnt;
vector<int>g[100005]; 
int col[100005],id[100005];
void dfs(int x,int ind){
	sz++;
	for(auto to:g[x]){
		if(!col[to]){
			col[to]=3-col[x];
			id[to]=ind;
			dfs(to,ind);
		}
	}
}
bool bin[100005];
int main(){
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int x,y;cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	int tot=0;
	for(int i=1;i<=n;i++){
		if(!col[i]){
			col[i]=1;
			id[i]=++tot;
			sz=0;
			dfs(i,tot);
			if(sz==1)cnt++;
		}
	}
	for(int i=1;i<=tot;i++)bin[i]=1;
	for(int i=1;i<=n;i++){
		for(auto to:g[i]){
			if(col[i]==col[to]){
				bin[id[i]]=0;
			}
		}
	}
	int cnt1=-cnt,cnt2=0;
	for(int i=1;i<=tot;i++){
		if(bin[i])cnt1++;
		else cnt2++;
	}
	cout<<(ll)n*n-(ll)(n-cnt)*(n-cnt)+(ll)(tot-cnt)*(tot-cnt)+(ll)cnt1*cnt1<<endl;
	return 0;
}