Defense Planning Strategies

In country A there are \(n\) important strategic bases. Some pairs of bases are connected by bidirectional roads. For each road, country A can decide either to deploy troops (denoted by \(T\)) or not (denoted by \(U\)); additionally, it may choose to perform a scorched earth operation (denoted by \(S\)) on a road. Performing scorched earth on a road prevents enemy country B from using that road in its operations, but also prohibits deployment of troops on that road.

The enemy country B has \(k\) possible combat plans. In the \(i\)th plan, B will attack the transportation line between base \(p_i\) and base \(q_i\). Concretely, country B will choose a simple path (i.e. a path that does not use the same road twice, though nodes may be repeated) from \(p_i\) to \(q_i\) in the network excluding roads undergoing scorched earth operations. If on some chosen path every road is without deployed troops (i.e. in state \(U\)), then B’s attack is successful.

Country A wishes to ensure that no matter which combat plan B carries out, the enemy cannot succeed. In other words, with the choices on each road, the following two conditions must hold:

1. Supply connectivity: After the scorched earth operations (i.e. after removing all \(S\) roads), the remaining network (roads in state \(T\) or \(U\)) must be connected (every pair of bases is connected by a path that does not use any scorched road).
2. Preventing successful attack: For every combat plan \(i\) and for every path from \(p_i\) to \(q_i\) in the remaining network (i.e. using roads not scorched), there must be at least one road on that path which has troops deployed (state \(T\)). Equivalently, in the subgraph consisting only of roads in state \(U\) (i.e. available and undefended), \(p_i\) and \(q_i\) must lie in different connected components.

Your task as part of the highest military command is to count the number of different defense plans satisfying the above conditions. Two defense plans are considered different if there is at least one road on which the status (troops deployed vs not, scorched or not scorched) differs. Since the number can be very large, output the answer modulo \(10^9+7\).

Note: Each road can be in one of three states: \(S\): scorched (no troops can be deployed and B cannot use this road), \(T\): not scorched and has troops deployed, \(U\): not scorched and no troops deployed.

The input guarantees that a decision is possible.

inputFormat

The first line contains three integers \(n, m, k\) \( (1 \le n, m, k \le \text{small})\): the number of bases, the number of roads, and the number of enemy combat plans.

Then follow \(m\) lines, each containing two integers \(u\) and \(v\) denoting that there is a bidirectional road connecting bases \(u\) and \(v\). (Bases are numbered from 1 to \(n\).)

Then follow \(k\) lines, each containing two integers \(p_i\) and \(q_i\) describing an enemy combat plan from base \(p_i\) to base \(q_i\).

outputFormat

Output one integer: the number of valid defense plans modulo \(10^9+7\).

sample

3 3 1
1 2
2 3
1 3
1 3

12