이상적인 인스타그램

Alenka는 새로운 인스타그램 스타가 되기로 마음먹었다. 곧바로 새 프로필(@TheRealAlenka)을 열었고, 이제 포르투갈의 어느 축구 선수를 앞지르려면 팔로워 1억 9천만 명만 더 모으면 된다. Alenka는 이른바 travelgram 트렌드를 따르기로 했고, 자신의 프로필에는 여행 사진만 올리기로 했다. 순서대로 시작해서 1997년 케이프타운, 1998년 세투발, 그리고 올해 아제르바이잔의 수도에서의 여름휴가까지 이어졌다. 안타깝게도 팔로워가 고작 1억 명밖에 모이지 않아서 Malnar 씨에게 도움을 청했다.

인스타그램에서 사진은 여러 행으로 배치되고, 각 행에는 사진이 최대 세 장까지 들어간다. 사진은 게시 시각 순으로 정렬되며, 가장 최근 게시물이 왼쪽 위 모서리에 오고 그다음은 이른바 읽기 순서를 따른다. 즉 왼쪽에서 오른쪽으로, 그다음 위에서 아래로다. Malnar 씨는 사진이 잘못 겹쳐져 있다는 것을, 그러니까 서로 다른 여행의 사진이 같은 행에 있는 경우가 있다는 것을 곧바로 알아챘다.

여행 A와 B의 사진은 왼쪽 그림에서는 잘 겹쳐져 있지만 오른쪽 그림에서는 그렇지 않다.

Alenka가 인스타그램 프로필에서 가능한 한 적은 수의 사진을 지워 남은 사진이 잘 겹쳐지도록 도와주자. 사진을 하나 지우면 게시 시각상 다음 사진이 그 자리를 차지하고, 가장 오래된 게시물이 한 칸 옮겨질 때까지 이어진다.

Alenka의 인스타그램 프로필의 최종 모습을 구하자.

첫째 줄에는 자연수 n (1 ≤ n ≤ 105)이 주어지며, 이는 Alenka의 게시물 수다.

나머지 줄에는 영어 대문자 n개가 주어지며, 각 줄에는 최대 세 글자가 들어간다. 이 줄들은 Alenka의 인스타그램 프로필의 현재 모습을 나타내며, 각 글자는 사진 한 장을 나타내고 같은 글자는 해당 사진들이 같은 여행에서 찍혔다는 것을 뜻한다.

입력 데이터는 문제의 서술과 일치한다고 가정할 수 있다. 즉 마지막 줄에만 사진이 세 장 미만일 수 있고, 게시물 순서는 Alenka의 여행의 시간순과 일치한다.

첫째 줄에는 Alenka의 프로필 최종 버전에 있는 게시물 수를 출력한다.

나머지 줄에는 입력 데이터와 동일한 형식으로 Alenka의 프로필을 구성하는 사진을 출력한다. 정답이 여러 개라면 아무거나 출력해도 된다.

두 번째 예제에 대한 설명: