In Ancient Berland there were n cities and m two-way roads of equal length. The cities are numbered with integers from 1 to n inclusively. According to an ancient superstition, if a traveller visits three cities ai, bi, ci in row, without visiting other cities between them, a great disaster awaits him. Overall there are k such city triplets. Each triplet is ordered, which means that, for example, you are allowed to visit the cities in the following order: ai, ci, bi. Vasya wants to get from the city 1 to the city n and not fulfil the superstition. Find out which minimal number of roads he should take. Also you are required to find one of his possible path routes.

Input

The first line contains three integers n, m, k (2 ≤ n ≤ 3000, 1 ≤ m ≤ 20000, 0 ≤ k ≤ 105) which are the number of cities, the number of roads and the number of the forbidden triplets correspondingly. 

Then follow m lines each containing two integers xi, yi (1 ≤ xi, yi ≤ n) which are the road descriptions. The road is described by the numbers of the cities it joins. No road joins a city with itself, there cannot be more than one road between a pair of cities. 

Then follow k lines each containing three integers ai, bi, ci (1 ≤ ai, bi, ci ≤ n) which are the forbidden triplets. Each ordered triplet is listed mo more than one time. All three cities in each triplet are distinct.

City n can be unreachable from city 1 by roads.

Output

If there are no path from 1 to n print -1. Otherwise on the first line print the number of roads d along the shortest path from the city 1 to the city n. On the second line print d + 1 numbers — any of the possible shortest paths for Vasya. The path should start in the city 1 and end in the city n.

Examples

Input

4 4 1
1 2
2 3
3 4
1 3
1 4 3


Output

2
1 3 4


Input

3 1 0
1 2


Output

-1


Input

4 4 2
1 2
2 3
3 4
1 3
1 2 3
1 3 4


Output

4
1 3 2 3 4
import java.io.IOException;
import java.io.InputStream;
import java.io.OutputStream;
import java.io.PrintWriter;
import java.util.*;

/*
                   _ooOoo_
                  o8888888o
                  88" . "88
                  (| -_- |)
                  O\  =  /O
               ____/`---'\____
             .'  \\|     |//  `.
            /  \\|||  :  |||//  \
           /  _||||| -:- |||||-  \
           |   | \\\  -  /// |   |
           | \_|  ''\---/''  |   |
           \  .-\__  `-`  ___/-. /
         ___`. .'  /--.--\  `. . __
      ."" '<  `.___\_<|>_/___.'  >'"".
     | | :  `- \`.;`\ _ /`;.`/ - ` : | |
     \  \ `-.   \_ __\ /__ _/   .-` /  /
======`-.____`-.___\_____/___.-`____.-'======
                   `=---='
^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
            pass System Test!
*/

public class E {
  private static class Task {

    void solve(FastScanner in, PrintWriter out) {
      int N = in.nextInt();
      int M = in.nextInt();
      int K = in.nextInt();
      ArrayList<Integer>[] graph = new ArrayList[N];
      for (int i = 0; i < N; i++) {
        graph[i] = new ArrayList<>();
      }

      for (int i = 0; i < M; i++) {
        int v = in.nextInt() - 1, u = in.nextInt() - 1;
        graph[v].add(u);
        graph[u].add(v);
      }

      //<a*N+b, [c]>
      TreeMap<Integer, TreeSet<Integer>> triples = new TreeMap<>();
      for (int i = 0; i < K; i++) {
        int a = in.nextInt() - 1;
        int b = in.nextInt() - 1;
        int c = in.nextInt() - 1;

        int key = a * N + b;
        TreeSet<Integer> cs = triples.get(key);
        if (cs == null) triples.put(key, cs = new TreeSet<>());
        cs.add(c);
      }

      ArrayDeque<Integer> deque = new ArrayDeque<>();
      int[][] dist = new int[N][N];
      for (int[] d : dist) Arrays.fill(d, Integer.MAX_VALUE);
      deque.add(0);
      dist[0][0] = 0;
      outer:
      while (!deque.isEmpty()) {
        Integer key = deque.poll();
        int v = key % N;// now
        int p = key / N;// parent
        for (int next : graph[v]) {
          if (triples.containsKey(key) && triples.get(key).contains(next)) continue;
          if (dist[v][next] > dist[p][v] + 1) {
            dist[v][next] = dist[p][v] + 1;
            deque.add(v * N + next);
            if (next == N - 1) break outer;
          }
        }
      }

      int min = Integer.MAX_VALUE;
      for (int i = 0; i < N; i++) min = Math.min(min, dist[i][N - 1]);
      if (min == Integer.MAX_VALUE) {
        out.println(-1);
        return;
      }

      out.println(min);
      ArrayList<Integer> ans = new ArrayList<>();
      int cur = N - 1;
      while (cur > 0) {
        ans.add(cur + 1);
        for (int v : graph[cur]) {
          if (dist[v][cur] == min) {
            cur = v;
            min--;
            break;
          }
        }
      }
      Collections.reverse(ans);
      out.print(1);
      for (int v : ans) {
        out.print(" " + v);
      }
      out.println();

    }
  }

  /**
   * ここから下はテンプレートです。
   */
  public static void main(String[] args) {
    OutputStream outputStream = System.out;
    FastScanner in = new FastScanner();
    PrintWriter out = new PrintWriter(outputStream);
    Task solver = new Task();
    solver.solve(in, out);
    out.close();
  }
  private static class FastScanner {
    private final InputStream in = System.in;
    private final byte[] buffer = new byte[1024];
    private int ptr = 0;
    private int bufferLength = 0;

    private boolean hasNextByte() {
      if (ptr < bufferLength) {
        return true;
      } else {
        ptr = 0;
        try {
          bufferLength = in.read(buffer);
        } catch (IOException e) {
          e.printStackTrace();
        }
        if (bufferLength <= 0) {
          return false;
        }
      }
      return true;
    }

    private int readByte() {
      if (hasNextByte()) return buffer[ptr++];
      else return -1;
    }

    private static boolean isPrintableChar(int c) {
      return 33 <= c && c <= 126;
    }

    private void skipUnprintable() {
      while (hasNextByte() && !isPrintableChar(buffer[ptr])) ptr++;
    }

    boolean hasNext() {
      skipUnprintable();
      return hasNextByte();
    }

    public String next() {
      if (!hasNext()) throw new NoSuchElementException();
      StringBuilder sb = new StringBuilder();
      int b = readByte();
      while (isPrintableChar(b)) {
        sb.appendCodePoint(b);
        b = readByte();
      }
      return sb.toString();
    }

    long nextLong() {
      if (!hasNext()) throw new NoSuchElementException();
      long n = 0;
      boolean minus = false;
      int b = readByte();
      if (b == '-') {
        minus = true;
        b = readByte();
      }
      if (b < '0' || '9' < b) {
        throw new NumberFormatException();
      }
      while (true) {
        if ('0' <= b && b <= '9') {
          n *= 10;
          n += b - '0';
        } else if (b == -1 || !isPrintableChar(b)) {
          return minus ? -n : n;
        } else {
          throw new NumberFormatException();
        }
        b = readByte();
      }
    }

    double nextDouble() {
      return Double.parseDouble(next());
    }

    double[] nextDoubleArray(int n) {
      double[] array = new double[n];
      for (int i = 0; i < n; i++) {
        array[i] = nextDouble();
      }
      return array;
    }

    double[][] nextDoubleMap(int n, int m) {
      double[][] map = new double[n][];
      for (int i = 0; i < n; i++) {
        map[i] = nextDoubleArray(m);
      }
      return map;
    }

    public int nextInt() {
      return (int) nextLong();
    }

    public int[] nextIntArray(int n) {
      int[] array = new int[n];
      for (int i = 0; i < n; i++) array[i] = nextInt();
      return array;
    }

    public long[] nextLongArray(int n) {
      long[] array = new long[n];
      for (int i = 0; i < n; i++) array[i] = nextLong();
      return array;
    }

    public String[] nextStringArray(int n) {
      String[] array = new String[n];
      for (int i = 0; i < n; i++) array[i] = next();
      return array;
    }

    public char[][] nextCharMap(int n) {
      char[][] array = new char[n][];
      for (int i = 0; i < n; i++) array[i] = next().toCharArray();
      return array;
    }
  }
}
