P8328 [COCI 2021/2022 #5] Usmjeravanje

永无岛有两条河流。每条河流沿岸分布有若干个城市，其中城市数量分别为 $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$ 则相反。 如果有多种符合题意的方案，输出任意一种。

**【样例 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](https://www.luogu.com.cn/paste/uv2vgxxa)。如果对此有疑问或想要 hack，请[私信编写者](https://www.luogu.com.cn/chat?uid=137367)或发帖。 **【来源】[COCI 2021-2022#5](https://hsin.hr/coci/contest5_tasks.pdf) Task 5 Usmjeravanje。**