Problem: 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 ai, bi and ci, for which she supposes LCA(ai, bi) = ci.

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.

Input

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 ui and vi (1 ≤ ui, vi ≤ n, ui ≠ vi) — 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 ai, bi, ci (1 ≤ ai, bi, ci ≤ n). Each of these triples define LCA(ai, bi) = ci. It's not guaranteed that there exists a tree that satisfy all the given LCA conditions.

Output

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

Examples

Input

4 0 0


Output

16


Input

4 0 1
3 4 2


Output

1


Input

3 1 0
1 2


Output

2


Input

3 0 2
2 3 2
2 3 1


Output

0


Input

4 1 2
1 2
2 2 2
3 4 2


Output

1

Note

In the second sample correct answer looks like this:

<image>

In the third sample there are two possible trees:

<image> <image>

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

Solution (in CPP):

Solution:
#include <bits/stdc++.h>
using namespace std;
template <typename T>
inline int checkbit(T n, T i) {
  return ((n >> i) & T(1));
}
inline int bitcount(int n) { return __builtin_popcount(n); }
inline int bitcount(long long n) { return __builtin_popcountll(n); }
template <typename T>
inline bool isPowerOfTwo(T n) {
  return (n != 0 and ((n & (n - 1)) == 0));
}
inline int binlog(int n) {
  assert(n > 0);
  return 32 - __builtin_clz(n) - 1;
}
inline int binlog(long long n) {
  assert(n > 0);
  return 64 - __builtin_clzll(n) - 1;
}
void bitprint(int n, int w = 32) {
  for (int i = w - 1; i >= 0; i--) {
    cout << checkbit(n, i);
  }
  cout << "\n";
}
void bitprint(long long n, int w = 64) {
  for (long long i = w - 1; i >= 0; i--) {
    cout << checkbit(n, i);
  }
  cout << "\n";
}
template <typename T>
inline T sqr(T x) {
  T x_ = (x);
  return x_ * x_;
}
template <typename T>
inline T qbr(T x) {
  T x_ = (x);
  return ((x_ * x_) * x_);
}
template <typename T>
inline int sign(T x) {
  T x_ = (x);
  return ((x_ > T(0)) - (x_ < T(0)));
}
template <typename T>
inline T mod(T x, T m) {
  T x_ = (x);
  return (((x_) >= 0) ? ((x_) % (m)) : ((((x_) % (m)) + (m)) % (m)));
}
template <typename T>
inline T gcd(T a, T b) {
  while (b) {
    T t = a % b;
    a = b;
    b = t;
  }
  return a;
}
template <typename T>
inline T gcd_ex(T a, T b, T& x, T& y) {
  if (b == 0) {
    x = 1, y = 0;
    return a;
  }
  T x1, y1;
  T d = gcd_ex(b, a % b, x1, y1);
  x = y1;
  y = x1 - (a / b) * y1;
  return d;
}
template <typename T>
inline T lcm(T a, T b) {
  return (a * (b / gcd(a, b)));
}
template <typename A, typename B, typename C>
function<C(A)> combine(function<B(A)> f, function<C(B)> g) {
  return bind(g, bind(f, placeholders::_1));
}
template <typename Collection, typename UnaryOperation>
void foreach (Collection& col, UnaryOperation op) {
  for_each(begin(col), end(col), op);
}
template <typename Collection, typename UnaryOperation>
Collection fmap(Collection& col, UnaryOperation op) {
  transform(begin(col), end(col), col.begin(), op);
  return col;
}
template <typename Collection, typename binop>
Collection zip(Collection& fc, Collection& sc, binop op) {
  transform(begin(fc), end(fc), sc.begin(), fc.begin(), op);
  return fc;
}
template <typename Collection, typename Condition>
bool exists(Collection& col, Condition con) {
  auto exist = find_if(begin(col), end(col), con);
  return exist != col.end();
}
template <typename Collection, typename Predicate>
Collection filterNot(Collection& col, Predicate predicate) {
  auto returnIterator = remove_if(begin(col), end(col), predicate);
  col.erase(returnIterator, end(col));
  return col;
}
void fastIO() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
}
template <class T1, class T2>
istream& operator>>(istream& in, pair<T1, T2>& P) {
  in >> P.first >> P.second;
  return in;
}
template <class T>
istream& operator>>(istream& in, vector<T>& Col) {
  for (auto& el : Col) in >> el;
  return in;
}
template <class T>
inline void getarr(T* arr, int l, int r) {
  for (long long i = l; i < r; i++) cin >> arr[i];
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const pair<T1, T2>& p) {
  os << "(" << p.first << ", " << p.second << ")";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<vector<T>>& v) {
  for (auto& row : v) {
    for (auto& el : row) os << el << " ";
    os << "\n";
  }
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const vector<T>& Col) {
  for (auto& el : Col) os << el << " ";
  return os;
}
template <class T>
ostream& operator<<(ostream& os, const set<T>& Col) {
  for (auto& el : Col) os << el << " ";
  return os;
}
template <class T1, class T2>
ostream& operator<<(ostream& os, const map<T1, T2>& Col) {
  for (auto& el : Col) os << el << " ";
  return os;
}
template <class T>
inline void printarr(T* arr, int l, int r) {
  for (long long i = l; i < r; i++) {
    cout << arr[i] << " ";
  };
  cout << "\n";
}
template <typename First>
void read(First& t) {
  cin >> t;
}
template <typename First, typename... Args>
void read(First& f, Args&... args) {
  cin >> f;
  read(forward<Args&>(args)...);
}
template <typename T>
void print(T&& t) {
  cout << t << "\n";
}
template <typename First, typename... Args>
void print(First&& f, Args&&... args) {
  cout << f << " ";
  print(forward<Args&&>(args)...);
}
template <typename T>
void printLn(T&& t) {
  cout << t << "\n";
}
template <typename First, typename... Args>
void printLn(First&& f, Args&&... args) {
  cout << f << "\n";
  printLn(forward<Args&&>(args)...);
}
template <typename T, size_t N>
struct MakeTensor {
  template <typename... Args>
  static auto tensor(size_t first, Args... sizes)
      -> vector<decltype(MakeTensor<T, N - 1>::tensor(sizes...))> {
    auto inner = MakeTensor<T, N - 1>::tensor(sizes...);
    return vector<decltype(inner)>(first, inner);
  }
};
template <typename T>
struct MakeTensor<T, 1> {
  static vector<T> tensor(size_t size) { return vector<T>(size); }
};
template <typename T, typename... Args>
auto tensor(Args... args)
    -> decltype(MakeTensor<T, sizeof...(Args)>::tensor(args...)) {
  return MakeTensor<T, sizeof...(Args)>::tensor(args...);
}
const int MAXN = 13;
long long dp[1 << MAXN][MAXN][MAXN];
vector<int> G[MAXN];
vector<pair<int, int>> lcaIs[MAXN];
long long dpm[1 << MAXN][MAXN];
int V, E, Q;
long long ConstructTree(int mask, int root);
long long CalcVersions(int mask, int lastn, int root) {
  if (mask == 0) return 1;
  long long& curr = dp[mask][lastn][root];
  if (curr != -1) return curr;
  long long ways = 0;
  for (int submask = mask; submask > 0; submask = (submask - 1) & mask) {
    if (all_of(begin(lcaIs[root]), end(lcaIs[root]),
               [&](const pair<int, int>& p) {
                 return !checkbit(submask, p.first) ||
                        !checkbit(submask, p.second);
               })) {
      for (int nextRoot = lastn + 1; nextRoot < V; nextRoot++) {
        if (checkbit(submask, nextRoot) &&
            all_of(begin(G[nextRoot]), end(G[nextRoot]), [&](const int v) {
              return v == root || checkbit(submask, v);
            })) {
          int outmask = mask ^ submask;
          ways += ConstructTree(submask, nextRoot) *
                  CalcVersions(outmask, nextRoot, root);
        }
      }
    }
  }
  curr = ways;
  return ways;
}
long long ConstructTree(int mask, int root) {
  long long& answ = dpm[mask][root];
  if (answ != -1) return answ;
  if (all_of(begin(lcaIs[root]), end(lcaIs[root]), [&](pair<int, int> p) {
        return checkbit(mask, p.first) && checkbit(mask, p.second);
      })) {
    answ = CalcVersions(mask ^ (1 << root), -1, root);
  } else {
    answ = 0;
  }
  return answ;
}
int main() {
  cin >> V >> E >> Q;
  for (int i = 0; i < E; i++) {
    int a, b;
    cin >> a >> b;
    a--, b--;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  for (int i = 0; i < Q; i++) {
    int a, b, lca;
    read(a, b, lca);
    a--, b--, lca--;
    lcaIs[lca].push_back({a, b});
  }
  for (auto& grid : dp)
    for (auto& row : grid) fill(begin(row), end(row), -1);
  for (auto& row : dpm) fill(begin(row), end(row), -1);
  print(ConstructTree((1 << V) - 1, 0));
  return 0;
}