학원 체험 수업 수료 명단

문제

한 학원은 학생들이 여러 분야를 경험할 수 있도록 K종류의 체험 수업을 운영한다. 수업 종류에는 1번부터 K번까지 번호가 붙어 있다. 학생은 원하는 순서로 수업에 참여할 수 있으며, 같은 종류의 수업에 여러 번 참여해도 된다. 학원은 모든 종류의 수업에 적어도 한 번씩 참여한 학생에게 체험 과정 수료증을 발급하려 한다. 참여 기록에는 학생 코드와 수업 종류가 적혀 있다. 학생 코드는 영문 소문자 여섯 글자로 이루어지며, 코드가 같으면 같은 학생이다. 서로 다른 코드는 서로 다른 학생을 나타낸다. 한 학생의 기록이 여러 곳에 흩어져 있을 수 있고, 같은 학생과 같은 수업 종류로 이루어진 기록이 여러 번 나타날 수도 있다. 반복된 기록은 그 학생이 새로운 종류의 수업에 참여했다는 뜻이 아니다. 수료 여부는 참여 횟수의 합이 아니라 참여한 수업 종류로 판단한다. 예를 들어 수업이 세 종류라면 1번 수업에 세 번 참여한 학생은 수료하지 못한다. 반면 1번, 2번, 3번 수업에 각각 한 번 이상 참여했다면 다른 반복 기록의 수와 관계없이 수료한다. 참여 순서와 기록이 입력되는 순서는 수료 여부에 영향을 주지 않는다. 학원은 별도의 전체 학생 명단을 제공하지 않는다. 프로그램은 주어진 참여 기록에 등장한 학생들만 조사하면 된다. 모든 수업 종류에 참여하려면 적어도 하나의 기록이 필요하므로, 기록에 등장하지 않은 학생이 수료 명단에 포함되는 일은 없다. 참여 기록이 하나도 주어지지 않을 수도 있으며, 이 경우 수료한 학생은 없다. 수료 명단에는 같은 학생을 한 번만 적는다. 명단의 순서는 학생 코드의 사전 순으로 정하며, 영문 소문자의 순서는 a부터 z까지이다. 모든 코드는 길이가 같으므로 처음으로 다른 글자가 나타나는 위치에서 더 앞선 글자를 가진 코드가 먼저 온다. 참여 기록을 모두 확인하여 수료한 학생 수와 정렬된 학생 코드 목록을 구하는 프로그램을 작성한다.

입력

첫째 줄에 수업 종류의 수 K와 참여 기록의 수 M이 공백으로 구분되어 주어진다. K와 M은 정수이며 1 ≤ K ≤ 5, 0 ≤ M ≤ 30,000이다.
다음 M개의 줄에는 학생 코드 S와 수업 종류를 나타내는 정수 T가 공백으로 구분되어 주어진다. S는 영문 소문자 a부터 z까지로만 이루어진 길이 6의 문자열이며, 1 ≤ T ≤ K이다.
같은 학생 코드와 수업 종류의 조합이 여러 번 주어질 수 있다.

출력

첫째 줄에 수료한 학생 수 C를 출력한다. 다음 C개의 줄에 수료한 학생 코드를 사전 순으로 한 줄에 하나씩 출력한다. 수료한 학생이 없으면 첫째 줄에 0만 출력한다.

3 8
aaaaaa 1
bbbbbb 1
aaaaaa 2
aaaaaa 2
bbbbbb 3
aaaaaa 3
cccccc 2
bbbbbb 2

2
aaaaaa
bbbbbb

2 4
aaaaaa 1
aaaaaa 1
bbbbbb 2
cccccc 1

0

1 3
zzzzzz 1
abcdef 1
zzzzzz 1

2
abcdef
zzzzzz

출처: Devin.KR 자체 제작