We introduce two solutions.

Solution 1: backtrack the operations

The piece placed by the \(i\)-th operation stays alive by the end if and only if none of the \((i+1)\)-th operation and later places a piece in row \(R_i\) nor column \(C_i\).
This means that if the operations are scanned in reversed order, from the \(M\)-th to \(1\)-st, if any operation inspected so far places a piece in row \(R_i\) or column \(C_i\), then the piece placed by the current operation will not stay alive, and otherwise it will. Therefore, by managing for each row and column whether at least one piece has been already placed in that row (column) while backtracking the operations from the \(M\)-th to \(1\)-st, one can enumerate the pieces that stay alive, and in particular, the number of those pieces. The time complexity is \(O(M)\), which is fast enough.

Solution 2:

At any moment during the procedure, each row and column contains at most one piece. Therefore, for each row and column, one can manage whether the row (column) contains a piece, and if does, which operation placed the piece. It is also guaranteed that an operation removes at most two pieces, and each operation can be simulated in a constant time.
In this case too, the complexity is \(O(M)\), or \(O(N+M)\) depending on the implementation approach. In any case, it is fast enough.

Sample code In C++ (Solution 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;
}

Sample code in C++ (Solution 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;
}