题目描述

一个通信网络包含若干个节点，以及若干条直接连接这些节点的双向通信线路。已知所研究的通信网络是连通的，即：任意一对节点之间都存在（若干条通信线路首尾相接而成的）通信路径。

一些节点会向所有节点（包括它自己）提供 $A$ 类型服务，还有一些节点会向所有节点（包括它自己）提供 $B$ 类型服务。一个节点可能会同时提供两种类型的服务。每个节点都必须要访问这两种服务。

当一条通信线路断开时，可能会出现某个节点不能访问某种服务的情况。（即：存在某个节点以及某种服务，使得不存在任何提供该类型服务，且与该节点连通的节点）我们称会造成这种情况的通信线路为关键通信线路。

你的任务是，写一个程序计算有多少条关键通信线路，并求出每条关键通信线路所连接的两个端点。

输入格式

输入第一行包含四个整数 $N,M,K,L$。其中，$N \; (1 \le N \le 10^5)$ 表示通信网络的节点数，$M \; (1 \le M \le 10^6)$ 表示通信网络的通信线路数，$K \; (1 \le K \le N)$ 表示提供 $A$ 类型服务的节点数，$L \; (1 \le L \le N)$ 表示提供 $B$ 类型服务的节点数。节点编号为 $1$ 到 $N$。

第二行包含 $K$ 个整数，表示提供 $A$ 类型服务的节点编号。

第三行包含 $L$ 个整数，表示提供 $B$ 类型服务的节点编号。

接下来 $M$ 行，每行包含两个整数 $p,q \; (1 \le p,q \le N,p \neq q)$，表示一条通信线路的两个端点的编号。保证任意两个节点之间至多只有一条通信线路。

输出格式

输出第一行包含一个整数 $S$，表示关键通信线路的数量。

接下来 $S$ 行，每行包含两个整数 $p,q$，表示一条关键通信线路所连接的两个端点的编号。

关键通信线路的顺序任意，每一条关键通信线路所连接的两个端点的顺序也任意。

9 10 3 4
2 4 5
4 9 8 3
1 2
4 1
2 3
4 2
1 5
5 6
6 7
6 8
7 9
8 7

3
3 2
5 6
7 9

提示

本题为 CEOI2005 D2T2，原题面请见：Critical Network Lines。

感谢