SPAM 개선

중복 사용자를 정리하는 놀라운 작업을 마친 후, 상사는 회사의 SPAM(System for Publishing Amazing Marketing) 개선에 대한 당신의 성과를 기대하고 있다.

마케팅 캠페인이 고객에게 매우 유용함에도 불구하고, 너무 많은 메시지가 전송되고 특정 고객이 같은 메시지를 여러 번 받는다는 불만이 고객 서비스에 접수되었다.

SPAM은 메일링 리스트를 기반으로 한다. 각 메일링 리스트는 고객 이메일 또는 다른 메일링 리스트로 구성된다. 고객 이메일은 언제든지 기존 메일링 리스트에 추가될 수 있지만, 메일링 리스트는 생성될 때만 기존의 여러 메일링 리스트에 추가될 수 있다. 여러 메일링 리스트를 동시에 생성할 수는 없다.

메시지가 메일링 리스트로 전송되면, 시스템은 리스트의 각 주소로 메시지를 보낸다. 리스트의 주소가 고객 이메일이면 해당 고객 이메일로 메시지가 전송되고, 주소가 메일링 리스트이면 그 메일링 리스트에 대해 과정이 시작된다.

개인정보 보호를 위해 다음 예에서 메일링 리스트와 고객 이메일은 정수로 표시된다. 1, 2, 3이 메일링 리스트이고 4, 5가 고객 이메일이라고 하자. 또한 메일링 리스트 1은 메일링 리스트 2와 3을 포함하고, 메일링 리스트 2는 고객 이메일 4와 5를 포함하며, 메일링 리스트 3은 고객 이메일 4와 메일링 리스트 2를 포함한다. 이제 메시지가 메일링 리스트 1로 전송된다고 하자. 이는 리스트가 위에서 설명한 대로 처리되고, 그다음 메일링 리스트 2와 3도 처리됨을 의미한다. 메일링 리스트 2가 처리될 때 메시지는 고객 이메일 4와 5로 전송된다. 메일링 리스트 3이 처리될 때 고객 이메일 4로 두 번째 메시지가 전송되고, 메일링 리스트 2가 다시 처리되어 고객 이메일 4로 세 번째 메시지가, 고객 이메일 5로 두 번째 메시지가 전송된다. 따라서 총 다섯 개의 메시지가 고객 이메일로 전송된다.

당신의 임무는 어떤 고객도 같은 메시지를 여러 번 받지 않도록 SPAM을 최적화하는 것이다. 첫 단계로, 상사는 개선 전후에 전송되는 메시지 수를 알고 싶어 한다. 위 예에서, 작업이 끝난 후에는 두 개의 메시지만 고객 이메일로 전송되어야 한다.

첫 번째 줄에는 두 정수 N과 L (2 ≤ N ≤ 2000, 1 ≤ L ≤ min(N − 1, 1000))이 주어지며, 각각 시스템의 주소 수와 메일링 리스트인 주소 수를 나타낸다. 주소는 1부터 N까지의 서로 다른 정수로 식별된다. 주소 1부터 L까지는 메일링 리스트이고, 나머지는 고객 이메일이다. i = 1, 2, . . . , L에 대해, 다음 L개의 줄 중 i번째 줄은 정수 K (1 ≤ K < N)와 K개의 서로 다른 정수 M1, M2, . . . , MK (1 ≤ Mi ≤ N for i = 1, 2, . . . , K)로 메일링 리스트 i를 설명하며, 이는 메일링 리스트가 K개의 주소 M1, M2, . . . , MK를 포함함을 나타낸다. 각 고객 주소는 적어도 하나의 메일링 리스트에 나타난다.

메시지가 메일링 리스트 1로 전송될 때, 개선 전후에 고객 이메일로 전송되는 메시지 수를 각각 나타내는 두 정수 B와 A를 한 줄에 출력한다. 이 수는 매우 클 수 있으므로, 109 + 7로 나눈 나머지를 출력한다.