\(N,M,T\) がいずれも小さいので，全探索して数えても間に合いそう． DFS によりすべて列挙する． このとき，取りこぼしと重複が無いようにする． 今回は起こらなかったが，仮に重複するのなら，その分を割ることにする．
実装
先に \(T\) 個の入れ物 \(v[i] \ (i \in T)\) を用意して，そこに人 \(i \in N \) を割り当てていく． 重複しないために， 空の \(v[i]\) が複数あってそれを使うときは， 一番 \(i\) の小さい物を使うというルールにする．
また，DFS で潜る前に変更した部分を， DFS の潜りから帰った後に戻す．
終了条件と遷移を分けて書くと楽． DFS の深さ \(i\) において，人 \(i \in N\) の割り当てを決める．
使っている記号，マクロ等 "https://ecsmtlir.hatenablog.com/entry/2022/12/23/131925"
int main() {
ll n, t, m ;
cin >> n >> t >> m;
vll a(m), b(m);
rep(i,m){
cin >> a[i] >> b[i];
a[i]--, b[i]--;
}
vvll v(t);
ll ans = 0;
auto f = [&](auto f, ll i = 0) -> void {
if(i == n){
rep(j,t) rep(k,m){
if(in(a[k], v[j]) && in(b[k], v[j])) return;
}
rep(j,t) if(v[j].size() == 0) return;
ans++;
return;
}
bool g = false;
rep(j,t) if(!g){
if(v[j].size() == 0) g = true;
v[j].push_back(i);
f(f, i+1);
v[j].pop_back();
}
};
f(f);
cout << ans << endl;
return 0;
}
