graphs *2800

Please click on ads to support us..

Python Code:

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 = ' ')

    
    

C++ Code:

// 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...
*/


Comments

Submit
0 Comments
More Questions

1618C - Paint the Array
469A - I Wanna Be the Guy
1294A - Collecting Coins
1227A - Math Problem
349A - Cinema Line
47A - Triangular numbers
1516B - AGAGA XOOORRR
1515A - Phoenix and Gold
1515B - Phoenix and Puzzle
155A - I_love_username
49A - Sleuth
1541A - Pretty Permutations
1632C - Strange Test
673A - Bear and Game
276A - Lunch Rush
1205A - Almost Equal
1020B - Badge
1353A - Most Unstable Array
770A - New Password
1646B - Quality vs Quantity
80A - Panoramix's Prediction
1354B - Ternary String
122B - Lucky Substring
266B - Queue at the School
1490A - Dense Array
1650B - DIV + MOD
1549B - Gregor and the Pawn Game
553A - Kyoya and Colored Balls
1364A - XXXXX
1499B - Binary Removals