Description

A communication network contains several nodes and several undirected communication lines that directly connect these nodes. The given network is connected, that is: for any pair of nodes, there exists a communication path formed by connecting (several) communication lines end to end.

Some nodes provide service of type $A$ to all nodes (including themselves), and some nodes provide service of type $B$ to all nodes (including themselves). A node may provide both types of services. Every node must be able to access both services.

When a communication line breaks, it may happen that some node cannot access a certain service. (That is, there exist a node and a service type such that there is no node that provides this service type and is connected to that node.) We call any communication line that can cause such a situation a critical communication line.

Your task is to write a program to compute how many critical communication lines there are, and output the two endpoints of each critical communication line.

Input Format

The first line contains four integers $N,M,K,L$. Here, $N \; (1 \le N \le 10^5)$ is the number of nodes in the network, $M \; (1 \le M \le 10^6)$ is the number of communication lines, $K \; (1 \le K \le N)$ is the number of nodes that provide service type $A$, and $L \; (1 \le L \le N)$ is the number of nodes that provide service type $B$. The nodes are numbered from $1$ to $N$.

The second line contains $K$ integers, which are the node indices that provide service type $A$.

The third line contains $L$ integers, which are the node indices that provide service type $B$.

The next $M$ lines each contain two integers $p,q \; (1 \le p,q \le N,p \neq q)$, representing the indices of the two endpoints of a communication line. It is guaranteed that between any two nodes there is at most one communication line.

Output Format

The first line contains an integer $S$, the number of critical communication lines.

The next $S$ lines each contain two integers $p,q$, indicating the two endpoints of a critical communication line.

The order of the critical communication lines can be arbitrary, and the order of the two endpoints for each critical communication line can also be arbitrary.

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

Hint

This problem is CEOI2005 D2T2. For the original statement, see: Critical Network Lines.

Thanks to

Translated by ChatGPT 5