우승할 수 있는 팀

셰이크 압둘은 축구를 정말 좋아한다. 해마다 여는 이 대회에 유명한 팀을 불러 모으려고 돈을 얼마나 썼는지는 묻지 않는 편이 좋다. 그만큼 돈을 썼으니 특정 팀끼리 맞붙는 경기를 꼭 보고 싶어 한다. 그래서 보고 싶은 경기를 하나도 빠뜨리지 않고 목록으로 적어 두었다.

이 경기를 다음 규칙에 맞게 라운드로 나눈다.

• 한 라운드에서 남아 있는 팀은 각각 많아야 한 경기를 치른다.
• 남은 팀의 수가 짝수이면 모든 팀이 정확히 한 경기를 치른다.
• 남은 팀의 수가 홀수이면 경기를 치르지 않는 팀이 정확히 하나 있다. 그 팀은 부전승으로 다음 라운드에 올라간다.
• 각 경기의 승자는 다음 라운드에 올라가고, 패자는 대회에서 탈락한다.
• 팀이 하나만 남으면 그 팀이 대회 우승 팀이 된다.

귀납법으로 증명할 수 있듯이 팀이 $n$개인 대회에서는 우승 팀이 가려질 때까지 정확히 $n - 1$경기가 필요하고, 셰이크가 적어 둔 목록의 경기 수도 $n - 1$이다.

1라운드가 끝나면 아직 치르지 않은 경기가 남은 팀이 이미 탈락해 있을 수도 있다. 그래서 일정을 짤 때는 각 경기의 승자까지 함께 정해야 한다. 승자를 어떻게 정하느냐에 따라 규칙을 지키는 일정이 여러 가지로 나오고, 우승 팀도 달라진다.

목록의 경기를 모두 치르면서 규칙을 지키고 어떤 팀의 우승으로 끝나는 일정이 하나라도 있으면, 그 팀을 우승 후보라고 하자. 우승 후보가 몇 팀인지와 그중 이름이 가장 앞서는 팀을 구한다.

입력은 여러 개의 테스트 케이스로 이루어진다. 각 테스트 케이스는 대회에 참가하는 팀의 수 $n$ ($2 \le n \le 1000$)으로 시작한다. 다음 $n$줄에는 참가하는 팀의 이름이 한 줄에 하나씩 주어진다. 팀 이름은 영어 알파벳('a'부터 'z', 'A'부터 'Z')으로만 이루어지고 길이는 25 이하다. 한 테스트 케이스 안에서 팀 이름은 서로 다르다.

이어지는 $n - 1$줄에는 셰이크가 보고 싶어 하는 경기가 순서에 상관없이 주어진다. 각 줄에는 그 경기를 치르는 두 팀의 이름이 주어진다. 주어진 경기만으로 규칙을 지키는 대회 일정을 항상 만들 수 있다.

마지막 테스트 케이스 다음 줄에는 0이 주어진다.

각 테스트 케이스마다 두 값을 공백으로 구분해 한 줄에 출력한다. 먼저 우승 후보의 수를 출력하고, 이어서 우승 후보 중 이름이 가장 앞서는 팀의 이름을 출력한다.

이름은 ASCII 순서로 비교한다. 대문자는 모두 소문자보다 앞서므로 Zulu가 apple보다 앞선다.