UOJ Logo Universal Online Judge

UOJ

#78. 二分图最大匹配

统计

从前一个和谐的班级,有 $n_l$ 个是男生,有 $n_r$ 个是女生。编号分别为 $1, \dots, n_l$ 和 $1, \dots, n_r$。

有若干个这样的条件:第 $v$ 个男生和第 $u$ 个女生愿意结为配偶。

请问这个班级里最多产生多少对配偶?

输入格式

第一行三个正整数,$n_l, n_r, m$。

接下来 $m$ 行,每行两个整数 $v, u$ 表示第 $v$ 个男生和第 $u$ 个女生愿意结为配偶。保证 $1 \leq v \leq n_l$,$1 \leq u \leq n_r$,保证同一个条件不会出现两次。

输出格式

第一行一个整数,表示最多产生多少对配偶。

接下来一行 $n_l$ 个整数,描述一组最优方案。第 $v$ 个整数表示 $v$ 号男生的配偶的编号。如果 $v$ 号男生没配偶请输出 $0$。

样例一

input

2 2 3
1 1
1 2
2 1

output

2
2 1

explanation

$1$ 号男生跟 $2$ 号女生幸福地生活在了一起~

$2$ 号男生跟 $1$ 号女生幸福地生活在了一起~

样例二

input

2 2 2
1 1
2 1

output

1
1 0

explanation

班上一个女神一个女汉子,两个男生都去追女神。一种最优方案是:

$1$ 号男生跟 $1$ 号女生幸福地生活在了一起~

$2$ 号男生孤独终生。= =||

限制与约定

$1 \leq n_l, n_r \leq 500$,$1 \leq m \leq 250000$。

时间限制:$1\texttt{s}$

空间限制:$256\texttt{MB}$

下载

样例数据下载