Polycarp is currently developing a project in Vaja language and using a popular dependency management system called Vamen. From Vamen's point of view both Vaja project and libraries are treated projects for simplicity. A project in Vaja has its own uniqie non-empty name consisting of lowercase latin letters with length not exceeding 10 and version — positive integer from 1 to 10 6 . Each project (keep in mind that it is determined by both its name and version) might depend on other projects. For sure, there are no cyclic dependencies. You're given a list of project descriptions. The first of the given projects is the one being developed by Polycarp at this moment. Help Polycarp determine all projects that his project depends on (directly or via a certain chain). It's possible that Polycarp's project depends on two different versions of some project. In this case collision resolving is applied, i.e. for each such project the system chooses the version that minimizes the distance from it to Polycarp's project. If there are several options, the newer (with the maximum version) is preferred. This version is considered actual; other versions and their dependencies are ignored. More formal, choose such a set of projects of minimum possible size that the following conditions hold: Polycarp's project is chosen; Polycarp's project depends (directly or indirectly) on all other projects in the set; no two projects share the name; for each project x that some other project in the set depends on we have either x or some y with other version and shorter chain to Polycarp's project chosen. In case of ties the newer one is chosen. Output all Polycarp's project's dependencies (Polycarp's project itself should't be printed) in lexicographical order. The first line contains an only integer n ( 1 ≤ n ≤ 1 000 ) — the number of projects in Vaja. The following lines contain the project descriptions. Each project is described by a line consisting of its name and version separated