{"problem":{"name":"[COCI 2021/2022 #5] Usmjeravanje","description":{"content":"永无岛有两条河流。每条河流沿岸分布有若干个城市，其中城市数量分别为 $a,b$。 对于位于同一条河流沿岸的 $i,j$ 两个城市，如果 $i \\lt j$，那么可以通过水路从城市 $i$ 到城市 $j$。 永无岛的居民们已经决定修建 $m$ 条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线，但方向有待商榷。 当两个城市之间可以通过水路或航线互相到达时，则称它们是","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":{"LuoguStyle":"P6"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8328"},"statements":[{"statement_type":"Markdown","content":"永无岛有两条河流。每条河流沿岸分布有若干个城市，其中城市数量分别为 $a,b$。\n\n对于位于同一条河流沿岸的 $i,j$ 两个城市，如果 $i \\lt j$，那么可以通过水路从城市 $i$ 到城市 $j$。\n\n永无岛的居民们已经决定修建 $m$ 条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线，但方向有待商榷。\n\n当两个城市之间可以通过水路或航线互相到达时，则称它们是连通的。在所有的城市中，存在若干个城市集合，使得集合中没有任何一对城市是连通的。请为每条航线选择一个方向，使得所有集合中包含元素最多的集合元素个数最少。\n\n## Input\n\n第一行两个正整数 $a,b$。\n\n第二行一个正整数 $m$。\n\n接下来的 $m$ 行，每行两个正整数 $x_i,y_i$，表示一条连接第一条河流的城市 $x_i$ 和第二条河流的城市 $y_i$ 的单向航线。数据保证没有重复的无序数对 $(x_i,y_i)$ 出现。\n\n## Output\n\n第一行一个正整数，表示最大集合元素个数的最小值。\n\n第二行 $m$ 个整数 $0$ 或 $1$。其中 $0$ 表示方向从第一条河流的城市 $x_i$ 到第二条河流的城市 $y_i$，$1$ 则相反。\n\n如果有多种符合题意的方案，输出任意一种。\n\n[samples]\n\n## Note\n\n**【样例 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。**","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8328","tags":["2021","Special Judge","COCI（克罗地亚）"],"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"]],"created_at":"2026-03-03 11:09:25"}}