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()); } } } |
English