你正在协助当地社区监控协会建立街道监控系统，以查明近期几起不幸的“狗屎事件”背后的罪魁祸首。

该系统由放置在街道电话线上的监听设备组成（其想法是，狗屎肇事者迟早会露出马脚，并在电话中讨论他们的卑劣行径）。每个监听设备都放置在连接房屋的电话线之一上，并将拦截所有沿该电话线路由的通话。

电话线网络结构如下：街道的一侧是奇数编号的房屋，另一侧是偶数编号的房屋。房屋编号排列方式使得奇数编号的房屋 $i$ 正对着街道另一侧的偶数编号房屋 $i + 1$。在街道的两侧，相邻的房屋对之间都有直接的电话线。此外，还有两条直接的电话线连接街道的两侧。这两条电话线中的每一条都连接着正对着的一对房屋。

同一侧房屋之间的通话沿两座房屋之间的直接路径路由，不会经过街道的另一侧。对于街道两侧房屋之间的通话，我们已知该通话将使用哪两条跨越街道的直接连接之一。

根据之前的调查，我们知道街道上哪些人之间有通话往来。我们希望以这样一种方式放置监听设备，以便能够拦截所有通话。换句话说，对于每一对有通话往来的人，在他们房屋之间的路由路径上必须至少有一个监听设备。

你的任务是找到一种使用最少数量监听设备的方法（因为它们很贵，而且我们上周把大部分预算都花在烧烤上了）。

图 I.1：样例输入 1 中的电话线网络示意图。共有 14 座房屋，每侧 7 座。两条跨越街道的直接连接分别连接房屋 3 与房屋 4，以及房屋 9 与房屋 10。房屋 7 和 11 的住户有通话往来，通话经由房屋 9 路由。房屋 5 和 6 的住户也有通话往来，通话经由房屋 7、9、10 和 8 路由。样例输入 2 与此类似，但其中房屋 5 和 6 之间的通话改由房屋 3 和 4 之间的直接连接路由。

输入格式

输入的第一行包含四个整数 $n, m, c_1$ 和 $c_2$ ($4 \le n \le 250\,000, 1 \le m \le 500\,000, 1 \le c_1 < c_2 < n$)，其中 $n$ 为偶数，表示街道上的房屋总数；$m$ 表示有通话往来的人数对；$c_1$ 和 $c_2$ 为奇数，表示两条跨越街道的线路分别连接房屋 $c_1$ 与 $c_1 + 1$，以及房屋 $c_2$ 与 $c_2 + 1$。

接下来 $m$ 行，每行以两个 $1$ 到 $n$ 之间的不同整数 $a$ 和 $b$ 开头，表示房屋 $a$ 的住户与房屋 $b$ 的住户有通话往来。如果房屋位于街道两侧，则后面会跟一个整数 $c \in \{c_1, c_2\}$，表示 $a$ 和 $b$ 之间的通话沿连接 $c$ 与 $c + 1$ 的直接线路路由。每对 $\{a, b\}$ 在输入中最多出现一次。

输出格式

输出一行一个整数 $\ell$，表示所需监听设备的最小数量。 随后输出 $\ell$ 行，每行包含一对整数，描述应在哪些房屋对之间放置监听设备（当然，这些房屋对必须由电话线直接连接）。如果存在多个最优解，你可以输出其中任意一个。

样例

样例输入 1

14 2 3 9
7 11
5 6 9

样例输出 1

1
7 9

样例输入 2

14 2 3 9
7 11
5 6 3

样例输出 2

2
3 4
7 9