记录编号	205037	评测结果	AAAAAAAWWA
题目名称	[SYOI 2015] Asm_Def三角形	最终得分	80
用户昵称	lxtgogogo	是否通过	未通过
代码语言	C++	运行时间	0.088 s
提交时间	2015-11-04 19:49:02	内存使用	1.31 MiB

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<iomanip>
#include<queue>
#include<cstdlib>
using namespace std;
 
const int mod=998244353;
const int r=100000;
int n=0,m=0,ans=0;
int x[r+10]={},y[r+10]={},f[r+10]={};
int a[10][10]={};
int bian[25][2]={},len=0;
bool ff[25]={};

bool check(){
	bool flag=true;
	for(int i=1;i<=n-2;i++)
	{
		for(int j=i+1;j<=n-1;j++)
		{
			for(int k=j+1;k<=n;k++)
			{
				int t=a[i][j]+a[k][j]+a[i][k];
				if(a[i][j]==2)	t-=2;
				if(a[k][j]==2)	t-=2;
				if(a[i][k]==2)	t-=2;
				if(t==2 || t==0)	{flag=false;break;}
			}
			if(!flag)	break;
		}
		if(!flag)	break;
	}
	return flag;
}
void dfs(int k){//k表示第几条边
	if(k>len)	return ;
	int xx=bian[k][0];
	int yy=bian[k][1];
	a[xx][yy]=1;
	a[yy][xx]=1;
	if(check())	ans++;
	dfs(k+1);//cut
	a[xx][yy]=0;
	a[yy][xx]=0;
	dfs(k+1);//not cut
}
long long fastmi(int n){
	long long ans=1,re=2;
	while(n)
	{
		if(n%2==1)	ans=ans*re%mod;
		n>>=1;
		re=re*re%mod;
	}
	return ans;
}
void work(){
	cout<<0<<endl;
}
int main(){
	freopen("tria.in","r",stdin);
	freopen("tria.out","w",stdout);
	
	cin>>n>>m;
	for(int i=1;i<=m;i++)
		scanf("%d%d%d",&f[i],&x[i],&y[i]);
	if(n<=2)	cout<<0<<endl;
	else
	{
		if(m==0)
		{
			long long ans=fastmi(n-1);
			cout<<ans<<endl;
		}
		else if(n<=7)
		{
			memset(a,0,sizeof(a));
			for(int i=1;i<=m;i++)
			{
				int t=0;
				if(f[i]==0)	t=1;
				else	t=2;
				a[x[i]][y[i]]=t;
				a[y[i]][x[i]]=t;
			}
			for(int i=1;i<n;i++)
				for(int j=i+1;j<=n;j++)
				{if(a[i][j]==0)	{bian[++len][0]=i;bian[len][1]=j;}}
			dfs(1);
			cout<<ans<<endl;
		}
		else
		{
			work();
		}
	}
	
	fclose(stdin);fclose(stdout);
	return 0;
}