#include <bits/stdc++.h>
using namespace std;
using pii = pair<int,int>;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int a,b,m;
if(!(cin>>a>>b>>m)) return 0;
vector<int> X(m), Y(m);
vector<vector<pii>> adjA(a+1), adjB(b+1); // store (other, edge_id)
for(int i=0;i<m;i++){
cin>>X[i]>>Y[i];
adjA[X[i]].push_back({Y[i], i});
adjB[Y[i]].push_back({X[i], i});
}
vector<int> compA(a+1, 0), compB(b+1, 0);
vector<int> ans(m, -1); // -1 = not set, 0 = A->B, 1 = B->A
int compId = 0;
// helper to find next index >= pos with (not yet assigned) and deg>0
auto nextA_with_deg = [&](int start)->int{
for(int i=start;i<=a;i++){
if(compA[i]==0 && !adjA[i].empty()) return i;
}
return -1;
};
auto nextB_with_deg = [&](int start)->int{
for(int j=start;j<=b;j++){
if(compB[j]==0 && !adjB[j].empty()) return j;
}
return -1;
};
int curA = 1, curB = 1;
while(true){
// find leftmost unprocessed with flights on each river
int la = nextA_with_deg(curA);
int lb = nextB_with_deg(curB);
if(la==-1 && lb==-1) break; // no more multi-node components to form
// If one side missing, we must still start from the other side's leftmost with flights
if(la == -1) { la = ++a; /* won't actually happen because adjB has edges -> assures both exist */ }
if(lb == -1) { lb = ++b; }
// expand intervals
int ra = la, rb = lb;
int pA = la, pB = lb;
// We'll only expand over nodes that are not yet assigned; that's ensured since la/lb found unassigned nodes.
while(pA <= ra || pB <= rb){
while(pA <= ra){
// process all edges of pA
for(auto [y,eid] : adjA[pA]){
if(y > rb){
// this flight causes expansion of rb: orient it B->A (1)
if(ans[eid] == -1) ans[eid] = 1;
rb = max(rb, y);
} else {
// edge to already-in-range y: leave for later (or set arbitrary)
// do nothing now
}
}
++pA;
}
while(pB <= rb){
for(auto [x,eid] : adjB[pB]){
if(x > ra){
// this flight causes expansion of ra: orient it A->B (0)
if(ans[eid] == -1) ans[eid] = 0;
ra = max(ra, x);
} else {
// internal edge: leave for later
}
}
++pB;
}
}
// assign component id to the whole interval pair
++compId;
for(int i=la;i<=ra;i++) compA[i] = compId;
for(int j=lb;j<=rb;j++) compB[j] = compId;
// move curA/curB forward
while(curA <= a && compA[curA] != 0) ++curA;
while(curB <= b && compB[curB] != 0) ++curB;
}
// Remaining cities (those that never had flights or were not covered) become singleton components
for(int i=1;i<=a;i++){
if(compA[i]==0) compA[i] = ++compId;
}
for(int j=1;j<=b;j++){
if(compB[j]==0) compB[j] = ++compId;
}
// For any edge not assigned during expansion, orient it from earlier component -> later component
for(int i=0;i<m;i++){
if(ans[i] != -1) continue;
int ca = compA[X[i]];
int cb = compB[Y[i]];
if(ca < cb) ans[i] = 0; // A->B
else ans[i] = 1; // B->A
}
// Number of SCCs equals compId
cout << compId << '\n';
for(int i=0;i<m;i++){
if(i) cout << ' ';
cout << ans[i];
}
cout << '\n';
return 0;
}
