测试数据来自 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}\) 。