<h2>题意</h2>
给你若干限制，限制为 $lca(u,v) = c$ 和 $(u,v)$ 有连边，数一下以一为根的满足限制的树的个数。
$n \leq 13$，限制总数 $\leq 100$
<h2>题解</h2>
这个题目太神仙了。。远古 CF 场的题目还是好。
考虑设 $f_{v,S}$ 表示 $v$ 节点子树内的点是 $S$ 的树的个数。答案是 $f_{0,U}$ （将点的标号减一后）
首先我们考虑一下不考虑限制怎么转移：一个 naive 的想法是：
$$f_{v,S} = \sum_{T \subseteq S} \sum_{x \in T} f_{x,T}* f_{v,S-T}$$
也就是枚举这次将那些点拿下去建一个子树。
但是我们考虑到会重复：我们考虑子树内的点集 $\{1,2,3,4,5\}$ 如果这样统计，那么方案 $\{1,2\} \{3,4,5\}$ 和 $\{3,4,5\} \{1,2\}$ 都会被计入，但是显然这两种方案是应该被计入一次的。
于是我们考虑固定 $T$ 内的一个点，这样就不会出现上面的情况了。
接下来我们来考虑限制，我们其实只需要转移的时候排除掉所有不正确的情况就好了：
- lca(u,v) = c
- 考虑如果你现在枚举的这个点为 $c$ 但是 $u,v$ 都在一个子树中，这显然不行。
- 考虑如果 $c$ 在你枚举的这个子树，那么 $u,v$ 也必须在这个子树中
- $u,v$ 有一条边
- 如果这个边的一个端点在你现在枚举的点上，那么另一端点只能有至多一个点在这个子树中，并且如果这个点在子树中，需要强制这个点为子树的根。
- 如果端点不在你枚举的点上，$u,v$ 只能同属于这个子树或同不属于这个子树。
然后分类讨论一下就做完了
/*
* Author: RainAir
* Time: 2019-10-08 19:07:45
*/
#include <algorithm>
#include <iostream>
#include <cstring>
#include <climits>
#include <cstdlib>
#include <cstdio>
#include <bitset>
#include <vector>
#include <cmath>
#include <ctime>
#include <queue>
#include <stack>
#include <map>
#include <set>
#define fi first
#define se second
#define U unsigned
#define P std::pair
#define LL long long
#define pb push_back
#define MP std::make_pair
#define all(x) x.begin(),x.end()
#define CLR(i,a) memset(i,a,sizeof(i))
#define FOR(i,a,b) for(int i = a;i <= b;++i)
#define ROF(i,a,b) for(int i = a;i >= b;--i)
#define DEBUG(x) std::cerr << #x << '=' << x << std::endl
const int MAXN = 13+2;
const int MAXM = 1000+5;
#define int LL
int fMAXN;
int n,m,q;
int pc[(1<<MAXN)+3];
int a[MAXM],b[MAXM],c[MAXM];
int GMAXN;
struct Edge{
int u,v;
Edge(int u=0,int v=0) : u(u),v(v) {}
}e[MAXN];
bool in(int x, int s){ return s & (1 << x); }
inline int dfs(int v,int S){
int &ans = fv;
if(pc[S] == 1) return ans = (S == (1<<v));
if(ans != -1) return ans;
ans = 0;S ^= (1<<v);
// int TT = ((1<<n)-1)^(1<<0);
int son = 0;
FOR(i,0,n-1) if((1<<i)&S) son = i; // 固定连通块包含的点，避免重复（不包含这个点的连通块总会在枚举的集合的补集被取到）
for(int T = S;T;T = (T-1)&S){
if(!((1<<son)&T)) continue;
// lca
// 如果 lca 在这个点上，那么两个点要在不同的子树里
// 如果 lca 在子树，那么这两个点都要在子树里
bool flag = true;
FOR(i,1,q){
if(c[i] == v && (T&(1<<a[i])) && (T&(1<<b[i]))){
flag = 0;
break;
}
}
if(!flag) continue;
FOR(i,1,q){
if(T&(1<<c[i]) && !((T&(1<<a[i])) && (T&(1<<b[i])))){
flag = 0;
break;
}
}
if(!flag) continue;
// edge
// 如果端点在这个点上，那么另一个点只能有一个在这个子树里
// 如果端点不在这个点上，不能一个在子树一个不在子树
FOR(i,1,m){
if(e[i].u != v && e[i].v != v && ((bool)(T&(1<<e[i].u))) ^ ((bool)(T&(1<<e[i].v)))){
flag = 0;
break;
}
}
if(!flag) continue;
int cnt = 0,x = 0;
FOR(i,1,m){
if(e[i].u == v || e[i].v == v){
int t = e[i].u == v ? e[i].v : e[i].u;
if(T&(1<<t)) cnt++,x = t;
if(cnt > 1){
flag = 0;
break;
}
}
}
if(!flag) continue;
// if(v == 1 && S == 4) DEBUG(T),DEBUG(cnt),DEBUG(x);
if(cnt == 1) ans += dfs(x,T)*dfs(v,(S^T)^(1<<v));
else{
FOR(x,0,n-1){
if(T&(1<<x))
ans += dfs(x,T)*dfs(v,(S^T)^(1<<v));
// if(v == 0 && T == 6) DEBUG(dfs(x,T)),DEBUG(x);
}
}
}
return ans;
}
signed main(){
scanf("%lld%lld%lld",&n,&m,&q);CLR(f,-1);
FOR(i,1,(1<<n)-1) pc[i] = pc[i>>1]+(i&1);
FOR(i,1,m){
int u,v;scanf("%lld%lld",&u,&v);--u;--v;
Gu = Gv = 1;
e[i] = Edge(u,v);
}
FOR(i,1,q) scanf("%lld%lld%lld",a+i,b+i,c+i),--a[i],--b[i],--c[i];
FOR(i,0,n-1) fi = 1;
printf("%lldn",dfs(0,(1<<n)-1));
return 0;
}
