测试数据来自 AHSFNUOI2020/1000

题目描述

$\text{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\%$ 的数据， $1\leq N\leq 1$ ；

对于 $20\%$ 的数据， $1\leq N\leq 10$ ；

对于额外 $15\%$ 的数据，一个人要么住单人间，要么就用单人桌；

对于额外 $15\%$ 的数据, 保证 $N$ 是偶数， $M_1=M_2=\frac{N}{2}$ ；

对于额外 $20\%$ 的数据, 保证数据完全随机生成；

对于 $100\%$ 的数据，保证 $1\leq N\leq 2\times 10^5,M_1,M_2\leq \frac{N}{2}$ 。