package chelper; import java.util.ArrayList; import java.util.Deque; import java.util.HashMap; import java.util.HashSet; import java.util.LinkedList; import java.util.List; import java.util.Map; import java.util.Objects; import java.util.Set; import java.util.TreeSet; import io.InputReader; import io.OutputWriter; import misc.SimpleSavingChelperSolution; public class C extends SimpleSavingChelperSolution { public void solve(int testNumber, InputReader in, OutputWriter out) { wrapSolve(testNumber, in, out); } class Project implements Comparable { final String name; final int version; final List dependencies = new ArrayList<>(); public Project(String name, int version) { this.name = name; this.version = version; } @Override public int compareTo(Project o) { if (!name.equals(o.name)) { return name.compareTo(o.name); } return -Integer.compare(version, o.version); } @Override public boolean equals(Object o) { if (this == o) return true; if (o == null || getClass() != o.getClass()) return false; Project project = (Project) o; return version == project.version && Objects.equals(name, project.name); } @Override public int hashCode() { return Objects.hash(name, version); } @Override public String toString() { return String.format("%s %d", name, version); } } Map> allProjects = new HashMap<>(); Project getProject(String name, int version) { allProjects.putIfAbsent(name, new HashMap<>()); allProjects.get(name).putIfAbsent(version, new Project(name, version)); return allProjects.get(name).get(version); } @Override public void solve(int testNumber) { int n = in.nextInt(); List projects = new ArrayList<>(); for (int i = 0; i < n; i++) { Project project = getProject(in.nextString(), in.nextInt()); projects.add(project); int depCount = in.nextInt(); for (int j = 0; j < depCount; j++) { Project depProject = getProject(in.nextString(), in.nextInt()); project.dependencies.add(depProject); } } Set dependencies = new TreeSet<>(); Set dependencyNames = new TreeSet<>(); Set neighbors = new TreeSet<>(); neighbors.add(projects.get(0)); while (!neighbors.isEmpty()) { Set nextNeighbors = new TreeSet<>(); for (Project neighbor : neighbors) { if (dependencyNames.contains(neighbor.name)) { continue; } dependencyNames.add(neighbor.name); dependencies.add(neighbor); nextNeighbors.addAll(neighbor.dependencies); } neighbors = nextNeighbors; } dependencies.remove(projects.get(0)); out.println(dependencies.size()); for (Project dependency : dependencies) { out.println(dependency); } } }