#include <bits/stdc++.h> using namespace std; typedef long long ll; #define endl "\n" ll p[100005], siz[100005], ranking[100005]; void reset(ll n) { ll i; for(i = 1; i <= n; i++) { p[i] = i; siz[i] = 1; ranking[i] = 0; } } ll parent(ll v) { if(p[v] == v) { return v; } return p[v] = parent(p[v]); } void merge(ll u, ll v) { ll x = parent(u); ll y = parent(v); if(x == y) { return; } if(ranking[x] > ranking[y]) { p[y] = x; siz[x] += siz[y]; } else { p[x] = y; siz[y] += siz[x]; if(ranking[x] == ranking[y]) { ranking[y]++; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); ll t = 1; //cin >> t; while(t--) { ll n, m, q; cin >> n >> m >> q; ll a[q + 1], b[q + 1], l[q + 1], r[q + 1], i; for(i = 1; i <= q; i++) { cin >> a[i] >> b[i]; l[i] = 1; r[i] = m; } reset(n); vector<ll>cand[m + 1]; while(true) { //cout << "?" << endl; bool ischange = false; for(i = 1; i <= q; i++) { if(l[i] != r[i]) { ischange = true; //cout << i << " " << l[i] << " " << r[i] << endl; ll mid = (l[i] + r[i]) / 2; cand[mid].push_back(i); } } if(ischange == false) { break; } for(i = 1; i <= m; i++) { ll j; ll rielval = m - i + 1; //cout << rielval << endl; for(j = rielval * 2; j <= n; j += rielval) { merge(rielval, j); } if(cand[i].size() == 0) { continue; } while(cand[i].size() != 0) { ll idx = cand[i].back(); //cout << i << " " << idx << endl; cand[i].pop_back(); ll x = parent(a[idx]), y = parent(b[idx]); if(x == y) { r[idx] = i; } else { l[idx] = i + 1; } } } reset(n); } for(i = 1; i <= q; i++) { cout << r[i] << endl; } cout << endl; } #ifndef ONLINE_JUDGE cerr << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; #endif return 0; } // Author: tryharderforioi100