package practice; import java.util.HashMap; import java.util.HashSet; import java.util.Map; import java.util.Optional; import java.util.Scanner; import java.util.Set; public class Main { public static void main(String[] args) { Main main = new Main(); main.solveC(); } private void solveA() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int Q = sc.nextInt(); UnionFind uf = new SetUnionFind(N + 1); for (int i = 0; i < Q; i++) { int P = sc.nextInt(); int A = sc.nextInt(); int B = sc.nextInt(); if (P == 0) { uf.union(A, B); } else { if (uf.judge(A, B)) { System.out.println("Yes"); } else { System.out.println("No"); } } } } private void solveB() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); System.out.println(N); } private void solveC() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); int M = sc.nextInt(); int Q = sc.nextInt(); int[] A = new int[M]; int[] B = new int[M]; int[] C = new int[Q]; int[] D = new int[Q]; for (int i = 0; i < M; i++) { A[i] = sc.nextInt(); B[i] = sc.nextInt(); } Set set = new HashSet<>(); for (int i = 0; i < Q; i++) { C[i] = sc.nextInt(); D[i] = sc.nextInt(); set.add(trans(C[i], D[i], N)); } SetUnionFind uf = new SetUnionFind(N + 1); for (int i = 0; i < M; i++) { if (!set.contains(trans(A[i], B[i], N))) { uf.union(A[i], B[i]); } } int[] ans = new int[N + 1]; for (int i = 2; i <= N; i++) { if (uf.judge(1, i)) { ans[i] = -1; } } for (int i = Q - 1; i >= 0; i--) { Set set1 = uf.getSet(1); boolean cContain1 = set1.contains(C[i]); boolean dContain1 = set1.contains(D[i]); if (cContain1 && !dContain1) { for (int j : uf.getSet(D[i])) { if (ans[j] == 0) { ans[j] = i + 1; } } } if (!cContain1 && dContain1) { for (int j : uf.getSet(C[i])) { if (ans[j] == 0) { ans[j] = i + 1; } } } uf.union(C[i], D[i]); } for (int i = 2; i <= N; i++) { System.out.println(ans[i]); } } class SetUnionFind extends ArrayUnionFind { Map> childs; public SetUnionFind(int size) { super(size); childs = new HashMap<>(); for (int i = 0; i < size; i++) { childs.put(i, new HashSet<>()); childs.get(i).add(i); } } public Set getSet(int id) { return childs.get(root(id)); } @Override public void union(int A, int B) { Set setA = childs.get(root(A)); Set setB = childs.get(root(B)); if (setA.size() > setB.size()) { setA.addAll(setB); childs.put(root(B), setA); } else { setB.addAll(setA); childs.put(root(A), setB); } super.union(A, B); } } private long trans(int x, int y, int max) { if (x < y) { return 1L * x * max + y; } else { return 1L * y * max + x; } } private void solveD() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); System.out.println(N); } private void solveE() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); System.out.println(N); } private void solveF() { Scanner sc = new Scanner(System.in); int N = sc.nextInt(); System.out.println(N); } interface Graph { void link(int from, int to, long cost); Optional getCost(int from, int to); int getVertexNum(); } interface FlowResolver { long maxFlow(int from, int to); } /** * グラフの行列による実装 * 接点数の大きいグラフで使うとMLEで死にそう */ class ArrayGraph implements Graph { private Long[][] costArray; private int vertexNum; public ArrayGraph(int n) { costArray = new Long[n][]; for (int i = 0; i < n; i++) { costArray[i] = new Long[n]; } vertexNum = n; } @Override public void link(int from, int to, long cost) { costArray[from][to] = new Long(cost); } @Override public Optional getCost(int from, int to) { return Optional.ofNullable(costArray[from][to]); } @Override public int getVertexNum() { return vertexNum; } } /** * DFS(深さ優先探索)による実装 * 計算量はO(E*MaxFlow)のはず (E:辺の数, MaxFlow:最大フロー) */ class DfsFlowResolver implements FlowResolver { private Graph graph; public DfsFlowResolver(Graph graph) { this.graph = graph; } /** * 最大フロー(最小カット)を求める * @param from 始点(source)のID * @param to 終点(target)のID * @return 最大フロー(最小カット) */ public long maxFlow(int from, int to) { long sum = 0L; long currentFlow; do { currentFlow = flow(from, to, Long.MAX_VALUE / 3, new boolean[graph.getVertexNum()]); sum += currentFlow; } while (currentFlow > 0); return sum; } /** * フローの実行 グラフの更新も行う * @param from 現在いる節点のID * @param to 終点(target)のID * @param current_flow ここまでの流量 * @param passed 既に通った節点か否かを格納した配列 * @return 終点(target)に流した流量/戻りのグラフの流量 */ private long flow(int from, int to, long current_flow, boolean[] passed) { passed[from] = true; if (from == to) { return current_flow; } for (int id = 0; id < graph.getVertexNum(); id++) { if (passed[id]) { continue; } Optional cost = graph.getCost(from, id); if (cost.orElse(0L) > 0) { long nextFlow = current_flow < cost.get() ? current_flow : cost.get(); long returnFlow = flow(id, to, nextFlow, passed); if (returnFlow > 0) { graph.link(from, id, cost.get() - returnFlow); graph.link(id, from, graph.getCost(id, from).orElse(0L) + returnFlow); return returnFlow; } } } return 0L; } } /** * 1-indexedのBIT配列 */ class BinaryIndexedTree { private long[] array; public BinaryIndexedTree(int size) { this.array = new long[size + 1]; } /** * 指定した要素に値を加算する * 計算量はO(logN) * @param index 加算する要素の添字 * @param value 加算する量 */ public void add(int index, long value) { for (int i = index; i < array.length; i += (i & -i)) { array[i] += value; } } /** * 1〜指定した要素までの和を取得する * 計算量はO(logN) * @param index 和の終端 * @return 1〜indexまでの和 */ public long getSum(int index) { long sum = 0L; for (int i = index; i > 0; i -= (i & -i)) { sum += array[i]; } return sum; } } interface UnionFind { void union(int A, int B); boolean judge(int A, int B); } /** * 配列によるUnionFindの実装 */ class ArrayUnionFind implements UnionFind { int[] parent; int[] rank; public ArrayUnionFind(int size) { parent = new int[size]; for (int i = 0; i < size; i++) { parent[i] = i; } rank = new int[size]; } @Override public void union(int A, int B) { int rootA = root(A); int rootB = root(B); if (rootA != rootB) { if (rank[rootA] < rank[rootB]) { parent[rootA] = rootB; } else { parent[rootB] = rootA; if (rank[rootA] == rank[rootB]) { rank[rootA]++; } } } } @Override public boolean judge(int A, int B) { return root(A) == root(B); } protected int root(int id) { if (parent[id] == id) { return id; } parent[id] = root(parent[id]); return parent[id]; } } }