描述

在实现程序自动分析的过程中，常常需要判定一些约束条件是否能被同时满足。
考虑一个约束满足问题的简化版本：假设 x1,x2,x3,…x1,x2,x3,… 代表程序中出现的变量，给定 nn 个形如 xi=xjxi=xj 或 xi≠xjxi≠xj 的变量相等/不等的约束条件，请判定是否可以分别为每一个变量赋予恰当的值，使得上述所有约束条件同时被满足。例如，一个问题中的约束条件为：x1=x2x1=x2，x2=x3x2=x3，x3=x4x3=x4，x1≠x4x1≠x4，这些约束条件显然是不可能同时被满足的，因此这个问题应判定为不可被满足。
现在给出一些约束满足问题，请分别对它们进行判定。

输入格式

输入文件的第 11 行包含 11 个正整数 tt，表示需要判定的问题个数。注意这些问题之间是相互独立的。
对于每个问题，包含若干行：
第 11 行包含 11 个正整数 nn，表示该问题中需要被满足的约束条件个数。
接下来 nn 行，每行包括 33 个整数 i,j,ei,j,e，描述 11 个相等/不等的约束条件，相邻整数之间用单个空格隔开。若 e=1e=1，则该约束条件为 xi=xjxi=xj；若 e=0e=0，则该约束条件为 xi≠xjxi≠xj。

输出格式

输出文件包括 tt 行。
输出文件的第 kk 行输出一个字符串 “YES” 或者 “NO”（不包含引号，字母全部大写），“YES” 表示输入中的第 kk 个问题判定为可以被满足，“NO” 表示不可被满足。

样例一

input

2
2
1 2 1
1 2 0
2
1 2 1
2 1 1

output

NO
YES

explanation

在第一个问题中，约束条件为：x1=x2,x1≠x2x1=x2,x1≠x2。这两个约束条件互相矛盾，因此不可被同时满足。
在第二个问题中，约束条件为：x1=x2,x2=x1x1=x2,x2=x1。这两个约束条件是等价的，可以被同时满足。

样例二

input

2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0

output

YES
NO

explanation

在第一个问题中，约束条件有三个：x1=x2x1=x2，x2=x3x2=x3，x3=x1x3=x1。只需赋值使得 x1=x2=x3x1=x2=x3，即可同时满足所有的约束条件。
在第二个问题中，约束条件有四个：x1=x2x1=x2，x2=x3x2=x3，x3=x4x3=x4，x1≠x4x1≠x4。由前三个约束条件可以推出 x1=x2=x3=x4x1=x2=x3=x4，然而最后一个约束条件却要求 x1≠x4x1≠x4，因此不可被满足。

样例三

见样例数据下载。

限制与约定

时间限制：2s2s
空间限制：512MB
题目其实就是求是否一对点会有两种情况出现，如果有，则输出NO，没有输出YES，那么我们就要维护一个集合，则我们就要用到并查集。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int fa[1000005], a[1000005], h[1000005];
struct qer
{
	int a, id;
}p[2000010];
bool cmp(qer a, qer b)
{
	return a.a < b.a;
}
int find(int x)
{
	return fa[x] == x ? x : fa[x] = find(fa[x]);
}
int main()
{
	int t;
	cin >> t;
	while (t--)
	{
		int n;
		cin >> n;
		for (int i = 1; i <= n; i++)
		{
			scanf("%d%d%d", &p[i*2-1].a, &p[i*2].a, &a[i]);
			p[i*2-1].id = i*2-1, p[i*2].id = i*2;
		}
		sort(p + 1, p + n*2 + 1, cmp);
		int k = 0;
		for (int i = 1; i <= n*2; i++)
		{
			if (p[i].a != p[i-1].a)
				k++;
			h[p[i].id] = k;
			fa[i] = i;
		}
		for (int i = 1; i <= n; i++)
		{
			if (a[i] == 1)
			{
				int fx = find(h[i*2-1]);
				int fy = find(h[i*2]);
				if (fx != fy)
					fa[fx] = fy;
			}
		}
		int sp = 0;
		for (int i = 1; i <= n; i++)
		{
			if (a[i] == 0)
			{
				int fx = find(h[i*2-1]);
				int fy = find(h[i*2]);
				if (fx == fy)
				{
					sp = 1;
					break;
				}
			}
		}
		if (sp)
			puts("NO");
		else
			puts("YES");
	}
	return 0;
}