← 返回题目列表

Codeforces · 599/E

E. 桑迪和坚果

中文机器翻译题面 查看原题

有根树是一种没有任何简单环的连通图,其中一个顶点被选为根。在此问题中,顶点号 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 的信息不一致。