第一问

考虑对补图跑二分图带权最大独立集。

这一部分可以通过一个人类智慧的网络最大流实现。

0           ->    1  - n        101

1   -   n   ->   n+1 - 2n       inf, 当且仅当补图上有该边时连边

n+1 -  2n   ->    2n+1          100

跑从源点 $S=0$ 到汇点 $T=2n+1$ 的最大流，即最小割。

然后就可以计算出男生、女生人数了。

$101$ 与 $100$ 是为了保证男生数目尽量多。

如下图是样例。

---

第二问

记 $n$ 个男生，$m$ 个女生的该图中任意挑 $k$ 条边的方案数为 $f_{n,m}=\binom{nm}{k}$，其中符合题目条件的选法有 $g_{n,m}$ 种。

则显然有

$$f_{n,m}=\sum_{a,b}\binom na\binom mbg_{a,b}$$

由二维二项式反演，我们得到

$$g_{n,m}=\sum_{a,b}\binom na\binom mb(-1)^{n+m-a-b}f_{a,b} $$

即答案为

$$\sum_{a,b}\binom na\binom mb\binom{ab}k(-1)^{n+m-a-b} $$

直接做就好了。

---

Code

码头去掉了。

Dinic D;
bol E[55][55];
modint C[5005][5005];
int main()
{
#ifdef MYEE
    freopen("QAQ.in","r",stdin);
#endif
    uint n,k,m;
    scanf("%u%u%u",&n,&k,&m);
    D.build((n+1)<<1);
    for(uint i=1;i<=n;i++)D.insert(0,i,101),D.insert(i+n,n<<1|1,100);
    for(uint i=1;i<=n;i++)for(uint j=1;j<=n;j++)E[i][j]=true;
    while(m--){uint u,v;scanf("%u%u",&u,&v),E[u][v]=false;}
    for(uint i=1;i<=n;i++)for(uint j=1;j<=n;j++)if(E[i][j])D.insert(i,j+n,-1);
    ullt w=201llu*n-D.run(0,n<<1|1);
    uint a=w%100;
    uint b=w/100-a;
    printf("%u %u\n",a,b);
    AnyMod::ChgMod(19921228);
    C[0][0]=1;
    for(uint i=1;i<=5000;C[i][0]=1,i++)for(uint j=1;j<=i;j++)C[i][j]=C[i-1][j-1]+C[i-1][j];
    modint ans;
    for(uint i=0;i<=a;i++)for(uint j=0;j<=b;j++)
        ((i^j)&1)?ans-=C[a][i]*C[b][j]*C[(a-i)*(b-j)][k]:ans+=C[a][i]*C[b][j]*C[(a-i)*(b-j)][k];
    ans.println();
    return 0;
}