考虑整个建边过程，任意 (a,b) 都连边肯定不好搞，因为只要求连通，所以看一下有没有等价方案，发现在某一天 m-i+1=g 时，把所有的 kg 向 g 连边是等价的，可以直接把询问两个端点丢到对应集合里，每次合并枚举小集合查大集合就能做到 n\log n
#include<bits/stdc++.h>
using namespace std;
#define fio(x) freopen(x".in","r",stdin),freopen(x".out","w",stdout)
#define tio() freopen("in.txt","r",stdin),freopen("out.txt","w",stdout)
using ll=long long ;
const int N=1e5+10;
int n,m,q;
set<int>s[N];
int ans[N];
int fa[N];
int siz[N];
int find(int x){return fa[x]==x?x:fa[x]=find(fa[x]);}
void mer(int x,int y,int t){
x=find(x),y=find(y);
if(x==y)return ;
if(siz[x]<siz[y])swap(x,y);
for(auto it=s[y].begin();it!=s[y].end();++it){
if(s[x].count(*it))ans[*it]=t,s[x].erase(*it);
else s[x].insert(*it);
}
fa[y]=x;
siz[x]+=siz[y];
}
int main(){
// fio("bridge");
// tio();
scanf("%d%d%d",&n,&m,&q);
for(int i=1;i<=q;++i){
int a,b;
scanf("%d%d",&a,&b);
s[a].insert(i);
s[b].insert(i);
}
for(int i=1;i<=n;++i)fa[i]=i,siz[i]=1;
for(int i=m;i>0;--i){
for(int j=2*i;j<=n;j+=i){
mer(i,j,m-i+1);
}
}
for(int i=1;i<=q;++i)
printf("%d\n",ans[i]);
return 0;
}