싱글 엘리미네이션
시간 제한2초메모리 제한512 MB
16명의 선수 사이 모든 대진의 승패가 정해져 있을 때, 네 라운드의 대진을 마음대로 짜서 우승시킬 수 있는 선수를 모두 찾는다.
문제
싱글 엘리미네이션은 테니스 메이저 대회, 미국 대학 농구 토너먼트, 대학 미식축구 플레이오프, 여러 올림픽 종목에서 쓰는 대진 방식이다. 참가자 수 이 2의 거듭제곱일 때 가장 깔끔하게 맞아떨어진다. 각 라운드에서 남은 선수를 둘씩 짝지어 경기를 치르고, 진 선수는 모두 탈락하고 이긴 선수만 다음 라운드에 올라간다. 번의 라운드가 끝나면 한 명이 남고, 그 선수가 우승한다.
모든 상대를 이기는 선수가 있으면 그 선수가 언제나 우승한다. 선수마다 유독 상대하기 까다로운 선수가 하나 이상 있을 때부터 상황이 재미있어진다. 운이 나빠 그런 상대를 일찍 만난 선수는 탈락하고, 나중에 그 선수에게 졌을 다른 선수가 이득을 본다. 그래서 각 라운드에서 누가 누구와 붙을지 정하는 권한은 원하는 선수를 우승시키는 데 쓸모가 크다.
선수 16명이 참가한다. 두 선수가 붙으면 누가 이기는지는 모든 쌍에 대해 미리 정해져 있고, 결과는 항상 그대로 나온다. 1라운드 대진을 짠 다음, 2라운드에서는 1라운드 승자끼리 원하는 대로 짝을 지을 수 있다. 3라운드와 4라운드도 마찬가지다. 어떤 선수에게 가장 유리하게 대진을 짰을 때 그 선수가 우승한다면, 그 선수는 우승 가능성이 있다. 우승 가능성이 있는 선수를 모두 찾아라.
입력
첫 줄에 데이터 세트의 개수 가 주어진다. 이어서 개의 데이터 세트가 다음 형식으로 주어진다.
각 데이터 세트는 16개의 줄로 이루어지고, 각 줄에는 16개의 수 이 주어진다. 이면 번 선수와 번 선수가 붙었을 때 번 선수가 이기고, 이면 번 선수가 이긴다. 서로 다른 와 에 대해 와 중 정확히 하나만 1이다. 번 선수가 자기 자신과 붙는 일은 없으므로 의 값은 아무 의미가 없다. 입력을 읽기 편하도록 넣어 둔 값이다.
출력
각 데이터 세트마다 먼저 Data Set x:를 한 줄에 출력한다. 여기서 는 데이터 세트의 번호이고 1부터 센다. 그다음 줄에 대진을 가장 유리하게 짰을 때 우승할 수 있는 선수의 번호를 증가하는 순서로, 공백 하나로 구분해 한 줄에 모두 출력한다. 각 데이터 세트를 출력한 뒤에는 빈 줄을 하나 출력한다.