Sandy and Nuts

题意翻译

你曾经有一棵（以 $1$ 号点为根的）树，但你却忘记了它的形态，只记得其中的 $m$ 条边，以及 $q$ 对关系：$a_i$ 号点和 $b_i$ 号点的 $\text{LCA}$ 为 $c_i$ 号点。现在你想知道有多少种满足这些条件的树。

题目描述

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.

输入输出格式

输入格式

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.

输出格式

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

输入输出样例

输入样例 #1

4 0 0

输出样例 #1

16

输入样例 #2

4 0 1
3 4 2

输出样例 #2

1

输入样例 #3

3 1 0
1 2

输出样例 #3

2

输入样例 #4

3 0 2
2 3 2
2 3 1

输出样例 #4

0

输入样例 #5

4 1 2
1 2
2 2 2
3 4 2

输出样例 #5

1

说明

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.