import java.util.ArrayList; import java.util.LinkedList; import java.util.List; import java.util.Queue; import java.util.Scanner; import java.util.Set; import java.util.TreeSet; public class CrowdedForest { static final int MaxClearing = 500; static final String EPSILON = "Empty"; static public Set trail[][]; public static void addTrail(int c1, int c2, Set animals) { trail[c1][c2] = animals; trail[c2][c1] = animals; } // display trails public static void printTrails() { for (int i = 0; i < MaxClearing; i++) for (int j = 0; j < MaxClearing; j++) { Set animals = trail[i][j]; if (animals != null) { System.out.println("[" + i + "," + j + "]" + animals); } } } // find all clearings reachable without collecting animals public static Set reachable(Set start) { boolean newClearing = true; Set reached = new TreeSet(); reached.addAll(start); while (newClearing) { newClearing = false; for (int c : start) { for (int i = 0; i < MaxClearing; i++) { Set animals = trail[c][i]; if ((animals != null) && animals.contains(EPSILON)) { if (!start.contains(i)) { reached.add(i); newClearing = true; } } } } start.addAll(reached); } return reached; } // find trail to neighboring clearing(s) with animal a public static Set findNeighbors(Set locations, String a) { Set dests = new TreeSet(); // find all neighboring clearings reached on path with animal a for (int c : locations) { for (int i = 0; i < MaxClearing; i++) { Set animals = trail[c][i]; if ((animals != null) && !animals.contains(EPSILON)) { for (String s : animals) { if (a.equals(s)) { dests.add(i); } } } } } dests = reachable(dests); // System.out.println(locations + "--" + a + "->" + dests); return dests; } // find path in forest for target list public static Queue> findPath(List target) { Queue> path = new LinkedList>(); Set locations = new TreeSet(); locations.add(0); locations = reachable(locations); path.offer(locations); for (String a : target) { Set dests = findNeighbors(locations, a); if (dests.isEmpty()) return null; locations = dests; path.offer(dests); } if (!locations.contains(0)) return null; return path; } public static void main(String[] argv) { int c1 = 0, c2 = 0; trail = new TreeSet[MaxClearing][MaxClearing]; Scanner sc = new Scanner(System.in); while (sc.hasNextLine()) { Scanner lsc = new Scanner(sc.nextLine()); // read in trails if (lsc.hasNextInt()) { c1 = lsc.nextInt(); c2 = lsc.nextInt(); Set animals = new TreeSet(); if (!lsc.hasNext()) { animals.add(EPSILON); } else while (lsc.hasNext()) { animals.add(lsc.next()); } addTrail(c1, c2, animals); continue; } // printTrails(); // no more trails List targets = new ArrayList(); while (lsc.hasNext()) targets.add(lsc.next()); Queue> q = findPath(targets); if (q == null) System.out.println("Failed"); else { System.out.println("Succeeded"); } } } }