모든 길은 어디로 통하는가?

"모든 길은 로마로 통한다"라는 오래된 격언이 있다. 이 말이 문자 그대로 참이라면 두 도시 사이의 경로를 찾는 일은 간단하다. 도시 $A$에서 도시 $B$로 가려면 $A$에서 로마로 간 뒤 로마에서 $B$로 가면 된다. 물론 실제로는 더 짧은 경로가 존재하는 경우가 많다.

로마 제국의 도로망은 단순한 트리 구조를 이룬다. 로마에서 출발한 여러 개의 도로가 가까운 도시들로 뻗어 나가고, 그 도시들에서 다시 더 먼 도시들로 도로가 이어지는 식이다. 따라서 도시들은 로마를 중심으로 여러 계층(level)에 놓여 있다고 볼 수 있다. 로마는 홀로 $0$번 계층에 있으며, $i$번 계층의 도시는 오직 $i-1$번 계층과 $i+1$번 계층의 도시들하고만 연결된다. 도로망에는 사이클이 없다. $i$번 계층의 모든 도시는 $i-1$번 계층의 도시 정확히 하나(로마에 더 가까운 유일한 이웃)와 연결되고, $i+1$번 계층의 도시 $0$개 이상과 연결된다. 그 결과 도로망은 로마를 루트로 하는 트리가 되며, 임의의 두 도시 사이에는 정확히 하나의 단순 경로가 존재한다.

이러한 도로망과 도시들이 주어질 때, 주어진 두 도시 사이의 가장 짧은 경로를 구하라. 경로의 길이는 그 경로에 놓인 도시의 수로 잰다.

첫째 줄에는 공백 하나로 구분된 두 정수가 주어진다. 첫 번째 정수 $m$은 도로망에 있는 도로의 수, 두 번째 정수 $n$은 질의의 수이다.

다음 $m$개의 줄에는 각각 공백 하나로 구분된 두 도시의 이름이 주어지며, 하나의 도로를 나타낸다. 도시 이름은 최대 열 개의 알파벳으로 이루어지고 첫 글자는 대문자이다. 서로 다른 두 도시는 같은 첫 글자를 가지지 않는다. Rome이라는 도시는 항상 등장하며 $0$번 계층의 도시이다. 각 도로 줄에서 첫 번째 도시는 두 번째 도시보다 낮은 번호의 계층에 있다(즉 첫 번째 도시가 두 번째 도시의 로마 쪽 이웃이다). 같은 도로 줄이 두 번 나오는 일은 없으며, 도로망은 위에서 설명한 트리 구조를 따른다.

이어지는 $n$개의 줄에는 각각 공백 하나로 구분된 두 도시의 이름이 주어지며, 이것이 질의 쌍이다. 각 쌍에 대해 첫 번째 도시에서 두 번째 도시로 가는 가장 짧은 경로를 구해야 한다. 질의에 등장하는 두 도시는 모두 앞의 도로 목록에 반드시 나타나며, 한 도시가 자기 자신과 짝지어지는 경우는 없다.

$n$개의 질의 각각에 대해, 해당 쌍의 두 도시 사이 가장 짧은 경로를 한 줄에 출력한다. 도로망이 트리이므로 이 경로는 유일하다. 경로는 첫 번째 질의 도시에서 두 번째 질의 도시까지(양 끝 도시 포함) 지나는 도시들의 첫 글자를 공백 없이 연속된 대문자로 나열하여 나타낸다. $k$번째 출력 줄은 $k$번째 질의에 대응한다.