誰も辞退しなかったとき、すなわち投票者全員が第一候補に投票したときの当選者を候補者 \(X\), このとき、ついで得票数が多い候補者を候補者 \(Y\). とします。ここで、当選者の ときと同様に、得票数が同じ場合は番号が小さい方を選ぶことにします。
また、以下では、\(1\leq k\leq N\) について、候補者 \(k\)を第一候補としている投票者の人数を \(N_k\) で表します。

ある候補者 \(k\) が辞退したとき、候補者 \(k\) を第一候補としていた投票者 \(N_k\) 人の第二候補がそれぞれ \(c_1,c_2,\ldots, c_{N_k}\) であったとすると、このときの当選者としてあり得るのは候補者 \(X,Y, c_1,c_2,\ldots, c_{N_k}\) のみです。
なぜなら、これ以外の候補者 \(Z\) の得票数は辞退前の時点で \(X,Y\) より少なく（あるいは同票で番号が大きく）、候補者 \(k\) の辞退によって増えていません。このとき、候補者 \(X,Y\) の少なくとも一方は辞退しておらず、得票数が減ることはないため、その候補者（\(X\) または \(Y\)）より優先して当選することはできないためです。

このことを踏まえて、それぞれの候補者が辞退した時の投票結果をシミュレーションし、当選者を決定することを考えます。

投票結果は、それぞれの場合について各投票者の投票先を確認すると全体で \(\Theta(M^2)\) の時間計算量がかかりますが、誰も辞退しなかった時の状態を最初にシミュレーションし、それぞれの候補が辞退した時の差分をぞれぞれの場合について反映することで、前計算に \(O(M)\)、 候補者 \(k\) が辞退するケースにおいて \(O(N_k)\). となるためすべてのケースについて合計で \(O(M)\) で求めることができます。
具体的には、各候補者についてその候補者を第一候補としている投票者のリストを保持しておき、候補者 \(k\) が辞退するときは、候補者 \(k\) の得票数を \(0\) にするかわり、その \(N_k\) 人の投票者それぞれの第二候補の得票数を増やせば良いです。
それぞれの場合の当選者の候補は先に挙げた高々 \((N_k+2)\) 人であるため、それぞれの得票数を確認すれば良いです。よって、それぞれの場合の当選者も \(O(N_k)\) で決定することができます。

ゆえに、全体で \(O(N+M)\) ですべての場合の当選者を求めることができました。

C++ による実装例:

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

#define N (int)2e+5

int main(void){
	int n,m,x,y;
	pair<int,int> c1={N,-1},c2={N,-1}; //candidate,received vote
	vector<int>a[N];
	int b[N]={};

	cin>>n>>m;
	for(int i=0;i<m;i++){
		cin>>x>>y;
		a[x-1].push_back(y-1);
		b[x-1]++;
	}

	for(int i=0;i<n;i++){
		if(b[i]>c1.second){c2=c1; c1={i,b[i]};}
		else if(b[i]>c2.second)c2={i,b[i]};
	}

	for(int i=0;i<n;i++){
		int sz=a[i].size();
		for(int j=0;j<sz;j++)b[a[i][j]]++;
		b[i]=0;

		pair<int,int> c0={N,-1};
		for(int j=0;j<sz+2;j++){
			if(j<sz)x=a[i][j];
			else if(j==sz)x=c1.first;
			else x=c2.first;
			if(b[x]>c0.second)c0={x,b[x]};
			else if((b[x]==c0.second)&&(x<c0.first))c0={x,b[x]};
		}
		cout<<(c0.first+1)<<endl;


		b[i]=sz;
		for(int j=0;j<sz;j++)b[a[i][j]]--;
	}
	return 0;
}