#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];
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);
if(akt.c <= ro)
{
int ko = 0;
if(v < akt.v) ko = 1;
F[ko].pb({v,akt.v,akt.c});
}
//cout << "V: " << v << " AKT: " << akt.v << " C: " << akt.c << " KOL: " << kol << '\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)E.size()-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});
}
rep(i,2) F[i].clear();
for(int i = 0; i <= nr; ++i) vis[i] = 0;
for(auto v : V)
{
//cout << '\n';
DFS(v);
//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;
}
