가장 긴 강

차오프라야 수계는 태국을 대표하는 강 수계다. 길이가 긴 순서로 여섯 개를 꼽으면 다음과 같다.

• 타친강 765 km
• 난강 740 km
• 욤강 700 km
• 핑강 658 km
• 빠삭강 513 km
• 왕강 335 km

이 수계를 단순하게 나타낸 모형이 그림 1이다. 작은 빨간색 수는 각 강을 이루는 구간의 길이다. 강이 하류로 흐르다가 둘 이상 만나는 지점을 합류점이라 하고, 합류점에는 큰 검은색 수를 붙였다. 이 모형에서 모든 강은 합류점에서 끝나거나 바다로 흘러들며, 바다에는 특별한 합류점 번호 0을 붙인다. 0이 아닌 합류점에서 둘 이상의 강이 만나면 합쳐진 강은 그곳에서 만난 강 가운데 하나의 이름을 물려받는다. 핑강과 왕강은 합류점 1에서 만나고, 그림에서는 합쳐진 강이 핑강이라는 이름을 유지한다. 이렇게 이름을 붙이면 핑강의 길이는 658 km이고 왕강은 335 km에 그친다. 합쳐진 강을 왕강이라고 불렀다면 왕강이 688 km, 핑강이 305 km가 된다.

그림 1. 첫 번째 예제의 수계. 같은 색으로 그린 구간이 하나의 강이다.

이 사실이 알려지자 강을 낀 마을 사이에 다툼이 벌어졌다. 왕강 사람들은 이름만 잘 붙이면 자기네 강이 가장 길어질 수 있고, 두 번째가 될 수도 있으며, 적어도 꼴찌는 면한다고 주장한다. 이런 주장을 모두 검증하라.

강의 순위는 모든 강을 길이가 긴 순서로 늘어놓았을 때의 위치이고, 가장 긴 강의 순위가 1이다. 강마다 모든 이름 붙이기 방법을 통틀어 얻을 수 있는 가장 좋은 순위를 구하라. 어느 합류점에서든 새로 생긴 큰 강의 이름은 그곳에서 만나는 작은 강의 이름 가운데 하나여야 한다. 한 이름 붙이기 방법에서 길이가 같은 강이 둘 이상이면 그 강은 모두 가장 좋은 순위를 받는다. 예를 들어 한 강이 가장 길고 나머지 강의 길이가 모두 같다면 나머지 강의 순위는 모두 2다.

첫째 줄에 수계에 있는 발원지의 수 $n$ ($1 \le n \le 500000$)과 양수 번호가 붙은 합류점의 수 $m$ ($0 \le m \le n - 1$)이 주어진다. 이 합류점의 번호는 1부터 $m$까지다.

다음 $n$개 줄은 발원지를 하나씩 설명한다. 각 줄에는 그 발원지에서 시작하는 강의 이름을 나타내는 문자열과 정수 $c$ ($0 \le c \le m$), $d$ ($1 \le d \le 10^9$)가 주어진다. $c$는 하류 방향으로 가장 가까운 합류점의 번호이고, $d$는 발원지에서 그 합류점까지의 거리(km)다. 강 이름은 영어 대소문자로만 이루어지고 길이는 1자 이상 10자 이하다.

마지막 $m$개 줄은 합류점 1번부터 $m$번까지를 같은 방식으로 설명한다. 그중 $k$번째 줄은 번호가 $k$인 합류점을 설명하며, 하류 방향으로 가장 가까운 합류점의 번호와 합류점 $k$에서 그 합류점까지의 거리(km)를 나타내는 두 정수가 주어진다.

1번부터 $m$번까지의 합류점은 각각 "하류 방향으로 가장 가까운 합류점"으로 두 번 이상 나오고, 합류점 0은 한 번 이상 나온다. 모든 발원지는 합류점 0과 이어져 있다.

입력에 나온 순서대로 강마다 한 줄씩 출력한다. 각 줄에는 강의 이름과 그 강이 받을 수 있는 가장 좋은 순위를 공백으로 구분해 출력한다.