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>
#pragma comment(linker, "/stack:20000000")
using namespace std;
double __begin;
template <typename T1, typename T2, typename T3>
struct triple {
  T1 a;
  T2 b;
  T3 c;
  triple(){};
  triple(T1 _a, T2 _b, T3 _c) : a(_a), b(_b), c(_c) {}
};
template <typename T1, typename T2, typename T3>
bool operator<(const triple<T1, T2, T3> &t1, const triple<T1, T2, T3> &t2) {
  if (t1.a != t2.a)
    return t1.a < t2.a;
  else if (t1.b != t2.b)
    return t1.b < t2.b;
  else
    return t1.c < t2.c;
}
template <typename T1, typename T2, typename T3>
inline std::ostream &operator<<(std::ostream &os, const triple<T1, T2, T3> &t) {
  return os << "(" << t.a << ", " << t.b << ", " << t.c << ")";
}
inline int bits_count(int v) {
  v = v - ((v >> 1) & 0x55555555);
  v = (v & 0x33333333) + ((v >> 2) & 0x33333333);
  return ((v + (v >> 4) & 0xF0F0F0F) * 0x1010101) >> 24;
}
inline int bits_count(long long v) {
  int t = v >> 32;
  int p = (v & ((1LL << 32) - 1));
  return bits_count(t) + bits_count(p);
}
unsigned int reverse_bits(register unsigned int x) {
  x = (((x & 0xaaaaaaaa) >> 1) | ((x & 0x55555555) << 1));
  x = (((x & 0xcccccccc) >> 2) | ((x & 0x33333333) << 2));
  x = (((x & 0xf0f0f0f0) >> 4) | ((x & 0x0f0f0f0f) << 4));
  x = (((x & 0xff00ff00) >> 8) | ((x & 0x00ff00ff) << 8));
  return ((x >> 16) | (x << 16));
}
inline int sign(int x) { return x > 0; }
inline bool isPowerOfTwo(int x) { return (x != 0 && (x & (x - 1)) == 0); }
template <typename T1, typename T2>
inline std::ostream &operator<<(std::ostream &os, const std::pair<T1, T2> &p) {
  return os << "(" << p.first << ", " << p.second << ")";
}
template <typename T>
inline std::ostream &operator<<(std::ostream &os, const std::vector<T> &v) {
  bool first = true;
  os << "[";
  for (unsigned int i = 0; i < v.size(); i++) {
    if (!first) os << ", ";
    os << v[i];
    first = false;
  }
  return os << "]";
}
template <typename T>
inline std::ostream &operator<<(std::ostream &os, const std::set<T> &v) {
  bool first = true;
  os << "[";
  for (typename std::set<T>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T1, typename T2>
inline std::ostream &operator<<(std::ostream &os, const std::map<T1, T2> &v) {
  bool first = true;
  os << "[";
  for (typename std::map<T1, T2>::const_iterator ii = v.begin(); ii != v.end();
       ++ii) {
    if (!first) os << ", ";
    os << *ii;
    first = false;
  }
  return os << "]";
}
template <typename T, typename T2>
void printarray(T a[], T2 sz, T2 beg = 0) {
  for (T2 i = beg; i < sz; i++) cout << a[i] << " ";
  cout << endl;
}
inline long long mulmod(long long x, long long n, long long _mod) {
  long long res = 0;
  while (n) {
    if (n & 1) res = (res + x) % _mod;
    x = (x + x) % _mod;
    n >>= 1;
  }
  return res;
}
inline long long powmod(long long x, long long n, long long _mod) {
  long long res = 1;
  while (n) {
    if (n & 1) res = (res * x) % _mod;
    x = (x * x) % _mod;
    n >>= 1;
  }
  return res;
}
inline long long gcd(long long a, long long b) {
  long long t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline int gcd(int a, int b) {
  int t;
  while (b) {
    a = a % b;
    t = a;
    a = b;
    b = t;
  }
  return a;
}
inline long long lcm(long long a, long long b) { return a / gcd(a, b) * b; }
inline long long gcd(long long a, long long b, long long c) {
  return gcd(gcd(a, b), c);
}
inline int gcd(int a, int b, int c) { return gcd(gcd(a, b), c); }
template <class T>
inline void cinarr(T &a, int n) {
  for (int i = 0; i < n; ++i) cin >> a[i];
}
long long dp[1 << 13][13][13];
int cor[1 << 13];
vector<pair<int, int> > edges;
vector<int> w[101];
vector<triple<int, int, int> > lcas;
vector<pair<int, int> > pars[120];
bool areConnected[101][101];
int n, m, q;
long long makeTree(int mask, int root);
long long compose(int mask, int lastr, int root) {
  if (mask == 0) return 1;
  long long &res = dp[mask][lastr][root];
  if (res != -1) {
    return res;
  }
  long long ans = 0;
  for (int sm = mask; sm > 0; sm = mask & (sm - 1)) {
    int outm = mask ^ sm;
    bool bad = false;
    for (auto p : pars[root]) {
      if (((sm >> p.first) & 1) && ((sm >> p.second) & 1)) {
        bad = true;
        break;
      }
    }
    if (bad) continue;
    for (int oneMoreRoot = lastr + 1; oneMoreRoot < n; ++oneMoreRoot) {
      if (((sm >> oneMoreRoot) & 1)) {
        bool bad = false;
        for (auto x : w[oneMoreRoot]) {
          if (x != root && !((sm >> x) & 1)) {
            bad = true;
            break;
          }
        }
        if (!bad) {
          ans += makeTree(sm, oneMoreRoot) * compose(outm, oneMoreRoot, root);
        }
      }
    }
  }
  res = ans;
  return ans;
}
long long dpm[1 << 13][13];
long long makeTree(int mask, int root) {
  long long &res = dpm[mask][root];
  if (res != -1) return res;
  bool bad = false;
  for (auto p : pars[root]) {
    if (!((mask >> p.first) & 1) || !((mask >> p.second) & 1)) {
      bad = true;
      break;
    }
  }
  if (bad)
    res = 0;
  else
    res = compose(mask ^ (1 << root), -1, root);
  return res;
}
int main() {
  cin >> n >> m >> q;
  for (int i = 0; i < m; i++) {
    int x, y;
    cin >> x >> y;
    --x;
    --y;
    w[x].push_back(y);
    w[y].push_back(x);
    edges.push_back({x, y});
    areConnected[x][y] = areConnected[y][x] = true;
  }
  for (int i = 0; i < q; i++) {
    int x, y, z;
    cin >> x >> y >> z;
    --x;
    --y;
    --z;
    lcas.push_back({x, y, z});
    pars[z].push_back({x, y});
  }
  for (int mask = 0; mask < (1 << n); ++mask) {
    for (int i = 0; i < 13; i++)
      for (int j = 0; j < 13; j++) dp[mask][i][j] = -1;
    for (int i = 0; i < 13; i++) dpm[mask][i] = -1;
  }
  long long ans = makeTree((1 << n) - 1, 0);
  cout << ans << endl;
  return 0;
}