CF599E.Sandy and Nuts

Rooted tree is a connected graph without any simple cycles with one vertex selected as a root. In this problem the vertex number 1 will always serve as a root.

Lowest common ancestor of two vertices u and v is the farthest from the root vertex that lies on both the path from u to the root and on path from v to the root. We will denote it as LCA(u, v).

Sandy had a rooted tree consisting of n vertices that she used to store her nuts. Unfortunately, the underwater storm broke her tree and she doesn't remember all it's edges. She only managed to restore m edges of the initial tree and q triples a__i, b__i and c__i, for which she supposes LCA(a__i, b__i) = c__i.

Help Sandy count the number of trees of size n with vertex 1 as a root, that match all the information she remembered. If she made a mess and there are no such trees then print 0. Two rooted trees are considered to be distinct if there exists an edge that occur in one of them and doesn't occur in the other one.

有根树是一种连通且不含简单环的图，其中指定一个顶点作为根。在本题中，顶点编号 1 始终作为根。

两个顶点 $u$ 和 $v$ 的最近公共祖先（Lowest Common Ancestor, LCA） 是距离根最远、同时位于 $u$ 到根的路径和 $v$ 到根的路径上的顶点。我们将其记作 $\mathrm{LCA}(u,\,v)$。

Sandy 原本拥有一棵包含 $n$ 个顶点的有根树，用于储存她的坚果。不幸的是，一场水下风暴摧毁了这棵树，她已无法记起全部的边。她仅成功恢复了初始树中的 $m$ 条边，以及 $q$ 个三元组 $a_i$, $b_i$ 和 $c_i$，她推测满足 $\mathrm{LCA}(a_i,\,b_i) = c_i$。

请帮助 Sandy 计算：满足她所记住的所有信息、且以顶点 1 为根的 $n$ 个顶点的有根树共有多少种？若她记忆有误，不存在满足条件的树，则输出 0。若两棵有根树存在某条边仅属于其中一棵，则认为它们是不同的。

The first line of the input contains three integers n, m and q (1 ≤ n ≤ 13, 0 ≤ m < n, 0 ≤ q ≤ 100) — the number of vertices, the number of edges and LCA triples remembered by Sandy respectively.

Each of the next m lines contains two integers u__i and v__i (1 ≤ u__i, v__i ≤ n, u__i ≠ v__i) — the numbers of vertices connected by the i-th edge. It's guaranteed that this set of edges is a subset of edges of some tree.

The last q lines contain the triplets of numbers a__i, b__i, c__i (1 ≤ a__i, b__i, c__i ≤ n). Each of these triples define LCA(a__i, b__i) = c__i. It's not guaranteed that there exists a tree that satisfy all the given LCA conditions.

输入的第一行包含三个整数 $n$、$m$ 和 $q$（$1 ≤ n ≤ 13$，$0 ≤ m < n$，$0 ≤ q ≤ 100$），分别表示顶点数、边数以及 Sandy 记住的 LCA 三元组数量。

接下来的 $m$ 行每行包含两个整数 $u_i$ 和 $v_i$（$1 ≤ u_i,\,v_i ≤ n$，$u_i ≠ v_i$），表示第 $i$ 条边所连接的两个顶点编号。保证这些边构成的集合是某棵树的边集的一个子集。

最后 $q$ 行每行包含三个数 $a_i$、$b_i$、$c_i$（$1 ≤ a_i,\,b_i,\,c_i ≤ n$）。每个三元组表示 $\mathrm{LCA}(a_i,\,b_i) = c_i$。不能保证存在一棵树满足所有给定的 LCA 条件。

Print a single integer — the number of trees of size n that satisfy all the conditions.

输出一个整数——满足所有条件的大小为 $n$ 的树的数量。

In the second sample correct answer looks like this:

In the third sample there are two possible trees:

In the fourth sample the answer is 0 because the information about LCA is inconsistent.

第二个样例的正确答案如下所示：

第三个样例中存在两棵可能的树：

第四个样例的答案为 0，因为关于 LCA 的信息相互矛盾。