#P18686. This is not an Abnormal Team!
This is not an Abnormal Team!
This is not an Abnormal Team!
题目描述
愿一切回归正常, 愿所有收获皆可期待, 愿前途光明, 从此不再悲伤。
——(不是小青鱼)
XCPC 集训队中有 名男生和 名女生,其中有 对男生与女生处于恋爱关系中。一人可以同时与多人处于恋爱关系中,但不会出现同性之间的恋爱关系。
小青鱼是集训队教练,他想把所有人分成若干支 XCPC 队伍,每支队伍最多 3 人。为了让队伍不是“不正常的”,如果一支队伍多于 1 人,那么其中至少有一名成员与队内其他所有成员都处于恋爱关系中。
然而,独自参加 XCPC 不如与队友一起参赛有趣,因此小青鱼希望单人队的数量尽量少。另外,如果一个人同时与另外两名队友处于恋爱关系中,这支队伍可能会不稳定。因此,在单人队数量已经最少的前提下,他还希望三人队的数量尽量少。
小青鱼急于找到一种分队方式。为了让一切回归正常,请帮助他完成分队,让队伍能够为冠军而战。XCPC 是他最喜欢的事业,请帮助他!
输入格式
第一行包含三个整数 (,),分别表示男生人数、女生人数以及恋爱关系的数量。
接下来 行,第 行包含两个整数 (,),表示第 名男生与第 名女生处于恋爱关系中。
保证所有 两两不同。输入只有一组数据;没有恋爱关系的人仍须分配到队伍中。男女分别编号,所以相同的数字编号可以组成一条合法关系。
输出格式
输出一行两个整数,依次表示最优方案中的单人队数量与三人队数量。先最小化第一个数,再在此前提下最小化第二个数。
样例输入
5 6 10
1 1
2 1
2 2
3 2
4 2
4 3
5 3
5 4
5 5
5 6
样例输出
1 2
样例说明
原题给出的一种最优分队如下:实线表示队伍内的关系,虚线表示其他恋爱关系,红色竖线分隔不同队伍。共有 1 支单人队、2 支三人队,另外两支为两人队。
