F.A.Qs Home Discuss ProblemSet Status Ranklist Contest 入门OJ LoginRegister 捐赠本站
Notice:1:注册本OJ方式请见https://www.lydsy.com/JudgeOnline/wttl/thread.php?tid=5671 2:请不要在讨论区中发空白主题帖。
Problem 4307. -- Maishroom & Class

4307: Maishroom & Class

Time Limit: 25 Sec  Memory Limit: 256 MB
Submit: 18  Solved: 9
[Submit][Status][Discuss]

Description

Maishroom在全国各地开设了OI辅导班,比如四川班等等。Maishroom的辅导班有两种讲师,也就是助教(主要是机房里其他小伙伴)和教师(主要是Maishroom自己)。当一个助教去打vp的时候,显然他就不能授课了,不过没有关系,因为只是助教。当一个教师A(例如Maishroom)去打(看)vp(片)的时候,他需要找另一个讲师B来代替自己的授课。如果B也是教师,他也需要另一个讲师C来代替自己,依次类推。
现在我们需要知道:
1)有多少个讲师不能去打vp。
2)有多少对讲师(A,B),单独地,每个人都可以去打vp,然而不能一起打(开)vp(黑)。

Input

第一行,两个整数N, K。分别表示:辅导班里的讲师数与教师数。
约定:编号1~K的为教师,编号K+1~N的为助教。
以下K行,表示各个教师可以被哪些讲师替代。
第i+1行,第一个整数Di,代表可代替教师i的讲师数,之后Di个整数为其编号。

Output

一行,两个整数。分别代表两问的答案。

Sample Input

7 5
2 6 7
1 7
2 2 7
1 5
1 4

Sample Output

2 3

HINT

教师4, 5不能去打vp。因为剩下一个人不能做两个人的事。

当教师2, 3开黑的时候,讲师7不可能同时顶替他们两个人。

事实上,(2, 3), (2, 7), (3, 7)都满足,可以单独vp,不能一起开黑。

对于100%的数据:1KN5,0001M20,000

Source

[Submit][Status][Discuss]

HOME Back