#include <bits/stdc++.h>
#define X first
#define Y second
#define MP make_pair
#define ll long long
using namespace std;
const int N = 1e5 + 1, BS = 300;
const ll INF = 1e18;
int n, m, q, used[N], dp[N];
vector< int > g[N];
vector< pair<int, int> > gg[N];
int main () {
ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
cin >> n >> m >> q;
for(int i = 1, x, y;i <= y;i++){
cin >> x >> y;
g[y].push_back(x);
}
set< pair<int, int> > act;
for(int i = 2;i <= n;i++){
act.clear();
for(int from: g[i]){
if(used[from] != i)
used[from] = i, dp[from] = 1, act.insert(MP(1, from));
for(pair<int, int> tmp: gg[from]){
if(used[tmp.Y] != i)
dp[tmp.Y] = 0, used[tmp.Y] = i;
if(tmp.X + 1 > dp[tmp.Y]){
act.erase(MP(dp[tmp.Y], tmp.Y));
dp[tmp.Y] = tmp.X + 1;
act.insert(MP(dp[tmp.Y], tmp.Y));
if(act.size() > BS)
used[act.begin()->Y] = -1, act.erase(act.begin());
}
}
while(!act.empty()){
gg[i].push_back(*act.begin());
act.erase(act.begin());
}
}
}
}
