#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define rep(a,b) for(int a = 0; a < (b); ++a)
#define all(t) t.begin(), t.end()
#define pb push_back
const int N = 5e5+5, INF = 2e9+54321;
const ll INF_L = (ll)2e18+54321;
struct Krawedz
{
int a,b,idx;
};
struct Kraw
{
int v,c;
};
int l,r,m,cnter,nr,kol,ro;
vector<Kraw> G[N];
int il[N];
bool uz[N];
bool vis[N];
int wyn[N];
bool vif[N];
vector<Krawedz> F[2];
vector<int> g[N];
vector<Krawedz> wie;
void DFS(int v)
{
while(!G[v].empty())
{
Kraw akt = G[v].back();
G[v].pop_back();
//cout << "V: " << v << " AKT V: " << akt.v << " AKT C: " << akt.c << '\n';
if(vis[akt.c]) continue;
vis[akt.c] = 1;
DFS(akt.v);
wie.pb({min(v,akt.v),max(v,akt.v),akt.c});
//cout << "V: " << v << " AKT: " << akt.v << " C: " << akt.c << " KOL: " << kol << '\n';
}
//cout << "XXX: " << v << '\n';
}
int xn = 0;
void DFS2(int v)
{
vif[v] = 1, ++xn;
for(auto x : g[v]) if(!vif[x]) DFS2(x);
}
void rek(vector<Krawedz> E)
{
if(E.empty()) return;
//cout << '\n';
//cout << "EDGES: " << '\n';
//for(auto x : E) cout << "A: " << x.a << " B: " << x.b << " IDX: " << x.idx << '\n';
//cout << '\n';
int ok = 0;
for(auto x : E) g[x.a].pb(x.b), g[x.b].pb(x.a);
for(auto x : E)
{
if(vif[x.a]) continue;
xn = 0;
DFS2(x.a);
if(xn == 2) ++ok;
}
for(auto x : E) g[x.a].clear(), g[x.b].clear(), vif[x.a] = 0, vif[x.b] = 0;
if(ok == (int)E.size())
{
++cnter;
for(auto x : E)
{
//cout << "IDXXXX: " << x.idx << " CNTER: " << cnter << '\n';
wyn[x.idx] = cnter;
}
return;
}
vector<int> V;
for(auto x : E)
{
++il[x.a], ++il[x.b], V.pb(x.a), V.pb(x.b);
}
for(auto x : E) G[x.a].pb({x.b,x.idx}), G[x.b].pb({x.a,x.idx});
nr = (int)m-1, ro = nr;
for(auto x : V)
{
if(uz[x]) continue;
uz[x] = 1;
if(il[x] % 2 == 1) G[0].pb({x,++nr}), G[x].pb({0,nr});
}
//for(int i = 0; i <= l+r; ++i)
//{
//cout << '\n';
//cout << "I: " << i << " KRAW" << '\n';
//for(auto x : G[i]) cout << "V: " << x.v << " C: " << x.c << '\n';
//cout << '\n';
//}
rep(i,2) F[i].clear();
for(int i = 0; i <= nr; ++i) vis[i] = 0;
for(auto v : V)
{
//cout << '\n';
wie.clear();
DFS(v);
if((int)wie.size() == 0) continue;
int at = -1;
if((int)wie.size() == 1) at = wie[0].a;
else if(wie[0].a == wie[1].a or wie[0].a == wie[1].b) at = wie[0].b;
else at = wie[0].a;
for(int i = 0; i < (int)wie.size(); ++i)
{
int ko = 0;
//cout << "AA: " << wie[i].a << " BB: " << wie[i].b << '\n';
if(wie[i].a != at)
{
if(at < wie[i].a) ko = 1;
//cout << "AT: " << at << " NOW: " << wie[i].a << " KO: " << ko << '\n';
if(at > 0 and wie[i].a > 0) F[ko].pb({at,wie[i].a,wie[i].idx});
at = wie[i].a;
}
else
{
if(at < wie[i].b) ko = 1;
//cout << "AT: " << at << " NOW: " << wie[i].b << " KO: " << ko << '\n';
if(at > 0 and wie[i].b > 0) F[ko].pb({at,wie[i].b,wie[i].idx});
at = wie[i].b;
}
}
//cout << '\n';
}
for(auto x : E) il[x.a] = 0, il[x.b] = 0, G[x.a].clear(), G[x.b].clear(), uz[x.a] = 0, uz[x.b] = 0;
G[0].clear();
vector<Krawedz> af = F[0], bf = F[1];
rek(af);
rek(bf);
}
void solve()
{
cin >> l >> r >> m;
vector<Krawedz> K;
rep(i,m)
{
int a,b;
cin >> a >> b;
K.pb({a,l+b,i});
}
rek(K);
//cout << "CNTER: " << cnter << '\n';
int re = 1;
for(int i = 1; i < cnter; i *= 2, re *= 2);
cout << re << '\n';
rep(i,m) cout << wyn[i] << '\n';
}
int main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);
int T = 1;
//cin >> T;
while(T--) solve();
return 0;
}
