有没有好做法

题目背景

蛋糕吃完当然要拍照！

题目解释

小C、小F、小Y和他们的朋友们 $a_1, a_2, a_3, ......, a_n$ 要一起拍照，但是现在有 $m$ 组人不愿意站在一起，有 $k$ 组人必须要站在一起，那么他们在一起拍照到底有多少种可能性呢？

输入输出格式

输入格式

第一行输入 $n, m, k$，但是在 $a_1$ 到 $a_n$ 中不包括 小C、小F、小Y。

接下来的 $m$ 行，每行输入 $q_i, p_i$ 代表第 $q_i, p_i$ 两个人不愿意站在一起，保证 $q_i, p_i$ 升序输入且不重复。

再接下来的 $k$ 行，输入 $d_i, b_i$ 代表第 $d_i, b_i$ 两个人必须站在一起，与 $q_i, p_i$ 标准相同，但保证 $(d_i, b_i)$ 不会有任何一组与 $(q_i, p_i)$ 相同。

输出格式

输出最后的答案，对 $15263748$ 取模（不是质数），特别的，对于无解，输出 they cant make photo。

数据样例

8 0 0

40320

提示

对于 $20\%$ 的数据，保证 $1 \le n, m, k \le 10$。

对于所有的数据，保证 $1 \le n , m, k \le 10^6$。