축구 베팅
시간 제한1초메모리 제한128 MB
점수가 적힌 16경기의 결과가 뒤섞여 주어질 때, 단일 토너먼트 대진을 복원해 우승 팀을 찾는다.
문제
FIFA 월드컵의 조별 리그가 끝나고, 16강에 오른 16개 팀이 정해졌다. 우리 사장님은 남은 모든 경기를 분석하게 한 뒤, 토너먼트의 남은 경기 전체에 대해 각 경기의 결과를 종이 한 장에 적어 베팅해 두었다. 나는 그 베팅 내역을 가장 가까운 베팅 사무소에 가져가 1,000달러를 걸어야 했다. 그렇게 많은 현금을 주머니에 넣고 긴장한 나머지, 나는 (조금 덜렁대는 편이라) 넘어졌고 베팅 내역이 뒤섞여 버렸다. 그래서 이제 어떤 베팅이 결승전 것인지, 준결승전 것인지, 아니면 다른 경기 것인지 알 수 없게 되었다.
사장님을 실망시키고 싶지 않아서, 나는 딱 하나의 베팅만 하기로 했다. 바로 우승 팀에 거는 것이다. 내가 아는 것은, 각 라운드에서 이긴 팀(상대보다 골을 더 많이 넣은 팀)이 다음 라운드에 올라가고, 진 팀은 탈락한다는 것뿐이다. 단, 준결승은 예외로, 준결승에서 진 두 팀은 3위 결정전을 치른다. 따라서 경기는 모두 16번 열린다.
사장님의 베팅을 바탕으로, 어느 팀이 월드컵에서 우승할지 알려줄 수 있는가?
입력
첫째 줄에 테스트 케이스의 개수 가 주어진다. 각 테스트 케이스는 경기들을 무작위 순서로 설명하는 16개의 줄로 이루어진다. 각 경기는 t1 t2 g1 g2 형식으로 주어지며, 과 는 두 팀의 이름(각각 정확히 세 개의 대문자로 축약됨)이고, 과 는 각각 과 가 넣은 골 수이다.
출력
각 테스트 케이스마다, FIFA 월드컵에서 우승할 팀을 한 줄에 출력한다(항상 옳은 사장님의 분석에 따른다).