from collections import *
from itertools import *
from functools import *
from bisect import *
from heapq import *
import math
import sys
import struct
IN = lambda: sys.stdin.readline().rstrip("\r\n")
PN = lambda x: sys.stdout.write(x)
I = lambda: int(IN())
S = lambda: IN().split()
M = lambda: map(int, IN().split())
L = lambda: list(map(int, IN().split()))
G = lambda: map(lambda x: int(x) - 1, IN().split())
def array(shape, value = 0):
if len(shape) == 0:
return value
else:
return [array(shape[1:], value = value) for _ in range(shape[0])]
mod = 1000000007
def qpow(a, b, p = mod):
res = 1
while b:
if b & 1:
res = res * a % p
a = a * a % p
b >>= 1
return res
mod = 998244353
class Comb:
def __init__(self, n, p = mod):
self.__fac = [0 for _ in range(n + 1)]
self.__ifac = [0 for _ in range(n + 1)]
self.__fac[0] = 1
self.__mod = p
for i in range(1, n + 1):
self.__fac[i] = i * self.__fac[i - 1] % self.__mod
self.__ifac[n] = qpow(self.__fac[n], mod - 2)
for i in range(n - 1, -1, -1):
self.__ifac[i] = (i + 1) * self.__ifac[i + 1] % self.__mod
def binom(self, a, b):
if a < b or b < 0:
return 0
return self.__fac[a] * self.__ifac[b] * self.__ifac[a - b] % self.__mod
def fac(self, n):
return self.__fac[n]
def ifac(self, n):
return self.__ifac[n]
a, b, m = M()
n = a + b
e = [0 for _ in range(m + 1)]
deg = [0 for _ in range(n + 1)]
for i in range(1, m + 1):
u, v = M()
v += a
e[i] = (u, v)
deg[u] += 1
deg[v] += 1
ans = max(deg)
match = [[0 for _ in range(n + 1)] for __ in range(n + 1)]
for i in range(1, m + 1):
c1, c2 = 1, 1
u, v = e[i]
while match[u][c1]:
c1 += 1
while match[v][c2]:
c2 += 1
match[u][c1] = v
match[v][c2] = u
if c1 == c2:
continue
c0, w = c2, v
while w != 0:
match[w][c1], match[w][c2] = match[w][c2], match[w][c1]
w = match[w][c0]
c0 ^= c1 ^ c2
def getans(i):
u, v = e[i]
for j in range(1, ans + 1):
if match[v][j] == u:
return j
return -1
print(ans)
for i in range(1, m + 1):
print(getans(i), end = ' ')
// hiensumi: Maybe, success will come tomorrow. Thus, just keep trying! =) "Z/x
#include "bits/stdc++.h"
#define fod(i,a,b) for(int i = a;i <= b; i++)
#define fok(i,a,b) for(int i = a;i >= b; i--)
#define ll long long
#define int long long
#define fi first
#define se second
#define mask(i) (1LL<<(i))
#define BITpos(a,i) ((a >> i) & 1LL)
#define pb push_back
#define el '\n'
#define all(v) v.begin(), v.end()
#define odd(i) (i & 1LL)
using namespace std;
typedef pair<int, int> ii;
const int MOD = 1e9 + 7;
inline void kill(){cerr << "\nTime: " << clock() << "ms\n"; cerr << "⏁⊑⟒ ⋔⍜⍜⋏ ⍙⏃⌇ ⌇⍜ ⏚⟒⏃⎍⏁⟟⎎⎍⌰ ⏁⊑⏃⏁ ⏁⊑⟒⍀⟒ ⍙⏃⌇ ⏃ ⋔⟟⍀⍀⍜⍀ ⟟⋏ ⏁⊑⟒ ⍜☊⟒⏃⋏.\n"; exit(0);}
inline void add(int &x, int y, int mod = MOD) { x += y; while (x >= mod) x -= mod; while (x < 0) x += mod;}
inline void mul(int &x, int y, int mod = MOD) { x = (x * 1LL * y) % mod;}
inline int bpow(int x, int y, int mod = MOD) { int ans = 1; while (y) { if (y & 1) mul(ans, x, mod); mul(x, x, mod); y >>= 1;} return ans;}
inline int bp(int a, int b){int res = 1; while (b > 0) {if (b & 1) res = res * a; a = a * a; b >>= 1; } return res;}
inline int Inv(int x, int mod = MOD) { return bpow(x, mod - 2, mod);}
inline int Div(int x, int y, int mod = MOD) { int tmp = x; mul(tmp, Inv(y, mod), mod); return tmp;}
template<class T> bool mini(T& a,T b){return (a>=b)?a=b,1:0;}
template<class T> bool maxi(T& a,T b){return (a<=b)?a=b,1:0;}
struct point{int x, y;};
struct edge{int u, v, c;};
//int find(int u){if (lab[u] < 0) return u; return lab[u] = find(lab[u]);}
//bool join(int u, int v){u = find(u);v = find(v);if(u == v) return 0;if(lab[u] > lab[v]) swap(u,v);lab[u] += lab[v];lab[v] = u; return 1;}
const ll INF = 1e18, base = 1e6 + 5, multitest = 0;
//"Life is a daring adventure or it is nothing at all." -Helen Keller...
//"Success isn't determined by how many times you win, but by how you play the week after you lose." -Pele...
#define name ""
#define ld long double
// remember to reset value for multitestcase
// she is your motivation!!!
void init(){
}
int a, b, m, match[base];
vector <int> g[base];
vector <ii> hn;
void inp(){
cin >> a >> b >> m;
fod(i,1,m){
int u, v; cin >> u >> v;
g[u].pb(v + a);
g[v+a].pb(u);
hn.pb(ii(u,v));
}
}
namespace sub_task1{
int ans[1005][1005], dd[base];
bool konig(int u, int cnt, int color){
if(dd[u] == cnt) return 0;
dd[u] = cnt;
for(int v : g[u]){
bool ch = u > a and g[match[v]].size() < color;
if(ch or match[v] == 0 or konig(match[v], cnt, color)){
if(ch) match[match[v]] = 0;
match[v] = u;
match[u] = v;
return 1;
}
}
return 0;
}
void solve(){
int res = 0;
fod(i,1,a+b) maxi(res, (int)g[i].size());
cout << res << el;
int cnt = 0;
fok(color, res, 1){
fod(i,1,a+b) match[i] = 0;
fod(i,1,a+b){
if(match[i] == 0 and g[i].size() == color){
konig(i,++cnt,color);
}
}
fod(u,1,a) if(match[u] != 0){
int v = match[u];
ans[u][v-a] = color;
g[u].erase(find(all(g[u]), v));
g[v].erase(find(all(g[v]), u));
}
}
for(auto [u,v] : hn){
cout << ans[u][v] << " ";
}
}
}
signed main(){
ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
if(fopen(name".inp", "r")){
freopen(name".inp", "r", stdin);
freopen(name".out", "w", stdout);
}
int Test = 1; if(multitest) cin >> Test;
init();
while(Test--){
inp();
sub_task1 :: solve();
}
kill();
}
/*
Trú mưa nơi gốc cây ngày xưa
Để nhìn em lần cuối trong mưa
Để nắm tay đưa em đi về
Chốn mộng mơ...
Có hôm mây gió chợt ca vang
Nụ cười em như nắng mùa thu sang
Làm lòng tôi xao xuyến mà lang thang
Nghĩ về em...
Mình tôi thao thức
mình tôi day dứt
Cớ sao em không về với tôi
Mình tôi thao thức
mình tôi day dứt
Cớ sao em không cười với tôi
Gió mang câu ca về nơi đây
gió mang câu ca về với đời em
Nắng mang câu thơ về nơi đây
chính em mang thơ về với tình ta ...
Chiếc radio của em
Và từng ly trà đá ly kem
Cùng hát lên câu ca êm đềm
giữa mùa yêu
Những bông hoa xanh ngoài hiên
Vào buổi chiều tràn nắng an nhiên
Ta ngồi bên cạnh nhau
ngắm mùa thu sang...
*/
2090. K Radius Subarray Averages | 2091. Removing Minimum and Maximum From Array |
6. Zigzag Conversion | 1612B - Special Permutation |
1481. Least Number of Unique Integers after K Removals | 1035. Uncrossed Lines |
328. Odd Even Linked List | 1219. Path with Maximum Gold |
1268. Search Suggestions System | 841. Keys and Rooms |
152. Maximum Product Subarray | 337. House Robber III |
869. Reordered Power of 2 | 1593C - Save More Mice |
1217. Minimum Cost to Move Chips to The Same Position | 347. Top K Frequent Elements |
1503. Last Moment Before All Ants Fall Out of a Plank | 430. Flatten a Multilevel Doubly Linked List |
1290. Convert Binary Number in a Linked List to Integer | 1525. Number of Good Ways to Split a String |
72. Edit Distance | 563. Binary Tree Tilt |
1306. Jump Game III | 236. Lowest Common Ancestor of a Binary Tree |
790. Domino and Tromino Tiling | 878. Nth Magical Number |
2099. Find Subsequence of Length K With the Largest Sum | 1608A - Find Array |
416. Partition Equal Subset Sum | 1446. Consecutive Characters |