ovo
Never gonna give you up~Never gonna let you down~
昨天 T2 求调捏qwq
得分 \(55\)，分别在 #3，#5，#7 wa 了。
//transport
#include<bits/stdc++.h>
#define N 1010
#define M 4010
using namespace std;
const long long mod=1e9+7;
long long qpow(long long base,int power){
long long ans=1;
for(;power;power>>=1,base=(base*base)%mod)
if(power&1) ans=ans*base%mod;
return ans;
}
int c[M],si[M];
long long f[M][M],g[M][M],w[M][M];
int path[N][N],d[N][N];
int cnt[M];
int to[M][2];
int siz[N];
bool vis[M];
struct edges{
int s,e,nex,id;
bool vi;
}ed[N<<1];
int pre[N],ti=1;
inline void add(int s,int e,int id){
ed[++ti]={s,e,pre[s],id,0};
pre[s]=ti;
return;
}
void dfs_a(int x,int fa){
siz[x]=1;
for(int i=pre[x];i;i=ed[i].nex){
if(ed[i].e==fa||ed[i].vi) continue;
dfs_a(ed[i].e,x);
siz[x]+=siz[ed[i].e];
}
return;
}
void dfs_b(int x,int fa,int S,int &ans){
for(int i=pre[x];i;i=ed[i].nex){
if(ed[i].e==fa||ed[i].vi) continue;
if((S-siz[ed[i].e])*siz[ed[i].e]==cnt[ed[i].id]) ans=i;
dfs_b(ed[i].e,x,S,ans);
}
return;
}
int init(int rt){
dfs_a(rt,0);
int ans=0;
dfs_b(rt,0,siz[rt],ans);
int s=ed[ans].s,e=ed[ans].e,x=ed[ans].id;
si[x]=siz[rt];
c[x]+=siz[rt]-1;
if(siz[s]<siz[e]) swap(s,e);
ed[ans].vi=1;
ed[ans^1].vi=1;
if(siz[rt]-siz[e]-1) to[x][0]=init(s);
if(siz[e]-1) to[x][1]=init(e);
c[x]+=c[to[x][0]]-si[to[x][0]]+1;
c[x]+=c[to[x][1]]-si[to[x][1]]+1;
return x;
}
long long fac[M],inv[M];
void inits(int m){
fac[0]=1;
for(int i=1;i<=m;i++) fac[i]=(fac[i-1]*i)%mod;
inv[m]=qpow(fac[m],mod-2);
for(int i=m-1;i>=0;i--) inv[i]=inv[i+1]*(i+1)%mod;
si[0]=1;
c[0]=0;
f[0][0]=1;
g[0][0]=1;
return;
}
inline long long C(int n,int m){
if(m>n) return 0;
return fac[n]*inv[m]%mod*inv[n-m]%mod;
}
void solve(int rt){
int x=to[rt][0],y=to[rt][1];
if(x) solve(x);
if(y) solve(y);
int a=c[x]-si[x]+1,b=c[y]-si[y]+1;
for(int i=0;i<=a;i++)
for(int j=0;j<=b;j++)
w[rt][i+j]=C(i+j,i)*C(c[x]-i+c[y]-j,c[x]-i)%mod*g[x][i]%mod*g[y][j]%mod;
int k=c[rt]-c[x]-c[y]-1;
for(int i=0;i<=a+b;i++) f[rt][i+k]=w[rt][i]*fac[k]%mod*C(k+i,i)%mod;
for(int i=a+b+k;i>=0;i--) g[rt][i]=(g[rt][i+1]+f[rt][i])%mod;
return;
}
int main(){
freopen("transport.in","r",stdin);
freopen("transport.out","w",stdout);
int n,m;
scanf("%d%d",&n,&m);
for(int i=2;i<=n;i++)
for(int j=1,ds;j<i;j++){
scanf("%d",&ds);
d[i][j]=ds;
d[j][i]=ds;
cnt[ds]++;
vis[ds]=1;
}
for(int i=1,s,e;i<=m;i++){
scanf("%d%d",&s,&e);
path[s][e]=i;
path[e][s]=i;
if(d[s][e]!=i) c[d[s][e]]++;
if(vis[i]){
add(s,e,i);
add(e,s,i);
}
}
inits(m);
int ma=init(1);
solve(ma);
printf("%lld",g[ma][0]);
}