GRAPHTRE Editorialist

#include <bits/stdc++.h>

using namespace std;

const int MX = 5005 , MOD = 1000000007;

vector < int > v[MX];

int T , n , m;

pair < int , int > arr[MX];

int dp[MX][MX] , val[MX] , tot[MX][MX];

int main(){
    scanf("%d",&T);
    while(T--){

        scanf("%d %d",&n,&m);

        for(int j = 0 ; j <= n ; j++){
            v[j].clear();
            for(int i = 0 ; i <= n ; i++){
                dp[j][i] = 0;
                tot[j][i] = 0;
            }
        }

        for(int j = 1 ; j <= n ; j++){
            scanf("%d",&arr[j].first);
            val[j] = arr[j].first;
            arr[j].second = j;
        }

        for(int j = 1 ; j <= m ; j++){
            int a , b;
            scanf("%d %d",&a,&b);
            v[a].push_back(b);
            v[b].push_back(a);
        }

        sort(arr+1 , arr+1+n);
        reverse(arr+1 , arr+1+n);

        dp[0][0] = 1;

        for(int nodes = 1 ; nodes <= n ; nodes++){

            int bigger = 0;

            int node = arr[nodes].second;

            for(auto nxt : v[node])
                if(val[nxt] > val[node])
                    ++bigger;

            for(int trees = 1 ; trees <= nodes ; trees++){

                // ways of constructing [trees] trees with first [nodes] nodes

                //add our new node as new root

                dp[nodes][trees] = dp[nodes-1][trees-1];

                //add it to some other parent

                dp[nodes][trees] += (1ll * bigger * dp[nodes - 1][trees])%MOD; dp[nodes][trees] %= MOD;



                // in case of adding new root we will have same respects and we add our node value to each single way

                tot[nodes][trees] = (1ll * tot[nodes - 1][trees - 1] + 1ll * val[node] * dp[nodes - 1][trees - 1])%MOD;

                // in case of connecting it to some parent the sum of respects will remain the same except that for each way we can construct new forests
                // so we need to multiply the total respects

                tot[nodes][trees] += (1ll * tot[nodes - 1][trees] * bigger)%MOD;


                tot[nodes][trees] %= MOD;




            }

        }

        for(int j = 1 ; j <= n ; j++){

            cout<<tot[n][j]<<' ';

        }

        cout<<endl;
    }

}