1575번 - 졸업

세준이는 형택 대학교의 학생 상담자이다. 형택 대학교의 졸업 조건은 복잡하다. 졸업 조건은 학생마다 다르다. 졸업 조건은 다음과 같은 형태를 가지고 있다. 1, 2, 3, 4중 2개의 수업을 들어라. 학생들은 이러한 졸업 조건을 N개 가지고 있다. N개를 모든 충족시켜야 졸업할 수 있다.

그런데, 갑자기 형택 대학교의 졸업 조건이 바뀌었다. 어떤 졸업 조건을 충족시킬 때 사용한 수업은, 다른 졸업 조건을 충족시킬 수 없는 것이다.

예를 들어서, “1, 2, 3중 2개의 수업을 들어라“, ”3, 4, 5중 2개의 수업을 들어라“가 있을 때, 첫 번째 조건을 충족시키는 수업이 1, 3이면, 두 번째 조건을 충족시킬 때, 3은 이용되어서 안되는 것이다.

따라서, 졸업이 다가워져서 혼란스러워진 학생들은 세준이에게 자주 찾아오기 시작했다. 세준이는 학생들이 자기를 찾아오지 않고서도 몇 개의 수업을 들어야 되는지 알 수 있게 하기 위해서 프로그램을 하나 작성했다.

정문이가 현재 들은 수업과, 졸업 조건이 주어질 때, 그 학생이 졸업하기 위해서 들어야하는 최소 수업의 개수와, 어떤 수업을 들어야 하는지 구하는 프로그램을 작성하시오.

수업은 숫자 하나로 표시되며, 1보다 크거나 같고, 100보다 작거나 같은 수 하나이다.

첫째 줄에 정문이가 들은 수업의 개수가 주어진다. 이 수는 0보다 크거나 같고, 100보다 작거나 같다. 둘째 줄에는 정문이가 들은 수업이 공백을 사이에 두고 주어진다. 만약 정문이가 들은 수업이 없을 때는, 이 줄은 빈 줄이다. 셋째 줄에는 정문이의 졸업 조건의 개수 N이 주어진다. 이 수는 1보다 크거나 같고 100보다 작거나 같다. 넷째 줄부터 N개의 줄에는 정문이의 졸업 조건이 한 줄에 하나씩 주어진다. 졸업 조건은 다음과 같은 형태로 주어진다. 첫 번째 숫자는 그 조건에 나타나는 수업의 개수 중 몇 개의 수업을 들어야 하는지가 주어진다. 두 번째 숫자는, 그 조건에 나타나는 수업의 개수이다. 세 번째 숫자부터는 수업의 번호가 주어진다. 예를 들어서, 1, 2, 3, 4중 2개의 수업을 들어라는 2 4 1 2 3 4와 같이 주어진다. 첫 번째 숫자와 두 번째 숫자는 100보다 작거나 같은 자연수이다. 또, 중복되는 졸업 조건은 없다.

첫째 줄에 정문이가 들어야 하는 수업의 개수를 출력한다. 만약 수업의 개수가 여러 개일 경우에는 수업의 개수가 가장 작은 것을 출력한다. 둘째 줄에는 정문이가 어떤 수업을 들어야 하는지 공백을 사이에 두고 출력한다. 가장 적은 수의 수업의 개수가 여러 개일 경우에는 이 수열이 사전 순으로 앞서는 것을 출력한다. 1, 2, 3, 4는 1, 2, 3, 5보다 사전 순으로 앞선다. 만약 어떻게 해도 졸업을 할 수 없을 때는, 첫째 줄에 -1을 출력한다. 또, 수업을 여러 번 들을 수는 없다.

이미 1을 들었기 때문에 첫 번째 조건을 충족시킬 때, 2를 사용하고, 두 번째 조건을 충족시킬 때 3,4를 사용한다.