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

有一个有 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 行，每行输出两个数，这两个数只有可能是 0 或 1 ，分别代表编号为 i 的点在 X 图，Y 图的情况： 0 表示无颜色， 1 表示有颜色。

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

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

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

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

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