前言：

和模拟赛 T1 相同的 trick。

思路：

首先考虑两个人的决策都固定时（即 $k=n+1$）的答案。

比较套路地，把“恰好第 $i$ 局结束游戏”转化为“第 $i$ 局还没结束”再做个差分。那么问题就变成了每次可以选 $x_i,y_i$ 中的一个，每个点只能被选一次，$i$ 次操作后还未发生冲突的次数。

那么这就是 Angle Beats 2.0。在每个 $x_i,y_i$ 之间连一条无向边，就形成了若干个连通块，其中每个连通块的方案数都是独立的。

相当于求把点分配给边有几种分法。下面分类讨论连通块内边数和点数的关系。记边数为 $cnt$，点数为 $sz$。

• $cnt=sz-1$：形成的是一棵树。可以指定一个点不选，方案数为 $sz$。
• $cnt=sz$：形成的是一棵基环树。有两种分配的方向，因此方案数为 $2$。
• $cnt>sz$：显然无解。

乘起来即可。

再考虑有不确定决策时的情况。

相当于在原先若干个连通块的基础上，进行连边。

• 树和树连边：形成一棵树。
• 树上连边：形成一棵基环树。
• 树和基环树连边：形成一棵基环树。

而对答案产生影响的只有基环树的数量和树的点数的乘积。由于状态数不多，直接搜索即可。注意要加一些剪枝。

代码：

写得不太好，见谅。

/*
 * @Author: jianhe
 * @Date: 2026-01-12 08:56:26
 * @LastEditTime: 2026-01-12 11:32:13
 */
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define pb push_back
const ll N=55,base=233,mod=502424017;
ll n,k,x,y,res[N],ans[2],ct;
ll fa[N],sz[N],cnt[N];
multiset<ll> e;
// map<multiset<ll>,ll> mp[N];
unordered_map<ll,ll> mp[N];
ll getfa(ll x){return fa[x]==x?x:fa[x]=getfa(fa[x]);}
void hb(ll x,ll y){
    x=getfa(x),y=getfa(y);
    if(x==y) cnt[x]++;
    else fa[x]=y,cnt[y]+=cnt[x]+1,sz[y]+=sz[x];
}
ll get(multiset<ll> &e){
    ll res=0;
    for(auto it=e.begin();it!=e.end();it++) res=(res*base+*it)%mod;
    return res;
}
ll dfs(ll x,multiset<ll> &e,ll ct){
    if(x>n+1||!e.size()) return 0;
    ll tmp=get(e);
    if(mp[ct][tmp]) return mp[ct][tmp];
    ll res=0;multiset<ll> e2;e2=e;ll ttt=(1ll<<ct-1);
    ll p=1;for(auto it3=e.begin();it3!=e.end();it3++) p*=(*it3);
    ll lst=0;
    for(auto it=e.begin();it!=e.end();it++){
        if(*it==lst) continue;// 剪枝，跳过一些无用状态
        e2.erase(e2.find(*it));p/=*it;
        res=max(res,p*ttt*2-dfs(x+1,e2,ct));// 树上连边
        if(ct) res=max(res,p*ttt-dfs(x+1,e2,ct-1));// 树+基环树
        e2.insert(*it);auto it2=it;p*=*it;
        ll lst2=0;
        for(it2++;it2!=e.end();it2++){// 树+树
            if(*it2==lst2) continue;
            e2.erase(e2.find(*it)),e2.erase(e2.find(*it2));e2.insert(*it+*it2);
            p/=*it**it2,p*=*it+*it2;
            res=max(res,p*ttt-dfs(x+1,e2,ct-1));
            e2.erase(e2.find(*it+*it2));e2.insert(*it),e2.insert(*it2);
            p*=*it**it2,p/=*it+*it2;
            lst2=*it2;
        }
        lst=*it;
    }
    return mp[ct][tmp]=res;
}
int main(){
    ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    cin>>n>>k;res[0]=(1ll<<n+1);
    // ll st=clock();
    for(int i=1;i<=n;i++) fa[i]=i,sz[i]=1;
    for(int i=1;i<=k;i++){
        cin>>x>>y,hb(x,y);res[i]=(1ll<<n+1-i);
        for(int j=1;j<=n;j++)
            if(getfa(j)==j){
                if(cnt[j]>sz[j]) res[i]=0;
                else if(cnt[j]==sz[j]) res[i]*=2;
                else res[i]*=sz[j];
            }
        ans[i&1]+=res[i-1]-res[i];
    }
    for(int i=1;i<=n;i++)
        if(getfa(i)==i){
            if(cnt[i]==sz[i]) ct++;
            else e.insert(sz[i]);
        }
    if(!res[k]) cout<<ans[0]<<" "<<(1ll<<n+1)-ans[0];
    else{
        ans[k&1]+=dfs(k+1,e,ct+n+1-k);
        if(!(k&1)) cout<<ans[0]<<" "<<(1ll<<n+1)-ans[0];
        else cout<<(1ll<<n+1)-ans[1]<<" "<<ans[1];
    }
    // ll ed=clock();cerr<<"\n"<<(double)(ed-st)/CLOCKS_PER_SEC;
    return 0;
}