{"raw_statement":[{"iden":"statement","content":"永无岛有两条河流。每条河流沿岸分布有若干个城市，其中城市数量分别为 $a,b$。\n\n对于位于同一条河流沿岸的 $i,j$ 两个城市，如果 $i \\lt j$，那么可以通过水路从城市 $i$ 到城市 $j$。\n\n永无岛的居民们已经决定修建 $m$ 条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线，但方向有待商榷。\n\n当两个城市之间可以通过水路或航线互相到达时，则称它们是连通的。在所有的城市中，存在若干个城市集合，使得集合中没有任何一对城市是连通的。请为每条航线选择一个方向，使得所有集合中包含元素最多的集合元素个数最少。"},{"iden":"input","content":"第一行两个正整数 $a,b$。\n\n第二行一个正整数 $m$。\n\n接下来的 $m$ 行，每行两个正整数 $x_i,y_i$，表示一条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线。数据保证没有重复的无序数对 $(x_i,y_i)$ 出现。"},{"iden":"output","content":"第一行一个正整数，表示最大集合元素个数的最小值。\n\n第二行 $m$ 个整数 $0$ 或 $1$。其中 $0$ 表示方向从第一条河流的城市 $x_i$ 到第二条河流的城市 $y_i$，$1$ 则相反。\n\n如果有多种符合题意的方案，输出任意一种。"},{"iden":"note","content":"**【样例 1 解释】**\n\n最优的方案可以使得每对城市都连通，因此答案为 $1$。\n\n**【数据规模与约定】**\n\n**本题采用捆绑测试。**\n\n- Subtask 1（20 pts）：$1 \\le a,b,m \\le 15$。\n- Subtask 2（30 pts）：$1 \\le a,b \\le 1000$。\n- Subtask 3（60 pts）：无特殊限制。\n\n对于 $100\\%$ 的数据，$1 \\le a,b,m \\le 2 \\times 10^5$，$1 \\le x_i \\le a$，$1 \\le y_i \\le b$。\n\n**【说明】**\n\n本题采用自行编写的 [Special Judge](https://www.luogu.com.cn/paste/uv2vgxxa)。如果对此有疑问或想要 hack，请[私信编写者](https://www.luogu.com.cn/chat?uid=137367)或发帖。\n\n**【来源】[COCI 2021-2022#5](https://hsin.hr/coci/contest5_tasks.pdf) Task 5 Usmjeravanje。**"}],"translated_statement":null,"sample_group":[["5 3\n4\n1 2\n2 3\n3 1\n5 3","1\n1 1 0 0"],["6 6\n4\n1 2\n3 2\n4 3\n5 6","9\n1 0 1 1"],["8 7\n7\n1 3\n2 1\n3 4\n5 6\n6 5\n6 7\n8 7","5\n1 0 1 1 0 1 0"]],"show_order":[],"formal_statement":null,"simple_statement":null,"has_page_source":false}