C++

#include <cstdio>

#include <cstring>

using namespace std;

const int mod=1000003;

int N,M,grap[40][40],check[40],i_f_dp[20],n_f_dp,id=1;

int dt[66000];

int serch(int bm){

    if(bm==(1<<n_f_dp)-1)

        return 1;

    if(dt[bm]!=-1)

        return dt[bm];

    int is_end=1,return_=0;

    for(int i=1;i<=n_f_dp;i++){

        if((bm & 1<<(i-1))){

            continue;

        }

        int b=1;

        for(int j=1;j<=n_f_dp;j++){//error check j's bit==0

            if(grap[i_f_dp[i]][i_f_dp[j]]){

                if(!(bm & 1 << (j-1))){

                    b=0;

                    break;

                }

            }

        }

        if(b==0){

            continue;

        }

        int a=bm;

        a|=1<<(i-1);

        return_ = (return_ + serch(a))%mod;

    }

    return dt[bm] = return_;

}

 

int tnCr[40][40];

int nCr(int n,int r){

    if(n==r){

        return 1;

    }

    if(r==1){

        return n;

    }

    if(tnCr[n][r]!=0)

        return tnCr[n][r];

    return tnCr[n][r]=(nCr(n-1,r)+nCr(n-1,r-1))%mod;

}

void fill_i_f_dp(int n){

    check[n]=1;

    i_f_dp[id++]=n;

    for(int i=1;i<=N;i++){

        if(grap[n][i]||grap[i][n]){

            if(check[i]==0)

            fill_i_f_dp(i);

        }

    }

}

int main()

{

    scanf("%d %d",&N,&M);

    for(int i=0;i<M;i++){

        int a,b;

        scanf("%d %d",&a,&b);

        grap[a][b]=1;

    }

    for(int i=1;i<=N;i++){

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

            for(int k=1;k<=N;k++){

                if(grap[j][i]==0||grap[i][k]==0)

                    continue;

                if(grap[k][j]==1){

                    printf("0");

                    return 0;

                }

                grap[j][k]=1;

            }

        }

    }

    long long result=1,sum=0;

    for(int i=1;i<=N;i++){

        if(check[i]==1)

            continue;

        if(grap[i][i]==1){

            printf("0");

            return 0;

        }

        memset(i_f_dp,0,sizeof(i_f_dp));

        memset(dt,-1,sizeof(dt));

        n_f_dp=0;

        id=1;

        fill_i_f_dp(i);

        n_f_dp=id-1;

        sum+=n_f_dp;

        if(i!=1){

            int a=nCr(sum,n_f_dp)%mod;

            if(a!=0)

                result=result*a%mod;

        }

        int b=serch(0);

        if(b!=0)

            result=result*b%mod;

    }

    printf("%lld",result);

    return 0;

}