package No400番台; import java.io.ByteArrayInputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.util.ArrayDeque; import java.util.ArrayList; import java.util.Arrays; public class Main { @SuppressWarnings("unchecked") void solver() { int N = ni(), M = ni(), Q = ni(); ArrayList[] g = new ArrayList[N]; for (int i = 0; i < N; i++) g[i] = new ArrayList<>(); long[] ref = new long[Q]; int[] A = new int[M], B = new int[M]; for (int i = 0; i < M; i++) { A[i] = ni() - 1; B[i] = ni() - 1; } for (int i = 0; i < Q; i++) { int C = ni() - 1, D = ni() - 1; ref[i] = ((long) C << 32) | D; g[C].add(new Edge(C, D, i + 1)); g[D].add(new Edge(D, C, i + 1)); } Arrays.sort(ref); for (int i = 0; i < M; i++) { int idx = Arrays.binarySearch(ref, ((long) A[i] << 32) | B[i]); if (idx < 0) { g[A[i]].add(new Edge(A[i], B[i], Q + 1)); g[B[i]].add(new Edge(B[i], A[i], Q + 1)); } } ArrayDeque que = new ArrayDeque<>(); ArrayDeque[] pending = new ArrayDeque[Q + 2]; for (int i = 0; i < Q + 2; i++) pending[i] = new ArrayDeque<>(); que.add(0); pending[Q + 1].add(0); int[] d = new int[N]; boolean[] checked = new boolean[N]; for (int i = Q + 1; i >= 1; i--) { while (!pending[i].isEmpty()) { que.add(pending[i].poll()); while (!que.isEmpty()) { int v = que.poll(); if (checked[v]) continue; d[v] = i; checked[v] = true; for (Edge e : g[v]) { if (checked[e.dst]) continue; if (e.event_time >= i) { que.add(e.dst); } else { pending[e.event_time].add(e.dst); } } } } } for (int i = 1; i < N; i++) { if (d[i] == Q + 1) { out.println(-1); } else { out.println(d[i]); } } } void tr(Object... o) { System.out.println(Arrays.deepToString(o)); } class Edge { int src; int dst; int event_time; Edge(int src, int dst, int event_time) { this.src = src; this.dst = dst; this.event_time = event_time; } } static InputStream is; static PrintWriter out; static String INPUT = ""; public static void main(String[] args) throws Exception { is = INPUT.isEmpty() ? System.in : new ByteArrayInputStream(INPUT.getBytes()); out = new PrintWriter(System.out); new Main().solver(); ; out.flush(); } static long nl() { try { long num = 0; boolean minus = false; while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-')) ; if (num == '-') { num = 0; minus = true; } else { num -= '0'; } while (true) { int b = is.read(); if (b >= '0' && b <= '9') { num = num * 10 + (b - '0'); } else { return minus ? -num : num; } } } catch (IOException e) { } return -1; } static char nc() { try { int b = skip(); if (b == -1) return 0; return (char) b; } catch (IOException e) { } return 0; } static double nd() { try { return Double.parseDouble(ns()); } catch (Exception e) { } return 0; } static String ns() { try { int b = skip(); StringBuilder sb = new StringBuilder(); if (b == -1) return ""; sb.append((char) b); while (true) { b = is.read(); if (b == -1) return sb.toString(); if (b <= ' ') return sb.toString(); sb.append((char) b); } } catch (IOException e) { } return ""; } public static char[] ns(int n) { char[] buf = new char[n]; try { int b = skip(), p = 0; if (b == -1) return null; buf[p++] = (char) b; while (p < n) { b = is.read(); if (b == -1 || b <= ' ') break; buf[p++] = (char) b; } return Arrays.copyOf(buf, p); } catch (IOException e) { } return null; } public static byte[] nse(int n) { byte[] buf = new byte[n]; try { int b = skip(); if (b == -1) return null; is.read(buf); return buf; } catch (IOException e) { } return null; } static int skip() throws IOException { int b; while ((b = is.read()) != -1 && !(b >= 33 && b <= 126)) ; return b; } static boolean eof() { try { is.mark(1000); int b = skip(); is.reset(); return b == -1; } catch (IOException e) { return true; } } static int ni() { try { int num = 0; boolean minus = false; while ((num = is.read()) != -1 && !((num >= '0' && num <= '9') || num == '-')) ; if (num == '-') { num = 0; minus = true; } else { num -= '0'; } while (true) { int b = is.read(); if (b >= '0' && b <= '9') { num = num * 10 + (b - '0'); } else { return minus ? -num : num; } } } catch (IOException e) { } return -1; } }