有根树是一种没有任何简单环的连通图,其中一个顶点被选为根。在此问题中,顶点号 1 始终充当根。
两个顶点 u 和 v 的最低公共祖先是距离根顶点最远的顶点,该顶点既位于从 u 到根的路径上,又位于从 v 到根的路径上。我们将其表示为 LCA(u, v)。
桑迪有一棵由 n 个顶点组成的有根树,她用它来存储坚果。不幸的是,水下风暴折断了她的树,她不记得它的所有边缘。她只设法恢复了初始树的 m 个边和 q 个三元组 ai、bi 和 ci,为此她假设 LCA(ai, bi) = ci。
帮助桑迪数出大小为 n、以顶点 1 作为根的树的数量,这些树与她记住的所有信息相匹配。如果她弄得一团糟并且不存在这样的树,则打印 0。如果两棵有根树中存在出现在其中一棵中而另一棵中不存在的边,则认为两棵有根树是不同的。
输入
输入的第一行包含三个整数 n、m 和 q (1 ≤ n ≤ 13, 0 ≤ m < n, 0 ≤ q ≤ 100)——分别是 Sandy 记住的顶点数、边数和 LCA 三元组。
接下来的 m 行中的每一行都包含两个整数 ui 和 vi (1 ≤ ui, vi ≤ n, ui ≠ vi) - 由第 i 条边连接的顶点数。保证这组边是某棵树的边的子集。
最后 q 行包含数字 ai、bi、ci (1 ≤ ai、bi、ci ≤ n) 的三元组。这些三元组中的每一个都定义 LCA(ai, bi) = ci。不能保证存在满足所有给定 LCA 条件的树。
输出
打印一个整数——满足所有条件的大小为 n 的树的数量。
示例
输入 #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
注意
在第二个示例中,正确答案如下所示:
在第三个示例中,有两种可能的树:
在第四个样本中,答案为 0,因为有关 LCA 的信息不一致。