問題
鳗鱼王国的北正君现在正在解答 Unagi 合成编程竞赛(简称:UTPC)中出题的如下问题。
兔子王国有 n 羽年轻的雄性兔子和 n 羽年轻的雌兔正在生活。每只兔子有 1~2n ,奇数号是公兔,偶数号是母兔。 m 一套 (a_1, b_1), ..., (a_m, b_m) 被给出,这些是 a_i 号(奇数)的雄性和 b_i 偶数编号的母兔表示正在交往中。 (一只兔子也可能与多只兔子交往。这在兔子世界是常识。) 兔子王国的公主最近因为被鳗鱼王国的王子拒绝而受到了打击,每当看到正在交往的配对时,她就会无缘无故地感到愤怒。 因此,她考虑通过驱逐几只兔子出境来消灭国内正在交往的配对。 当然,被驱逐的兔子尽量越少越好。 请找出这样的方法之一,并输出应当驱逐的兔子的编号序列。
精通离散数学的北真君瞬间就理解了,这是一个“二分图的最小顶点覆盖”问题。 据北真君说,这个问题可以通过如下方式解决。
- 将每只兔子视为图的顶点,从起点向每只公兔画容量为1的边,从每只母兔向终点画容量为1的边。
- 每对 (a_i,b_i) 关于 a_i 个顶点向第 b_i 个顶点连一条容量为1的边。
- 求从起点到终点的最大流量。
- 考虑移除有流量的边并将其换为反向的图(残余图),希望在该图上求得由无法从起点到达的雄性和可达的雌性组成的集合,作为所要求的最小解。
北正君瞬间实现了这个算法并提交,但却得到了 Wrong Answer 的判定。北正君怀疑道:“作为天才的我不可能在程序里埋下 bug,一定是出题方犯了什么错误。”然而,尽管存在多个最小解,他发现 UTPC 使用的名为 KMCoder 的裁判系统只能通过完全匹配来判断正误。北正君猜透了出题者的心思,认为只要回答多个可能解中按字典序最小的一个就行,但即便是天才的北正君也不知道如何求字典序最小顶点覆盖。让我们来帮北正君继续写他的程序吧。
※在本东京大学编程竞赛(UTPC)中使用的裁判系统 AtCoder,与 KMCoder 不同,可以在非完全匹配的情况下进行正确与否的判定。配点
300
入力
输入按以下格式给出。
n m a1 b1 f1 ... am bm fm
n, m, a_i, b_i 如文中所述,a_i是奇数,b_i是偶数。 f_i是由北正君的程序求出的最大流中,流向顶点 a_i 到顶点 b_i 的边的流量(0 或 1)。 虽然保证北正君求出的最大流确实是最大流,但如果实在无法相信的话,也可以自行求最大流。
制約
输入中的每个变量都满足以下约束。
- 1 \leq n,m \leq 105
出力
找出应被驱逐的兔子集合中字典序最小的集合,并在第一行输出该集合的大小 C ,续 C 接着按行输出兔子的编号,按从小到大的顺序依次输出。 但是,集合 X 的字典序小于集合 Y ,是指将每个编号按从小到大的顺序排列后 x_1,x_2,...,x_C 和 按字典顺序比较 y_1,y_2,...,y_C 时,定义为某个 k存在 i=1,2,...,k-1关于x_i=y_i和x_k\lt y_k。
入力例1
4 6 1 2 1 3 4 1 3 6 0 5 2 0 7 2 0 7 8 1
输入示例 1 的输出示例 路径
3 2 3 7
入力例2
4 8 1 2 1 1 4 0 3 4 1 3 6 0 5 2 0 5 6 1 5 8 0 7 8 1
输入示例 2 的输出示例
4 1 3 5 7
入力例3
2 2 1 4 1 3 2 1
输入示例 3 的输出示例
2 1 2