题目描述

X 班有 \(n\) 个人，从 \(1\) 到 \(n\) 编号。他们中有一些人住双人宿舍，一些人住单间，也就是说一些人有唯一的一个室友，有些人则没有。同时有些人会和他的同桌共用一张双人桌，另一些人则单独坐。
你需要求出有多少个排列 \(P\)，满足原本的人 \(i\) 换到 \(P_i\) 的宿舍以及桌子上后，原本的室友以及同桌关系依旧不变，答案对 \(10^9+7\) 取模。

输入格式

第一行三个整数 \(n,m_1,m_2\)，表示人数，双人宿舍数量，双人桌数量。
接下来 \(m_1\) 行，每行两个整数 \(x,y\)，表示 \(x\) 和 \(y\) 同住一间双人宿舍。
接下来 \(m_2\) 行，每行两个整数 \(x,y\)，表示 \(x\) 和 \(y\) 同用一张双人桌。

输出格式

输出一行一个整数，表示满足条件的排列数量。

样例

样例输入 1

7 2 2
1 2
3 4
1 4
5 6

样例输出 1

4

样例输入 2

5 2 1
1 2
3 4
1 4

样例输出 2

2

数据范围与提示

对于 \(5\%\) 的数据，\(n=1\)。
对于 \(20\%\) 的数据，\(1\le n\le 10\)。
对于额外 \(15\%\) 的数据，一个人要么住单人间，要么就用单人桌。
对于额外 \(15\%\) 的数据，保证 \(n\) 是偶数， \(m_1=m_2=\frac n2\)。
对于额外 \(20\%\) 的数据，保证数据完全随机生成。
对于 \(100\%\) 的数据，保证 \(1\le n\le 2\times 10^5;m_1,m_2\le \frac n2\)。