Critical Communication Lines

A communication network consists of several nodes and several bidirectional communication lines connecting nodes directly. It is known that the network is connected, i.e. for any two nodes there exists a communication path (a series of communication lines) between them.

Some nodes provide service of type \(A\) to all nodes (including itself), and some nodes provide service of type \(B\) to all nodes (including itself). Note that a node may provide both services. Every node must have access to both services.

When a communication line fails (is removed), it is possible that there will be a node which cannot access one of the services. In other words, there exists a node and a service type such that there is no node providing that service in the connected component containing that node. Such a communication line is called a critical communication line.

Your task is to count the number of critical communication lines and output the endpoints of each critical communication line.

Input Format

inputFormat

The first line contains two integers \(n\) and \(m\), denoting the number of nodes and communication lines respectively. Nodes are numbered from 1 to \(n\).

The second line contains \(n\) space-separated integers, each being either 0 or 1. The \(i\)th integer is 1 if node \(i\) provides service \(A\) and 0 otherwise.

The third line contains \(n\) space-separated integers, each being either 0 or 1. The \(i\)th integer is 1 if node \(i\) provides service \(B\) and 0 otherwise.

Each of the next \(m\) lines contains two integers \(u\) and \(v\) (1 ≤ \(u, v\) ≤ \(n\)), which denote that there is a bidirectional communication line connecting nodes \(u\) and \(v\>.

outputFormat

On the first line, output a single integer \(k\), the number of critical communication lines.

Then output \(k\) lines, each containing two integers \(u\) and \(v\) that denote the endpoints of a critical communication line. You may output the endpoints in any order.

sample

4 3
1 0 1 1
0 1 0 1
1 2
2 3
3 4

1
1 2