#include <bits/stdc++.h>
#define sz(v) ((int)(v).size())
#define all(v) (v).begin(), (v).end()
#define cr(v, n) (v).clear(), (v).resize(n);
using namespace std;
using lint = long long;
using pi = array<int, 2>;
vector<int> split(int n, vector<pi> edges) {
if (sz(edges) == 0)
return {};
vector<vector<int>> gph(n);
vector<int> nxt(sz(edges) * 2), vis(sz(edges) * 2);
for (int i = 0; i < sz(edges); i++) {
auto [u, v] = edges[i];
v += n / 2;
gph[u].push_back(2 * i);
gph[v].push_back(2 * i + 1);
}
for (int i = 0; i < n; i++) {
for (int j = 0; j < sz(gph[i]); j += 2) {
nxt[gph[i][j]] = (gph[i][j + 1] ^ 1);
nxt[gph[i][j + 1]] = (gph[i][j] ^ 1);
}
}
vector<int> ans;
for (int i = 0; i < sz(edges) * 2; i++) {
if (!vis[i]) {
for (int j = i; !vis[j]; j = nxt[j]) {
ans.push_back(j);
vis[j] = vis[j ^ 1] = 1;
}
}
}
return ans;
}
vector<int> EdgeColoringRegular(int n, int k, vector<pi> edges) {
/*cerr << n << " " << k << " " << sz(edges) << endl;
for (auto &[u, v] : edges)
cout << u << " " << v << endl;*/
assert(k > 0);
if (k == 1) {
return vector<int>(sz(edges));
}
if (k % 2 == 0) {
auto decomp = split(2 * n, edges);
vector<pi> sub[2];
for (int i = 0; i < sz(decomp); i++) {
sub[i % 2].push_back(edges[decomp[i] / 2]);
}
vector<int> rec[2];
rec[0] = EdgeColoringRegular(n, k / 2, sub[0]);
rec[1] = EdgeColoringRegular(n, k / 2, sub[1]);
vector<int> ans(sz(edges));
for (int i = 0; i < sz(decomp); i++) {
ans[decomp[i] / 2] = rec[i % 2][i / 2] + (i % 2) * (k / 2);
}
return ans;
}
int t = 0;
while ((1 << t) < k * n)
t++;
vector<array<int, 4>> todnc;
int alph = (1 << t) / k;
int beta = (1 << t) - k * alph; // < k
for (int i = 0; i < sz(edges); i++) {
todnc.push_back({edges[i][0], edges[i][1] + n, alph, i});
}
if (beta > 0) {
for (int i = 0; i < n; i++) {
todnc.push_back({i, i + n, beta, -1});
}
}
for (int i = 0; i < t; i++) {
vector<pi> toeuler;
vector<array<int, 4>> sub[2];
for (auto &[u, v, k, idx] : todnc) {
if (k % 2)
toeuler.push_back({u, v - n});
}
sub[1] = sub[0];
auto pth = split(2 * n, toeuler);
vector<int> parity(sz(toeuler));
for (int i = 1; i < sz(pth); i += 2)
parity[pth[i] / 2] = 1;
int ptr = 0, bal = 0;
for (auto &[u, v, k, idx] : todnc) {
int l = k / 2, r = k / 2;
if (k % 2) {
if (parity[ptr++])
r++;
else
l++;
}
if (idx == -1)
bal += l - r;
if (l)
sub[0].push_back({u, v, l, idx});
if (r)
sub[1].push_back({u, v, r, idx});
}
if (bal >= 0)
todnc = sub[1];
else
todnc = sub[0];
}
vector<int> ans(sz(edges), -1);
for (auto &[u, v, z, idx] : todnc) {
assert(z == 1 && idx != -1);
ans[idx] = k - 1;
}
vector<pi> sub;
for (int i = 0; i < sz(edges); i++) {
if (ans[i] == -1)
sub.push_back(edges[i]);
}
int piv = 0;
auto sol = EdgeColoringRegular(n, k - 1, sub);
for (int i = 0; i < sz(edges); i++) {
if (ans[i] == -1)
ans[i] = sol[piv++];
}
return ans;
}
vector<int> EdgeColoring(int l, int r, vector<pi> edges) {
if (sz(edges) == 0)
return vector<int>();
vector<int> d[2];
cr(d[0], l);
cr(d[1], r);
for (auto &[x, y] : edges)
d[0][x]++, d[1][y]++;
int k = max(*max_element(all(d[0])), *max_element(all(d[1])));
for (int i = 0; i < 2; i++) {
vector<int> ord(l);
iota(all(ord), 0);
sort(all(ord), [&](int x, int y) { return d[i][x] < d[i][y]; });
vector<int> maps(l);
int nl = 0;
for (int j = 0; j < sz(ord);) {
int nxt = j, sum = 0;
while (nxt < sz(ord) && sum + d[i][ord[nxt]] <= k) {
sum += d[i][ord[nxt]];
maps[ord[nxt]] = nl;
nxt++;
}
nl++;
j = nxt;
}
for (auto &e : edges) {
e[i] = maps[e[i]];
}
l = nl;
swap(l, r);
}
int n = max(l, r);
cr(d[0], n);
cr(d[1], n);
for (auto &[x, y] : edges)
d[0][x]++, d[1][y]++;
int j = 0;
int orig = sz(edges);
for (int i = 0; i < n; i++) {
while (d[0][i] < k) {
while (d[1][j] == k)
j++;
edges.push_back({i, j});
d[0][i]++;
d[1][j]++;
}
}
auto sol = EdgeColoringRegular(n, k, edges);
sol.resize(orig);
return sol;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
int l, r, m;
cin >> l >> r >> m;
vector<pi> edges(m);
for (auto &[x, y] : edges)
cin >> x >> y, x--, y--;
auto ed = EdgeColoring(l, r, edges);
cout << *max_element(all(ed)) + 1 << "\n";
for (auto &x : ed)
cout << x + 1 << "\n";
}
