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 JAVA):

Solution:
import java.io.OutputStream;
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.Arrays;
import java.io.BufferedWriter;
import java.util.HashMap;
import java.io.IOException;
import java.io.Reader;
import java.io.InputStreamReader;
import java.util.Objects;
import java.util.StringTokenizer;
import java.util.Map;
import java.io.Writer;
import java.io.OutputStreamWriter;
import java.io.BufferedReader;
import java.io.InputStream;

/**
 * Built using CHelper plug-in
 * Actual solution is at the top
 *
 * @author Ruins He
 */
public class Main {
  public static void main(String[] args) {
    InputStream inputStream = System.in;
    OutputStream outputStream = System.out;
    InputReader in = new InputReader(inputStream);
    OutputWriter out = new OutputWriter(outputStream);
    TaskE solver = new TaskE();
    solver.solve(1, in, out);
    out.close();
  }

  static class TaskE {
    private int n;
    private int m;
    private int q;
    private int[] edges;
    private int[][] conditions;
    private long[][] dp;

    @SuppressWarnings("unchecked")
    public void solve(int testNumber, InputReader in, OutputWriter out) {
      n = in.nextInt();
      m = in.nextInt();
      q = in.nextInt();
      edges = new int[n];
      conditions = new int[q << 1][];
      int count = 0;
      Map<Pair<Integer, Integer>, Integer> lca = new HashMap<>();
      for (int i = 0; i < n; i++) lca.put(Pair.ofUnique(i, i), i);
      for (int i = 0; i < m; i++) {
        int u = in.nextInt() - 1;
        int v = in.nextInt() - 1;
        edges[u] |= 1 << v;
        edges[v] |= 1 << u;
      }
      for (int i = 0; i < q; i++) {
        int u = in.nextInt() - 1;
        int v = in.nextInt() - 1;
        int w = in.nextInt() - 1;
        Integer value = lca.get(Pair.ofUnique(u, v));
        if (value != null && !Objects.equals(value, w)) {
          out.println("0");
          return;
        } else if (value == null) {
          lca.put(Pair.ofUnique(u, v), w);
          conditions[count++] = new int[]{u, v, w};
          conditions[count++] = new int[]{v, u, w};
        }
      }
      q = count;
      dp = new long[n][1 << n];
      for (int i = 0; i < n; i++) Arrays.fill(dp[i], -1);
      out.println(dfs(0, (1 << n) - 1));
    }

    private long dfs(final int u, final int mask) {
      if (dp[u][mask] != -1) return dp[u][mask];
      if ((mask & (1 << u)) == 0) return dp[u][mask] = 0;
      for (int i = 0; i < q; i++) {
        if (conditions[i][2] == u) continue;
        if ((mask & (1 << conditions[i][0])) != 0 && conditions[i][1] == u) return dp[u][mask] = 0;
      }
      if (mask == (1 << u)) return dp[u][mask] = 1;
      long res = 0;

      int allChildren = mask ^ (1 << u);
      int highest = Integer.highestOneBit(allChildren);
      for (int subTree = allChildren; subTree != 0; subTree = (subTree - 1) & allChildren) {
        if ((subTree & highest) == 0) continue;
        int leftNodes = allChildren ^ subTree;
        if (isAllConditionsValid(u, subTree, leftNodes)) {
          for (int v = 0; v < n; v++) {
            if ((subTree & (1 << v)) != 0 && (edges[u] & (subTree ^ (1 << v))) == 0) {
              res += dfs(v, subTree) * dfs(u, leftNodes | (1 << u));
            }
          }
        }
      }

      return dp[u][mask] = res;
    }

    private boolean isAllConditionsValid(int u, int subTree, int leftNodes) {
      for (int i = 0; i < q; i++) {
        if (conditions[i][2] == u) continue;
        if ((subTree & (1 << conditions[i][0])) != 0
            && (leftNodes & (1 << conditions[i][1])) != 0) return false;
      }
      for (int v = 0; v < n; v++) {
        if ((subTree & (1 << v)) != 0 && (leftNodes & edges[v]) != 0) return false;
      }
      return true;
    }

  }

  static class InputReader {
    public final BufferedReader reader;
    public StringTokenizer tokenizer = null;

    public InputReader(Reader reader) {
      this.reader = new BufferedReader(reader, 32767);
    }

    public InputReader(InputStream inputStream) {
      this(new InputStreamReader(inputStream));
    }

    public String next() {
      while (tokenizer == null || !tokenizer.hasMoreTokens()) {
        try {
          tokenizer = new StringTokenizer(reader.readLine());
        } catch (IOException e) {
          throw new RuntimeException(e);
        }
      }
      return tokenizer.nextToken();
    }

    public int nextInt() {
      return Integer.parseInt(next());
    }

  }

  static class Pair<F extends Comparable<F>, S extends Comparable<S>> implements Comparable<Pair<F, S>> {
    public F first;
    public S second;

    public Pair(F first, S second) {
      this.first = first;
      this.second = second;
    }

    public static <F extends Comparable<F>, S extends Comparable<S>> Pair<F, S> of(
        F first, S second) {
      return new Pair<>(first, second);
    }

    public static <T extends Comparable<T>> Pair<T, T> ofUnique(
        T first, T second) {
      if (first == null) return of(null, second);
      else if (second == null) return of(null, first);
      else return first.compareTo(second) < 0 ? of(first, second) : of(second, first);
    }


    public int compareTo(Pair<F, S> other) {
      int fd = this.first.compareTo(other.first);
      if (fd != 0) return fd;
      else return this.second.compareTo(other.second);
    }


    public String toString() {
      return "Pair{" + first + ", " + second + "}";
    }


    public boolean equals(Object o) {
      if (this == o) return true;
      if (o == null || getClass() != o.getClass()) return false;

      Pair<?, ?> pair = (Pair<?, ?>) o;

      if (first != null ? !first.equals(pair.first) : pair.first != null) return false;
      return !(second != null ? !second.equals(pair.second) : pair.second != null);

    }


    public int hashCode() {
      return Objects.hash(first, second);
    }

  }

  static class OutputWriter {
    private final PrintWriter writer;

    private OutputWriter(Writer writer, boolean autoFlush) {
      this.writer = new PrintWriter(new BufferedWriter(writer, 32767), autoFlush);
    }

    public OutputWriter(Writer writer) {
      this(writer, true);
    }

    public OutputWriter(OutputStream outputStream) {
      this(new OutputStreamWriter(outputStream), false);
    }

    public OutputWriter println(String string) {
      writer.println(string);
      return this;
    }

    public OutputWriter println(long value) {
      writer.println(value);
      return this;
    }

    public void close() {
      writer.close();
    }

  }
}