import java.util.*; import java.io.*; import java.awt.Point; import java.math.BigDecimal; import java.math.BigInteger; import static java.lang.Math.*; public class C implements Runnable{ // SOLUTION!!! // HACK ME PLEASE IF YOU CAN!!! // PLEASE!!! // PLEASE!!! // PLEASE!!! void solve() throws IOException { int tests = readInt(); while (tests --> 0) { int n = readInt(); int m = readInt(); int k = readInt(); int[] deliveryCities = readIntArrayWithDecrease(k); int[][] graph = readGraph(n, m, true); int[] answer = getOrder(n, graph, k, deliveryCities); if (answer == null) { out.println(-1); } else { for (int v : answer) { if (v == -1) break; out.print(v + " "); } out.println(); } } } //////////////////////////////// int[][] graph; boolean[] used; List<Integer> topSort; //////////////////////////////// int[][] reverseGraph; int[] components; //////////////////////////////// int[] getOrder(int n, int[][] graph, int k, int[] deliveryCities) { this.used = new boolean[n]; this.topSort = new ArrayList<Integer>(); this.graph = graph; for (int v = 0; v < n; ++v) { if (!used[v]) { topSortDfs(v); } } Collections.reverse(topSort); List<Integer>[] reverseGraphList = new List[n]; for (int v = 0; v < n; ++v) { reverseGraphList[v] = new ArrayList<Integer>(); } for (int from = 0; from < n; ++from) { for (int to : graph[from]) { reverseGraphList[to].add(from); } } this.reverseGraph = new int[n][]; for (int from = 0; from < n; ++from) { reverseGraph[from] = new int[reverseGraphList[from].size()]; for (int index = 0; index < reverseGraph[from].length; ++index) { reverseGraph[from][index] = reverseGraphList[from].get(index); } } this.components = new int[n]; Arrays.fill(components, -1); for (int v : topSort) { if (components[v] == -1) { componentsDfs(v, v); } } boolean[] isComponentSorted = new boolean[n]; List<Integer> topSortComponents = new ArrayList<Integer>(); for (int v : topSort) { int component = components[v]; if (!isComponentSorted[component]) { topSortComponents.add(component); isComponentSorted[component] = true; } } boolean[] isComponentNeeded = new boolean[n]; for (int city : deliveryCities) { isComponentNeeded[components[city]] = true; } int lastComponent = -1; List<Integer> deliveryComponents = new ArrayList<Integer>(); for (int component : topSortComponents) { if (component != lastComponent && isComponentNeeded[component]) { deliveryComponents.add(component); lastComponent = component; } } Iterator<Integer> deliveryIterator = deliveryComponents.iterator(); int curComponent = -1, nextComponent = deliveryIterator.next(); List<Integer>[] componentCities = new List[n]; for (int component : topSortComponents) { componentCities[component] = new ArrayList<Integer>(); } for (int v : topSort) { componentCities[components[v]].add(v); } int[] lastParents = new int[n]; Arrays.fill(lastParents, -1); for (int component : topSortComponents) { boolean check = false; ch: for (int to : componentCities[component]) { for (int from : reverseGraph[to]) { int fromComponent = components[from]; if (fromComponent != component && lastParents[fromComponent] == curComponent) { check = true; break ch; } } } if (check) { lastParents[component] = curComponent; } if (component == nextComponent) { if (lastParents[component] == curComponent) { lastParents[nextComponent] = nextComponent; if (deliveryIterator.hasNext()) { curComponent = nextComponent; nextComponent = deliveryIterator.next(); } else { break; } } else { return null; } } } boolean[] isCityDelivery = new boolean[n]; for (int deliveryCity : deliveryCities) { isCityDelivery[deliveryCity] = true; } int answerSize = 0; int[] answer = new int[n]; Arrays.fill(answer, -1); int[] arrayForSort = new int[n]; for (int deliveryComponent : deliveryComponents) { int curSize = 0; for (int city : componentCities[deliveryComponent]) { if (isCityDelivery[city]) { arrayForSort[curSize++] = city + 1; } } Arrays.sort(arrayForSort, 0, curSize); for (int i = 0; i < curSize; ++i) { answer[answerSize++] = arrayForSort[i]; } } return answer; } void componentsDfs(int from, int component) { components[from] = component; for (int to : reverseGraph[from]) { if (components[to] == -1) { componentsDfs(to, component); } } } void topSortDfs(int from) { used[from] = true; for (int to : graph[from]) { if (!used[to]) { topSortDfs(to); } } topSort.add(from); } ///////////////////////////////////////////////////////////////////// final boolean ONLINE_JUDGE = !new File("input.txt").exists(); BufferedReader in; OutputWriter out; StringTokenizer tok = new StringTokenizer(""); public static void main(String[] args){ new Thread(null, new C(), "", 128 * (1L << 20)).start(); } ///////////////////////////////////////////////////////////////////// void init() throws FileNotFoundException{ Locale.setDefault(Locale.US); if (ONLINE_JUDGE){ in = new BufferedReader(new InputStreamReader(System.in)); out = new OutputWriter(System.out); }else{ in = new BufferedReader(new FileReader("input.txt")); out = new OutputWriter("output.txt"); } } //////////////////////////////////////////////////////////////// long timeBegin, timeEnd; void time(){ timeEnd = System.currentTimeMillis(); System.err.println("Time = " + (timeEnd - timeBegin)); } void debug(Object... objects){ if (ONLINE_JUDGE){ for (Object o: objects){ System.err.println(o.toString()); } } } ///////////////////////////////////////////////////////////////////// public void run(){ try{ timeBegin = System.currentTimeMillis(); Locale.setDefault(Locale.US); init(); solve(); out.close(); time(); }catch (Exception e){ e.printStackTrace(System.err); System.exit(-1); } } ///////////////////////////////////////////////////////////////////// String delim = " "; String readString() throws IOException{ while(!tok.hasMoreTokens()){ try{ tok = new StringTokenizer(in.readLine()); }catch (Exception e){ return null; } } return tok.nextToken(delim); } String readLine() throws IOException{ return in.readLine(); } ///////////////////////////////////////////////////////////////// final char NOT_A_SYMBOL = '\0'; char readChar() throws IOException{ int intValue = in.read(); if (intValue == -1){ return NOT_A_SYMBOL; } return (char) intValue; } char[] readCharArray() throws IOException{ return readLine().toCharArray(); } ///////////////////////////////////////////////////////////////// int readInt() throws IOException { return Integer.parseInt(readString()); } int[] readIntArray(int size) throws IOException { int[] array = new int[size]; for (int index = 0; index < size; ++index){ array[index] = readInt(); } return array; } int[] readSortedIntArray(int size) throws IOException { Integer[] array = new Integer[size]; for (int index = 0; index < size; ++index) { array[index] = readInt(); } Arrays.sort(array); int[] sortedArray = new int[size]; for (int index = 0; index < size; ++index) { sortedArray[index] = array[index]; } return sortedArray; } int[] readIntArrayWithDecrease(int size) throws IOException { int[] array = readIntArray(size); for (int i = 0; i < size; ++i) { array[i]--; } return array; } /////////////////////////////////////////////////////////////////// int[][] readIntMatrix(int rowsCount, int columnsCount) throws IOException { int[][] matrix = new int[rowsCount][]; for (int rowIndex = 0; rowIndex < rowsCount; ++rowIndex) { matrix[rowIndex] = readIntArray(columnsCount); } return matrix; } int[][] readIntMatrixWithDecrease(int rowsCount, int columnsCount) throws IOException { int[][] matrix = new int[rowsCount][]; for (int rowIndex = 0; rowIndex < rowsCount; ++rowIndex) { matrix[rowIndex] = readIntArrayWithDecrease(columnsCount); } return matrix; } /////////////////////////////////////////////////////////////////// long readLong() throws IOException{ return Long.parseLong(readString()); } long[] readLongArray(int size) throws IOException{ long[] array = new long[size]; for (int index = 0; index < size; ++index){ array[index] = readLong(); } return array; } //////////////////////////////////////////////////////////////////// double readDouble() throws IOException{ return Double.parseDouble(readString()); } double[] readDoubleArray(int size) throws IOException{ double[] array = new double[size]; for (int index = 0; index < size; ++index){ array[index] = readDouble(); } return array; } //////////////////////////////////////////////////////////////////// BigInteger readBigInteger() throws IOException { return new BigInteger(readString()); } BigDecimal readBigDecimal() throws IOException { return new BigDecimal(readString()); } ///////////////////////////////////////////////////////////////////// Point readPoint() throws IOException{ int x = readInt(); int y = readInt(); return new Point(x, y); } Point[] readPointArray(int size) throws IOException{ Point[] array = new Point[size]; for (int index = 0; index < size; ++index){ array[index] = readPoint(); } return array; } ///////////////////////////////////////////////////////////////////// int[][] readGraph(int vertexNumber, int edgeNumber, boolean isDirected) throws IOException{ @SuppressWarnings("unchecked") List<Integer>[] graph = new List[vertexNumber]; for (int index = 0; index < vertexNumber; ++index){ graph[index] = new ArrayList<Integer>(); } while (edgeNumber-- > 0){ int from = readInt() - 1; int to = readInt() - 1; graph[from].add(to); if (!isDirected) graph[to].add(from); } int[][] graphInt = new int[vertexNumber][]; for (int from = 0; from < vertexNumber; ++from) { graphInt[from] = new int[graph[from].size()]; for (int index = 0; index < graphInt[from].length; ++index) { graphInt[from][index] = graph[from].get(index); } } return graphInt; } ///////////////////////////////////////////////////////////////////// static class IntIndexPair { static Comparator<IntIndexPair> increaseComparator = new Comparator<IntIndexPair>() { @Override public int compare(IntIndexPair indexPair1, IntIndexPair indexPair2) { int value1 = indexPair1.value; int value2 = indexPair2.value; if (value1 != value2) return value1 - value2; int index1 = indexPair1.index; int index2 = indexPair2.index; return index1 - index2; } }; static Comparator<IntIndexPair> decreaseComparator = new Comparator<IntIndexPair>() { @Override public int compare(IntIndexPair indexPair1, IntIndexPair indexPair2) { int value1 = indexPair1.value; int value2 = indexPair2.value; if (value1 != value2) return -(value1 - value2); int index1 = indexPair1.index; int index2 = indexPair2.index; return index1 - index2; } }; int value, index; public IntIndexPair(int value, int index) { super(); this.value = value; this.index = index; } public int getRealIndex() { return index + 1; } } IntIndexPair[] readIntIndexArray(int size) throws IOException { IntIndexPair[] array = new IntIndexPair[size]; for (int index = 0; index < size; ++index) { array[index] = new IntIndexPair(readInt(), index); } return array; } ///////////////////////////////////////////////////////////////////// static class OutputWriter extends PrintWriter { final int DEFAULT_PRECISION = 12; protected int precision; protected String format, formatWithSpace; { precision = DEFAULT_PRECISION; format = createFormat(precision); formatWithSpace = format + " "; } public OutputWriter(OutputStream out) { super(out); } public OutputWriter(String fileName) throws FileNotFoundException { super(fileName); } public int getPrecision() { return precision; } public void setPrecision(int precision) { precision = max(0, precision); this.precision = precision; format = createFormat(precision); formatWithSpace = format + " "; } private String createFormat(int precision){ return "%." + precision + "f"; } @Override public void print(double d){ printf(format, d); } public void printWithSpace(double d){ printf(formatWithSpace, d); } public void printAll(double...d){ for (int i = 0; i < d.length - 1; ++i){ printWithSpace(d[i]); } print(d[d.length - 1]); } @Override public void println(double d){ printlnAll(d); } public void printlnAll(double... d){ printAll(d); println(); } } ///////////////////////////////////////////////////////////////////// static final int[][] steps = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}}; static final int[][] steps8 = { {-1, 0}, {1, 0}, {0, -1}, {0, 1}, {-1, -1}, {1, 1}, {1, -1}, {-1, 1} }; static final boolean check(int index, int lim){ return (0 <= index && index < lim); } ///////////////////////////////////////////////////////////////////// static final boolean checkBit(int mask, int bit){ return (mask & (1 << bit)) != 0; } ///////////////////////////////////////////////////////////////////// static final long getSum(int[] array) { long sum = 0; for (int value: array) { sum += value; } return sum; } static final Point getMinMax(int[] array) { int min = array[0]; int max = array[0]; for (int index = 0, size = array.length; index < size; ++index, ++index) { int value = array[index]; if (index == size - 1) { min = min(min, value); max = max(max, value); } else { int otherValue = array[index + 1]; if (value <= otherValue) { min = min(min, value); max = max(max, otherValue); } else { min = min(min, otherValue); max = max(max, value); } } } return new Point(min, max); } }