题目描述

你正在帮助社区监控协会在街区里布置监听设备，用来找出最近一些“不幸狗便事件”的罪魁祸首。

街道两侧各有一排房子：

• 一侧是奇数编号房屋；
• 另一侧是偶数编号房屋；
• 奇数房屋 $i$ 的正对面是偶数房屋 $i+1$。

同一侧街道上，相邻编号的房屋之间有电话线。例如奇数侧有 $1-3,3-5,\ldots$，偶数侧有 $2-4,4-6,\ldots$。

此外，还有两条跨街电话线。它们分别连接房屋 $c_1$ 与 $c_1+1$，以及房屋 $c_2$ 与 $c_2+1$，其中 $c_1,c_2$ 都是奇数。

通话路线规则如下：

1. 如果两座房子在街道同一侧，电话会沿同一侧的唯一路径传输，不会跨到另一侧；
2. 如果两座房子在街道两侧，输入会告诉你它们的通话使用哪一条跨街电话线，即经过 $c_1-c_1+1$ 或 $c_2-c_2+1$。

你知道哪些房屋中的人互相有通话关系。现在希望在若干条电话线上放置监听设备，使得每一对有通话关系的人，其通话路径上至少有一条电话线被监听。

请用最少的监听设备完成这个任务，并输出一种最优方案。

下图是样例中的电话网络示意。

输入格式

第一行包含四个整数 $n,m,c_1,c_2$：

• $n$ 表示房屋数量；
• $m$ 表示互相有通话关系的房屋对数；
• $c_1,c_2$ 表示两条跨街电话线分别为 $(c_1,c_1+1)$ 和 $(c_2,c_2+1)$。

数据保证：

• $4\le n\le 250000$；
• $n$ 为偶数；
• $1\le m\le 500000$；
• $1\le c_1<c_2<n$；
• $c_1,c_2$ 均为奇数。

接下来 $m$ 行，每行描述一对有通话关系的房屋。

• 若两座房屋在同一侧，则该行包含两个整数 $a,b$；
• 若两座房屋在街道两侧，则该行包含三个整数 $a,b,c$，其中 $c\in\{c_1,c_2\}$，表示该通话会使用跨街电话线 $(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