以下では、2つの解法を紹介します。

解法1: 操作を後ろからさかのぼる解法

\(i\) 回目の操作で置かれたコマが最後まで残っている必要十分条件は　は、\(i+1\) 回目以降の操作において、\(R_i\) 行目にも \(C_i\) 列目にも一度もコマが置かれていないことです。
これは、操作を逆順、すなわち\(M\) 回目から \(1\) 回目の順に戻るように見ると、それまでに見た操作の中で \(R_i\) 行目または \(C_i\) 列目にコマを置く操作が存在するならばその操作で置かれたコマは最後まで残らず、そうでないならば残るということになります。これより、各行・各列においてその行（列）にコマを置く操作が行われたかを管理しつつ、操作を\(M\) 回目から \(1\) 回目まで順に確認することによって、最後に残るコマを列挙、特にその個数を求めることができます。時間計算量は \(O(M)\) であり、十分高速です。

解法2: 各行、各列に置かれたコマを管理する方法

操作の途中の任意のタイミングにおいて、各行・各列には高々 \(1\) つのコマしか置かれていないことに注意すると、各行・各列ごとに、その行にコマが置かれていない、あるいは置かれているならばどの操作によるコマが置かれているかを配列によって管理することができます。また、このことから \(1\) 回の操作によって取り除かれるコマは高々 \(2\) つであり、それぞれの操作のシミュレーションを定数時間で行うことができます。
この場合も計算量は \(O(M)\) ないし実装方針によっては \(O(N+M)\) となります。いずれの場合でも十分高速です。

C++ による実装例（解法1）:

#include <bits/stdc++.h>
using namespace std;

#define N 300000
#define M 300000

int main(void){
	int n,m,ans=0;
	int r[M],c[M];
	bool rused[N+1]={},cused[N+1]={};

	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>r[i]>>c[i];
	}
	for(int i=m-1;i>=0;i--){
		if((!rused[r[i]])&&(!cused[c[i]]))ans++;
		rused[r[i]]=true;
		cused[c[i]]=true;
	}
	cout<<ans<<endl;
	return 0;
}

C++ による実装例（解法2）:

#include <bits/stdc++.h>
using namespace std;

#define N 300000
#define M 300000

int main(void){
	int n,m,idx,ans=0;
	int r[M+1],c[M+1];
	int rplace[N+1]={},cplace[N+1]={};

	cin>>n>>m;
	for(int i=1;i<=m;i++){
		cin>>r[i]>>c[i];
		if(rplace[r[i]]>0){
			idx=rplace[r[i]];
			rplace[r[idx]]=0;
			cplace[c[idx]]=0;
			ans--;
		}
		if(cplace[c[i]]>0){
			idx=cplace[c[i]];
			rplace[r[idx]]=0;
			cplace[c[idx]]=0;
			ans--;
		}
		rplace[r[i]]=i;
		cplace[c[i]]=i;
		ans++;
	}
	
	cout<<ans<<endl;
	return 0;
}