I. Heart Lingers, Future Fades
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a graph with $$$n$$$ vertices, $$$m_1$$$ undirected edges, and $$$m_2$$$ directed edges. The vertices are numbered $$$1,2,\cdots,n$$$.

This graph satisfies the following property: For any subset of vertices, the number of edges (regardless of whether they are directed or undirected) whose both endpoints lie inside this subset does not exceed the size of the subset.

Count the number of ways to assign a direction to every undirected edge such that, after all undirected edges are oriented, the resulting graph contains no directed cycle. Print the answer modulo $$$10^9+7$$$.

It is guaranteed that the answer (before taking the modulo) is at least $$$1$$$. In particular, if $$$m_1=0$$$, the answer is $$$1$$$.

Input

The first line contains three integers $$$n,m_1,m_2$$$ ($$$1\le n\le2\times10^5$$$, $$$m_1,m_2\ge0$$$, $$$m_1+m_2\le2\times10^5$$$).

Each of the next $$$m_1$$$ lines contains two integers $$$u,v$$$ ($$$1\le u,v\le n$$$), denoting an undirected edge $$$u\leftrightarrow v$$$.

Each of the next $$$m_2$$$ lines contains two integers $$$u,v$$$ ($$$1\le u,v\le n$$$), denoting a directed edge $$$u\to v$$$.

It is guaranteed that there is no self-loop in the graph, i.e., $$$u\ne v$$$.

It is also guaranteed that for any pair of vertices, there is at most one edge between them (regardless of whether it is directed or undirected).

Output

Output a single integer, the answer modulo $$$10^9+7$$$.

Example
Input
10 6 2
1 2
2 3
3 4
3 5
6 7
7 8
4 1
8 9
Output
56