#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
const int MAXN = 1e5;
const int MAXM = 5e5;
int A, B, M;
pii E[MAXM+10];
int CA[MAXN+10], CB[MAXN+10];
bool S[MAXM*2+10], T[MAXN+10];
vector<pii> adj1[MAXN+10], adj2[MAXN+10];
vector<int> cir;
int ans[MAXM+10];
void dfs(int now, int edge, int col)
{
if(col==1)
{
T[now]=1;
for(auto &nxt : adj1[now])
{
if(S[nxt.second]) continue;
S[nxt.second]=1;
dfs(nxt.first, nxt.second, 2);
}
}
else
{
for(auto &nxt : adj2[now])
{
if(S[nxt.second]) continue;
S[nxt.second]=1;
dfs(nxt.first, nxt.second, 1);
}
}
if(edge!=-2) cir.push_back(edge);
}
void solve(vector<int> &V, int &k)
{
int i, j;
vector<int> acomp, bcomp;
for(auto &it : V)
{
if(!CA[E[it].first]) acomp.push_back(E[it].first);
if(!CB[E[it].second]) bcomp.push_back(E[it].second);
CA[E[it].first]++; CB[E[it].second]++;
}
int maxdeg=0;
for(auto &it : acomp) maxdeg=max(maxdeg, CA[it]);
for(auto &it : bcomp) maxdeg=max(maxdeg, CB[it]);
if(maxdeg<=1)
{
for(auto &it : V) ans[it]=k;
for(auto &it : acomp) CA[it]=0;
for(auto &it : bcomp) CB[it]=0;
vector<int>().swap(V);
vector<int>().swap(acomp);
vector<int>().swap(bcomp);
k++; return;
}
for(auto &it : V)
{
adj1[E[it].first].push_back({E[it].second, it});
adj2[E[it].second].push_back({E[it].first, it});
}
int cnt=0;
int num=M+1;
for(auto &it : acomp) if(CA[it]%2)
{
adj1[it].push_back({0, num});
adj2[0].push_back({it, num});
num++;
cnt++;
}
for(auto &it : bcomp) if(CB[it]%2)
{
adj2[it].push_back({0, num});
adj1[0].push_back({it, num});
num++;
}
if(cnt%2)
{
adj1[0].push_back({0, num});
adj2[0].push_back({0, num});
num++;
}
acomp.push_back(0); bcomp.push_back(0);
for(auto it : acomp) if(!T[it]) dfs(it, -2, 1);
for(auto &it : V) S[it]=0;
for(i=M+1; i<num; i++) S[i]=0;
vector<int>().swap(V);
for(auto &it : acomp) CA[it]=0;
for(auto &it : bcomp) CB[it]=0;
for(auto &it : acomp) T[it]=0;
for(auto &it : acomp) vector<pii>().swap(adj1[it]);
for(auto &it : bcomp) vector<pii>().swap(adj2[it]);
vector<int>().swap(acomp);
vector<int>().swap(bcomp);
vector<int> L, R;
for(i=0; i<cir.size(); i++)
{
if(cir[i]<=M)
{
if(i%2) L.push_back(cir[i]);
else R.push_back(cir[i]);
}
}
vector<int>().swap(cir);
solve(L, k);
solve(R, k);
}
int main()
{
int i, j;
scanf("%d%d%d", &A, &B, &M);
for(i=1; i<=M; i++) scanf("%d%d", &E[i].first, &E[i].second);
vector<int> V;
for(i=1; i<=M; i++) V.push_back(i);
int ans2=1;
solve(V, ans2);
printf("%d\n", ans2-1);
for(i=1; i<=M; i++) printf("%d\n", ans[i]);
}
