이름 순서 바로잡기

졸업식에서 누가 언제 단상에 오를지 정하려면 보통 성을 알파벳 순으로 정렬하고, 성이 같으면 이름으로 순서를 정한다. 그러려면 먼저 각 학생의 이름과 성이 각각 무엇인지 알아내야 한다. 그런데 (1) 여러 나라와 문화권에서는 성과 이름의 순서가 반대이고, (2) 순서가 반대인 경우가 아니더라도 10,000줄짜리 운영체제를 거뜬히 작성하는 학생들이 “First Name”과 “Last Name” 두 칸 중 어디에 자기 이름과 성을 넣어야 하는지는 잘 판단하지 못한다는 문제가 있어서 이 일이 더 어려워진다. 이 문제에서는 USC 관리자가 이름과 성의 순서를 바로잡을 수 있도록 돕는 프로그램을 작성한다.

각 학생마다 그 학생이 이름과 성으로 입력한 두 문자열이 주어진다. 또한 각 문자열은 이름으로만 쓰이거나 성으로만 쓰일 수 있고, 둘 다로 쓰일 수는 없다고 가정한다.1 예를 들어 “Aretha Franklin”과 “Franklin Roosevelt”가 함께 있을 수 없다. 그러면 “Franklin”이 이름과 성 양쪽으로 쓰이기 때문이다. 두 학생이 이런 이름을 주장했다면 둘 중 한 명은 이름과 성을 뒤집어야 한다. 이름 목록이 주어졌을 때, 모든 이름이 일관되게, 즉 각 문자열이 이름으로만 쓰이거나 성으로만 쓰이도록 만들기 위해 입력한 이름을 뒤집어야 하는 학생 수의 최솟값을 출력한다. 불가능하면 “Impossible”을 출력한다.

1 완전히 현실적이지는 않다.

첫 줄에는 입력 데이터 세트의 수 $1 \le K \le 100$이 주어지고, 이어서 $K$개의 데이터 세트가 주어진다. 각 데이터 세트는 다음과 같다.

첫 줄에는 이름이 포함된 학생 수 $0 \le n \le 1{,}000$이 주어진다. 이어서 $n$개의 줄에 두 문자열 $s_{i,1}$, $s_{i,2}$가 공백으로 구분되어 주어진다. 각 문자열은 1자에서 30자까지의 소문자로 이루어진다.

각 데이터 세트마다 “Data Set x:”를 한 줄에 단독으로 출력한다. 여기서 x는 데이터 세트의 번호이다. 그다음 줄에 입력을 일관되게 만들기 위해 입력한 이름과 성을 뒤집어야 하는 학생 수의 최솟값을 출력한다. 방법이 없으면 “Impossible”을 출력한다.

각 데이터 세트 뒤에는 빈 줄을 하나 출력한다.