题目描述

永无岛有两条河流。每条河流沿岸分布有若干个城市，其中城市数量分别为 $a,b$。

对于位于同一条河流沿岸的 $i,j$ 两个城市，如果 $i \lt j$，那么可以通过水路从城市 $i$ 到城市 $j$。

永无岛的居民们已经决定修建 $m$ 条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线，但方向有待商榷。

当两个城市之间可以通过水路或航线互相到达时，则称它们是连通的。在所有的城市中，存在若干个城市集合，使得集合中没有任何一对城市是连通的。请为每条航线选择一个方向，使得所有集合中包含元素最多的集合元素个数最少。

输入格式

第一行两个正整数 $a,b$。

第二行一个正整数 $m$。

接下来的 $m$ 行，每行两个正整数 $x_i,y_i$，表示一条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线。数据保证没有重复的无序数对 $(x_i,y_i)$ 出现。

输出格式

第一行一个正整数，表示最大集合元素个数的最小值。

第二行 $m$ 个整数 $0$ 或 $1$。其中 $0$ 表示方向从第一条河流的城市 $x_i$ 到第二条河流的城市 $y_i$，$1$ 则相反。

如果有多种符合题意的方案，输出任意一种。

5 3
4
1 2
2 3
3 1
5 3

1
1 1 0 0

6 6
4
1 2
3 2
4 3
5 6

9
1 0 1 1

8 7
7
1 3
2 1
3 4
5 6
6 5
6 7
8 7

5
1 0 1 1 0 1 0

提示

【样例 1 解释】

最优的方案可以使得每对城市都连通，因此答案为 $1$。

【数据规模与约定】

本题采用捆绑测试。

• Subtask 1（20 pts）：$1 \le a,b,m \le 15$。
• Subtask 2（30 pts）：$1 \le a,b \le 1000$。
• Subtask 3（60 pts）：无特殊限制。

对于 $100\%$ 的数据，$1 \le a,b,m \le 2 \times 10^5$，$1 \le x_i \le a$，$1 \le y_i \le b$。

【说明】

本题采用自行编写的 Special Judge。如果对此有疑问或想要 hack，请私信编写者或发帖。

【来源】COCI 2021-2022#5 Task 5 Usmjeravanje。