题目描述

范洙主持了一档动物电视节目，共有 $n$ 只狗和 $m$ 只猫参加。

所有狗从 $1$ 到 $n$ 编号，所有猫从 $1$ 到 $m$ 编号。对于每一对狗 $i$ 和猫 $j$，它们之间的关系恰好为以下三种之一：

• 相爱；
• 讨厌；
• 互不关心。

这种关系是对称的。例如，如果狗 $i$ 喜欢、讨厌或不关心猫 $j$，那么猫 $j$ 对狗 $i$ 也具有相同的关系。

为了提高节目的收视率，范洙希望把当前的猫狗关系调整成更符合节目效果的目标状态。他可以进行以下两种操作：

1. 选择一只狗 $x$，以及两只编号相邻的猫 $y,y+1$，其中

   $$1\le x\le n,\qquad 1\le y<m.$$

   如果狗 $x$ 与猫 $y$、猫 $y+1$ 的关系相同，并且这两种关系均不是“互不关心”，则同时翻转这两对关系：

   • 若原来都相爱，则变为都讨厌；
   • 若原来都讨厌，则变为都相爱。

2. 选择一只猫 $y$，以及两只编号相邻的狗 $x,x+1$，其中

   $$1\le y\le m,\qquad 1\le x<n.$$

   如果猫 $y$ 与狗 $x$、狗 $x+1$ 的关系相同，并且这两种关系均不是“互不关心”，则同时翻转这两对关系：

   • 若原来都相爱，则变为都讨厌；
   • 若原来都讨厌，则变为都相爱。

请判断能否通过若干次操作把当前状态变为目标状态。

若可以做到，请求出所需操作次数的最小值，并输出一种达到该最小值的操作序列。

输入格式

第一行包含两个整数 $n,m$，分别表示狗和猫的数量。

接下来依次给出当前状态和目标状态。每个状态均按以下格式给出：

• 第一行包含两个整数 $l,h$，分别表示处于“相爱”关系和“讨厌”关系的猫狗对数量；

  $$1\le l+h\le 500$$

• 接下来 $l$ 行，每行包含两个整数 $d,c$，表示狗 $d$ 与猫 $c$ 相爱；

• 再接下来 $h$ 行，每行包含两个整数 $d,c$，表示狗 $d$ 与猫 $c$ 互相讨厌。

其中：

在同一个状态中，给出的 $l+h$ 对 $(d,c)$ 两两不同。

没有在这 $l+h$ 行中出现的猫狗对，其关系均为“互不关心”。

换言之，完整输入顺序为：

1. $n,m$；
2. 当前状态的 $l_1,h_1$ 及对应关系；
3. 目标状态的 $l_2,h_2$ 及对应关系。

输出格式

如果无法把当前状态变为目标状态，只输出一行：

-1

否则，第一行输出最少操作次数 $k$。

接下来输出 $k$ 行，按照实际执行顺序描述每次操作：

• 若选择狗 $x$ 以及猫 $y,y+1$，输出：

  0 x y
  

• 若选择猫 $y$ 以及狗 $x,x+1$，输出：

  1 y x
  

只要操作次数为最小值，并且操作序列合法且能得到目标状态，任意一种方案都会被接受。

样例输入

3 4
3 4
1 2
1 3
1 4
2 3
2 4
3 3
3 4
1 6
2 3
1 4
1 3
1 2
2 4
3 3
3 4

样例输出

3
0 1 2
1 3 1
0 1 3