记录编号	202548	评测结果	AAAAAAAAAA
题目名称	[SYOI 2015] Asm_Def三角形	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	0.016 s
提交时间	2015-11-01 14:16:07	内存使用	6.49 MiB

/***********************************************************************/
/**********************By Asm.Def-Wu Jiaxin*****************************/
/***********************************************************************/
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <cctype>
#include <algorithm>
using namespace std;
#define SetFile(x) ( freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) );
#define UseFREAD
#ifdef UseFREAD
#define getc() *(file_ptr++)
#define FreadLenth 5000000
char CHARPOOL[FreadLenth], *file_ptr = CHARPOOL;
#else
#define getc() getchar() 
#endif
#ifdef DEBUG
#include <ctime>
#endif
template<class T>inline void getd(T &x){
	char ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')ch = getc(), neg = true;
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/***********************************************************************/
const int maxn = 100003, mod = 998244353;
typedef long long LL;

int N, M, f[maxn << 1], info[maxn], cnt, tot;
bool known[maxn], val[maxn], info_v[maxn];

int find(int x){return f[x] == x ? x : f[x] = find(f[x]);}
inline void Link(int u, int v){f[u] = v;f[find(u + N)] = find(v + N);}
inline void Cut(int u, int v){f[find(u + N)] = v;f[find(v + N)] = u;}

inline bool init(){
	int i, u, v, opt;
	getd(N), getd(M);
	tot = N - 1;
	for(i = 1;i <= (N << 1);++i)f[i] = i;
	while(M--){
		getd(opt), getd(u), getd(v);
		if(u == 1){info[cnt] = v, info_v[cnt++] = opt;continue;}
		if(v == 1){info[cnt] = u, info_v[cnt++] = opt;continue;}
		u = find(u), v = find(v);
		if(opt){
			if(u == v)return false;
			if(find(u + N) == v)continue;
			Cut(u, v);
			--tot;
		}
		else {
			if(find(u + N) == v)return false;
			if(u == v)continue;
			Link(u, v);
			--tot;
		}
	}
	for(i = 0;i < cnt;++i){
		u = find(info[i]);
		if(known[u]){
			if(val[u] != info_v[i])return false;
			continue;
		}
		known[u] = true;
		val[u] = info_v[i];
		--tot;
	}
	return true;
}

inline int powmod(int n){
	int a = 2, ans = 1;
	while(n){
		if(n & 1)ans = (LL)ans * a % mod;
		a = (LL)a * a % mod;
		n >>= 1;
	}
	return ans;
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#elif !defined ONLINE_JUDGE
	SetFile(tria);
#endif

#ifdef UseFREAD
	fread(file_ptr, 1, FreadLenth, stdin);
#endif

	if(init())printf("%d\n", powmod(tot));
	else puts("0");

#ifdef DEBUG
	printf("\n%.3lf sec \n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}