#include <cmath>
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>

using namespace std;

typedef long long ll;

mt19937 rnd(219);

struct edge
{
    int a, b;
};

const int N = 1e6 + 7;

vector <int> g[N];
int col[N];
vector <edge> glob_edges;
bool vis[N];
bool us[N];
int pp;

void dfs(int v)
{
    us[v] = true;
    while (g[v].size() > 0)
    {
        int ind = g[v].back();
        g[v].pop_back();
        if (vis[ind])
        {
            continue;
        }
        vis[ind] = true;
        col[ind] = (pp ^= 1);
        dfs(glob_edges[ind].a == v ? glob_edges[ind].b : glob_edges[ind].a);
    }
}

vector <int> solve(vector <edge> e)
{
    if (e.empty())
    {
        return {};
    }
    vector <int> l, r;
    for (auto c : e)
    {
        l.push_back(c.a);
        r.push_back(c.b);
    }
    sort(l.begin(), l.end());
    sort(r.begin(), r.end());
    l.resize(unique(l.begin(), l.end()) - l.begin());
    r.resize(unique(r.begin(), r.end()) - r.begin());
    glob_edges.clear();
    int x = (int) l.size() + 1, y = (int) r.size() + 1;
    for (int i = 0; i < x + y; i++) g[i].clear();
    int ind = 0;
    for (auto &c : e)
    {
        c.a = lower_bound(l.begin(), l.end(), c.a) - l.begin();
        c.b = lower_bound(r.begin(), r.end(), c.b) - r.begin();
        auto ret = c;
        ret.b += x;
        glob_edges.push_back(ret);
        g[ret.a].push_back(ind);
        g[ret.b].push_back(ind);
        ind++;
    }
    vector <int> ids;
    int mx = 0;
    for (int i = 0; i < x + y; i++)
    {
        us[i] = 0;
        mx = max(mx, (int) g[i].size());
        if (g[i].size() % 2)
        {
            ids.push_back(i);
        }
    }
    bool bad = false;
    for (int i = 0; i < x + y; i++)
    {
        if (g[i].size() > 1)
        {
            bad = true;
        }
    }
    if (!bad)
    {
        vector <int> res(ind);
        return res;
    }
    else
    {
        vector <int> deg(x + y);
        for (int v : ids)
        {
            if (v < x)
            {
                glob_edges.push_back({v, x + y - 1});
                g[v].push_back(ind);
                g[x + y - 1].push_back(ind);
                ind++;
            }
            else
            {
                glob_edges.push_back({v, x - 1});
                g[v].push_back(ind);
                g[x - 1].push_back(ind);
                ind++;
            }
        }
        if (g[x - 1].size() % 2)
        {
            glob_edges.push_back({x - 1, x + y - 1});
            g[x - 1].push_back(ind);
            g[x + y - 1].push_back(ind);
            ind++;
        }
        for (int i = 0; i < ind; i++)
        {
            col[i] = -1;
        }
        for (int i = 0; i < ind; i++)
        {
            vis[i] = 0;
        }
        for (int i = 0; i < x + y; i++)
        {
            if (!g[i].empty())
            {
                dfs(i);
            }
        }
        vector <edge> to_l, to_r;
        vector <int> cols;
        for (int i = 0; i < (int) e.size(); i++)
        {
            cols.push_back(col[i]);
            if (col[i] == 0)
            {
                to_l.push_back(e[i]);
            }
            else
            {
                to_r.push_back(e[i]);
            }
        }
        auto x = solve(to_l);
        auto y = solve(to_r);
        int mx = *max_element(x.begin(), x.end()) + 1;
        int p_x = 0, p_y = 0;
        vector <int> ans;
        for (int i = 0; i < (int) e.size(); i++)
        {
            if (cols[i] == 0)
            {
                ans.push_back(x[p_x++]);
            }
            else
            {
                ans.push_back(mx + y[p_y++]);
            }
        }
        return ans;
    }
}

set <int> a[N];

int main()
{
#ifdef ONPC
    freopen("a.in", "r", stdin);
#endif
    ios::sync_with_stdio(0);
    cin.tie(0);
#ifdef ONPC
    while (true)
    {
        vector <edge> e;
        int l = rnd() % 100 + 1, r = rnd() % 100 + 1, m = rnd() % (l * r) + 1;
        //int l = 100000, r = 100000, m = 500000;
        set <pair <int, int> > q;
        for (int i = 0; i < m; i++)
        {
            int a = rnd() % l + 1, b = rnd() % r + 1;
            while (q.count({a, b}))
            {
                a = rnd() % l + 1;
                b = rnd() % r + 1;
            }
            q.insert({a, b});
            a--, b--;
            e.push_back({a, b});
        }
        for (int i = 0; i < l + r; i++) a[i].clear();
        auto ret = solve(e);
        int mx = 0;
        for (int i = 0; i < m; i++)
        {
            assert(!a[e[i].a].count(ret[i]));
            assert(!a[l + e[i].b].count(ret[i]));
            a[e[i].a].insert(ret[i]);
            a[l + e[i].b].insert(ret[i]);
            mx = max(mx, (int) a[e[i].a].size());
            mx = max(mx, (int) a[l + e[i].b].size());
        }
        int cur = 1;
        while (cur < mx)
        {
            cur *= 2;
        }
        cout << *max_element(ret.begin(), ret.end()) + 1 << ' ' << cur << ' ' << mx << endl;
        assert(*max_element(ret.begin(), ret.end()) + 1 <= cur);
        cout << "OK" << endl;
        return 0;
    }
#else
    vector <edge> e;
    int l, r, m;
    cin >> l >> r >> m;
    for (int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--, b--;
        e.push_back({a, b});
    }
    auto ret = solve(e);
    cout << *max_element(ret.begin(), ret.end()) + 1 << '\n';
    for (int c : ret)
    {
        cout << c + 1 << '\n';
    }
#endif
}