Longest Rivers

The Chao Phraya river system is the main river system of Thailand. Its six longest rivers, from longest to shortest, are:

• Tha Chin, 765 km
• Nan, 740 km
• Yom, 700 km
• Ping, 658 km
• Pa Sak, 513 km
• Wang, 335 km

Figure 1 shows a simplified model of this river system, where the smaller red numbers are the lengths of the individual sections of each river. A point where two or more rivers meet as they flow downstream is a confluence, and confluences carry the larger black numbers. In this model every river either ends at a confluence or flows into the sea, and the sea has the special confluence number 0. When two or more rivers meet at a confluence other than 0, the merged river takes the name of one of the rivers that join there. The Ping and the Wang meet at confluence 1, and in the figure the merged river keeps the name Ping. With that naming the Ping is 658 km long and the Wang is only 335 km. If the merged river were named Wang instead, the Wang would be 688 km long and the Ping only 305 km.

Figure 1. The river system of the first example. Sections drawn in the same color belong to one river.

Once this became widely known, rivalries broke out among the towns along the rivers. People living on the Wang argue that with a proper naming scheme their river could be the longest, or the second longest, or at least not the shortest one. Check every such claim.

The rank of a river is its position in the list of all rivers ordered by decreasing length, so the longest river has rank 1. For each river, find the best rank it can reach over all naming schemes. At any confluence, the name of the new larger river must be one of the names of the smaller rivers that join there. If two or more rivers have equal length under a naming scheme, all the tied rivers get the best of the positions they occupy. For example, if one river is the longest and all the other rivers have equal length, those other rivers all have rank 2.

The first line contains two integers $n$ ($1 \le n \le 500000$), the number of river sources in the system, and $m$ ($0 \le m \le n - 1$), the number of confluences with a positive label. Those confluences are numbered from 1 to $m$.

Each of the next $n$ lines describes one river source: a string, which is the name of the river at that source, followed by two integers $c$ ($0 \le c \le m$) and $d$ ($1 \le d \le 10^9$). Here $c$ is the identifier of the nearest confluence downstream, and $d$ is the distance in kilometers from the source to that confluence. A river name consists of 1 to 10 lowercase and uppercase letters.

The last $m$ lines describe confluences 1 to $m$ in the same way. The $k$-th of these lines describes the confluence with identifier $k$ and contains two integers: the identifier of the nearest confluence downstream, and the distance in kilometers from confluence $k$ to that confluence.

Every confluence from 1 to $m$ appears as the nearest confluence downstream at least twice, confluence 0 appears at least once, and every source is connected to confluence 0.

Print one line for each river, in the order the rivers appear in the input. On each line print the name of the river and its best possible rank, separated by a space.