#P18686. This is not an Abnormal Team!

This is not an Abnormal Team!

This is not an Abnormal Team!

题目描述

愿一切回归正常, 愿所有收获皆可期待, 愿前途光明, 从此不再悲伤。

——(不是小青鱼)

XCPC 集训队中有 n1n_1 名男生和 n2n_2 名女生,其中有 mm 对男生与女生处于恋爱关系中。一人可以同时与多人处于恋爱关系中,但不会出现同性之间的恋爱关系。

小青鱼是集训队教练,他想把所有人分成若干支 XCPC 队伍,每支队伍最多 3 人。为了让队伍不是“不正常的”,如果一支队伍多于 1 人,那么其中至少有一名成员与队内其他所有成员都处于恋爱关系中。

然而,独自参加 XCPC 不如与队友一起参赛有趣,因此小青鱼希望单人队的数量尽量少。另外,如果一个人同时与另外两名队友处于恋爱关系中,这支队伍可能会不稳定。因此,在单人队数量已经最少的前提下,他还希望三人队的数量尽量少。

小青鱼急于找到一种分队方式。为了让一切回归正常,请帮助他完成分队,让队伍能够为冠军而战。XCPC 是他最喜欢的事业,请帮助他!

输入格式

第一行包含三个整数 n1,n2,mn_1,n_2,m(1≤n1,n2≤1051\le n_1,n_2\le10^5,1≤m≤2×1051\le m\le2\times10^5),分别表示男生人数、女生人数以及恋爱关系的数量。

接下来 mm 行,第 ii 行包含两个整数 ui,viu_i,v_i(1≤ui≤n11\le u_i\le n_1,1≤vi≤n21\le v_i\le n_2),表示第 uiu_i 名男生与第 viv_i 名女生处于恋爱关系中。

保证所有 (ui,vi)(u_i,v_i) 两两不同。输入只有一组数据;没有恋爱关系的人仍须分配到队伍中。男女分别编号,所以相同的数字编号可以组成一条合法关系。

输出格式

输出一行两个整数,依次表示最优方案中的单人队数量与三人队数量。先最小化第一个数,再在此前提下最小化第二个数。

样例输入

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 支三人队,另外两支为两人队。

原PDF中的样例分队示意图