import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; import java.io.BufferedReader; import java.util.LinkedList; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class eks { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); PrintWriter out = new PrintWriter(outputStream); EKS_PLAYAROUND solver = new EKS_PLAYAROUND(); solver.solve(1, in, out); out.close(); } static class EKS_PLAYAROUND { public void solve(int testNumber, InputReader in, PrintWriter out) { int N = in.nextInt(); int M = in.nextInt(); ArrayList<Integer> H[] = new ArrayList[N + 1]; int MAX_L = 0; for (int i = 1; i <= N; i++) { H[i] = new ArrayList<>(); int L = in.nextInt(); MAX_L = Math.max(L, MAX_L); for (int j = 0; j < L; j++) { H[i].add(in.nextInt()); } } int S[] = new int[M]; for (int i = 0; i < M; i++) S[i] = in.nextInt(); ArrayList<Integer> current = new ArrayList<>(); current.add(1); if (S.length == 1 && S[0] == 1) { out.println(1); return; } for (int day = 2; day <= 80000; day++) { LinkedList<Integer> next = new LinkedList<>(); for (Integer a : current) { next.addAll(H[a]); } current = new ArrayList<>(next.size()); for (Integer a : next) { current.add(a); } if (contains(current, S)) { out.println(day); return; } if ((long) MAX_L * current.size() * S.length > 5000000) { out.println("-1"); return; } } } private boolean contains(ArrayList<Integer> current, int[] s) { for (int i = 0; i < current.size() - s.length + 1; i++) { boolean wrong = false; for (int j = 0; j < s.length; j++) { if (current.get(i + j) != s[j]) { wrong = true; break; } } if (!wrong) return true; } return false; } } static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } 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()); } } }
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 | import java.io.OutputStream; import java.io.IOException; import java.io.InputStream; import java.io.PrintWriter; import java.io.IOException; import java.io.InputStreamReader; import java.util.ArrayList; import java.util.StringTokenizer; import java.io.BufferedReader; import java.util.LinkedList; import java.io.InputStream; /** * Built using CHelper plug-in * Actual solution is at the top */ public class eks { public static void main(String[] args) { InputStream inputStream = System.in; OutputStream outputStream = System.out; InputReader in = new InputReader(inputStream); PrintWriter out = new PrintWriter(outputStream); EKS_PLAYAROUND solver = new EKS_PLAYAROUND(); solver.solve(1, in, out); out.close(); } static class EKS_PLAYAROUND { public void solve(int testNumber, InputReader in, PrintWriter out) { int N = in.nextInt(); int M = in.nextInt(); ArrayList<Integer> H[] = new ArrayList[N + 1]; int MAX_L = 0; for (int i = 1; i <= N; i++) { H[i] = new ArrayList<>(); int L = in.nextInt(); MAX_L = Math.max(L, MAX_L); for (int j = 0; j < L; j++) { H[i].add(in.nextInt()); } } int S[] = new int[M]; for (int i = 0; i < M; i++) S[i] = in.nextInt(); ArrayList<Integer> current = new ArrayList<>(); current.add(1); if (S.length == 1 && S[0] == 1) { out.println(1); return; } for (int day = 2; day <= 80000; day++) { LinkedList<Integer> next = new LinkedList<>(); for (Integer a : current) { next.addAll(H[a]); } current = new ArrayList<>(next.size()); for (Integer a : next) { current.add(a); } if (contains(current, S)) { out.println(day); return; } if ((long) MAX_L * current.size() * S.length > 5000000) { out.println("-1"); return; } } } private boolean contains(ArrayList<Integer> current, int[] s) { for (int i = 0; i < current.size() - s.length + 1; i++) { boolean wrong = false; for (int j = 0; j < s.length; j++) { if (current.get(i + j) != s[j]) { wrong = true; break; } } if (!wrong) return true; } return false; } } static class InputReader { public BufferedReader reader; public StringTokenizer tokenizer; public InputReader(InputStream stream) { reader = new BufferedReader(new InputStreamReader(stream), 32768); tokenizer = null; } 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()); } } } |