왕실 금고

먼 옛날 어느 왕국에서 왕실 금고가 점점 비어 갔다. 뇌물을 막기 위해 왕은 재무 관청을 개편하여 관리들이 반드시 짝을 이루어 일하도록 했다. 각 짝은 한 관리와 그 관리의 직속 부하 정확히 한 명으로 이루어진다.

관청은 수석 재무관이 이끈다. 수석 재무관은 오직 왕에게만 보고하고, 그 외 모든 관리는 정확히 한 명의 상관에게 보고하며 0명 이상의 직속 부하를 둘 수 있다. 각 관리는 최대 한 개의 짝에만 속할 수 있으며, 어떤 관리는 짝을 이루지 않고 남을 수도 있다.

관청의 조직 구조가 주어질 때, 만들 수 있는 짝의 최대 개수 M과, 정확히 M개의 짝을 이루는 서로 다른 방법의 수를 구하여라. 두 방법은 짝의 집합이 다르면 서로 다른 것으로 센다.

첫째 줄에 관리의 수 N이 주어진다($1 \le N \le 1000$). 관리들은 $1$부터 $N$까지의 서로 다른 번호를 가지며, 수석 재무관의 번호는 $1$이다.

다음 N개의 줄은 각각 한 관리를 설명한다. 각 줄에는 그 관리의 번호, 직속 부하의 수 K($0 \le K \le 999$), 그리고 K명의 부하 번호가 공백 하나로 구분되어 주어진다. 각 관리는 항상 자신의 상관보다 뒤에 설명된다.

두 줄을 출력한다. 첫째 줄에는 만들 수 있는 짝의 최대 개수 M을 출력한다. 둘째 줄에는 위 규칙에 따라 정확히 M개의 짝을 이루는 서로 다른 방법의 수를 출력한다. 이 수는 매우 커질 수 있다.