2021 软件学院 ACM 集训队筛选赛

Problem C. 凝光的游戏

凝光因为群玉阁被炸飞后可以安心摸鱼,就在无聊时创造了一个小游戏,请你来玩。

有一个有 n 个点的没有重边、自环的无向图,图中的点有有颜色和没颜色两种状态。没有颜色的点会显示一个数字,表明与其相连的点中有多少个是有颜色的。

现在给你两个这种图, X 图和 Y 图,两个图的形状一样,仅每个点的颜色有可能不同。

你最多进行 \lfloor n/2 \rfloor (下取整)次操作,每次操作你可以将 Y 图的一个有颜色点变成无颜色点,或者将 Y 图的一个无颜色点变成有颜色点,然后使得 Y 图上无颜色点的数字和等于 X 图上无颜色点的数字和。

输入

第一行输出两个数:n,m ,分别表示图的点和边的数量 (2 \leq n \leq 10^5, 1 \leq m \leq 3 \times 10^5)

之后有 n 行。对于这 n 行中的第 i 行,每行输出两个数,这两个数只有可能是 01 ,分别代表编号为 i 的点在 X 图,Y 图的情况: 0 表示无颜色, 1 表示有颜色。

接下来有 m 行来描述图的形状。每行输出两个数:u,v ,代表编号为这两个数的两个点之间相连。

输出

如果 \lfloor n/2 \rfloor 次操作内,不可能使得 Y 图数字和等于 X 图数字和,输出 -1

否则先输出一行要执行的操作数 k

然后输出 k 行数,每行代表一次操作:改变 Y 图编号为该数的点的颜色状态。

如果有多种方案,输出任意一种即可。

样例

标准输入 复制文本
3 1
0 1
1 1
1 0
1 2
标准输出 复制文本
1
2

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 8
通过 6

A B C D E F G H

现在已经封榜。
因为过题情况不理想,所以给点提示:A、E、F题是模板题,不知道对应模板的同学可以尝试其他题目。
F题的输出描述更准确了
B题测试样例出错,已修改
F题测试样例格式出错,已修改