#include <bits/stdc++.h>
using namespace std;
#define pii pair<int, int>
const int maxN = 5e5 + 10;
struct Node
{
int to, next;
}edge[maxN * 5 + 1];
int L, R, M, n, cnt, col;
int tot, head[maxN + 1];
int tl[maxN + 1], tr[maxN + 1];
int dl[maxN + 1], dr[maxN + 1];
int ans[maxN + 1], stk[maxN * 5 + 1], top;
bool vis[maxN * 5 + 1];
vector<pii> E[maxN * 2 + 1];
vector<int> vl[maxN * 2 + 1], vr[maxN * 2 + 1];
map<pii, int> G;
inline void clear(int node)
{
for(int i = 2; i <= tot; i++) vis[i] = false;
for(int i = 0; i < vl[node].size(); i++)
{
int x = vl[node][i];
dl[x] = head[x] = 0;
}
for(int i = 0; i < vr[node].size(); i++)
{
int x = vr[node][i] + n;
dr[x - n] = head[x] = 0;
}
head[2 * n + 1] = head[2 * n + 2] = 0;
tot = 1;
}
inline void add(int x, int y)
{
edge[++ tot] = (Node){y, head[x]}; head[x] = tot;
edge[++ tot] = (Node){x, head[y]}; head[y] = tot;
}
inline void dfs(int u)
{
for(int &i = head[u]; i; i = edge[i].next)
{
if(vis[i]) continue;
vis[i] = vis[i ^ 1] = true;
dfs(edge[i].to);
}
stk[++ top] = u;
}
inline void solve(int node)
{
for(int i = 0; i < E[node].size(); i++)
{
int u = E[node][i].first, v = E[node][i].second;
add(u, v + n);
dl[u] ++, dr[v] ++;
}
bool flag = true;
for(int i = 0; i < vl[node].size(); i++)
if(dl[ vl[node][i] ] > 1) { flag = false; break; }
for(int i = 0; i < vr[node].size(); i++)
if(dr[ vr[node][i] ] > 1) { flag = false; break; }
if(flag)
{
col ++;
for(int i = 0; i < E[node].size(); i++) ans[ G[ E[node][i] ] ] = col;
clear(node);
return;
};
int d1 = 0, d2 = 0;
for(int i = 0; i < vl[node].size(); i++)
if(dl[ vl[node][i] ] & 1) add(vl[node][i], 2 * n + 2), d2 ++;
for(int i = 0; i < vr[node].size(); i++)
if(dr[ vr[node][i] ] & 1) add(2 * n + 1, vr[node][i] + n), d1 ++;
if(d1 & 1) add(2 * n + 1, 2 * n + 2);
int nl = ++ cnt, nr = ++ cnt;
for(int i = 0; i < vl[node].size(); i++)
{
top = 0;
dfs(vl[node][i]);
while(top > 1)
{
int u = stk[top], v = stk[top - 1];
top --;
if(u > 2 * n || v > 2 * n) continue;
if(u > n) swap(u, v);
v -= n;
if(top & 1) E[nl].push_back( pii(u, v) );
else E[nr].push_back( pii(u, v) );
}
}
clear(node);
for(int i = 0; i < E[nl].size(); i++)
tl[ E[nl][i].first ] = tr[ E[nl][i].second ] = nl;
for(int i = 0; i < vl[node].size(); i++)
if(tl[ vl[node][i] ] == nl) vl[nl].push_back(vl[node][i]);
for(int i = 0; i < vr[node].size(); i++)
if(tr[ vr[node][i] ] == nl) vr[nl].push_back(vr[node][i]);
for(int i = 0; i < E[nr].size(); i++)
tl[ E[nr][i].first ] = tr[ E[nr][i].second ] = nr;
for(int i = 0; i < vl[node].size(); i++)
if(tl[ vl[node][i] ] == nr) vl[nr].push_back(vl[node][i]);
for(int i = 0; i < vr[node].size(); i++)
if(tr[ vr[node][i] ] == nr) vr[nr].push_back(vr[node][i]);
solve(nl), solve(nr);
}
int main()
{
scanf("%d %d %d", &L, &R, &M);
n = max(L, R);
cnt ++;
for(int i = 1; i <= M; i++)
{
int x, y;
scanf("%d %d", &x, &y);
G[ pii(x, y) ] = i;
E[cnt].push_back( pii(x, y) );
dl[x] ++, dr[y] ++;
}
for(int i = 1; i <= L; i++)
if(dl[i]) vl[cnt].push_back(i);
for(int i = 1; i <= R; i++)
if(dr[i]) vr[cnt].push_back(i);
for(int i = 1; i <= L; i++) dl[i] = 0;
for(int i = 1; i <= R; i++) dr[i] = 0;
tot = 1;
solve(1);
printf("%d\n", col);
for(int i = 1; i <= M; i++) printf("%d\n", ans[i]);
return 0;
}
