Description

在实现程序自动分析的过程中, 常常需要判定一些约束条件是否能被同时满足.

考虑一个约束满足问题的简化版本: 假设 \(x_1, x_2, x_3, \ldots\) 代表程序中出现的 变量, 给定 \(n\) 个形如 \(x_i = x_j\) 或 \(x_i \neq x_j\) 的变量相等/不等的约束条件, 请判定是否可以分别为每一个变量赋予恰当的值, 使得上述所有约束条件同时被满足. 例如, 一个问题中的约束条件为:\(x_1 = x_2, x_2 = x_3, x_3 = x_4, x_1 \neq x_4\), 这些 约束条件显然是不可能同时被满足的, 因此这个问题应判定为不可被满足.

现在给出一些约束满足问题, 请分别对它们进行判定.

Input

输入文件的第 \(1\) 行包含 \(1\) 个正整数 \(T\), 表示需要判定的问题个数. 注意这些问题 之间是相互独立的.

对于每个问题, 包含若干行:

第 \(1\) 行包含 \(1\) 个正整数 \(n\), 表示该问题中需要被满足的约束条件个数.

接下来 \(n\) 行, 每行包括 \(3\) 个整数 \(i, j, e\), 描述 \(1\) 个相等/不等的约束条件, 相邻整数之间用单个空格隔开. 若 \(e = 1\), 则该约束条件为 \(x_i = x_j\); 若 \(e = 0\), 则该约束条件为 \(x_i \neq x_j\).

Output

输出文件包括 \(T\) 行.

输出文件的第 \(k\) 行输出一个字符串 YES 或者 NO (不包含引号, 字母全部大写),YES 表示输入中的第 \(k\) 个问题判定为可以被满足,NO 表示不可被满足.

Sample Input

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

Sample Output

NO
YES

Data Range

对于所有数据, 满足:\(1 \leq n \leq 10^6, 1 \leq i, j \leq 10^9\)

Explanation

此题可以强行离线, 先搞定所有的相等条件, 然后判断不等条件是否可以满足.

当然也可以用某年 NOIP 的 “食物链” 的做法维护并查集偏移量, 也就是强制在线的做法, 虽然这种做法代码量并不会高出多少.

由于本蒟蒻很懒所以就只写了强行离线的做法.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <set>
#include <algorithm>

using namespace std;
typedef long long lli;
const int maxn = 2000100;

class DisjointSet
{
public:
    int par[maxn];
    int n;
    int find(int p)
    {
        if (par[p] == p)
            return p;
        return par[p] = find(par[p]);
    }
    void join(int p, int q)
    {
        p = find(p);
        q = find(q);
        par[p] = q;
        return ;
    }
    void init(int n)
    {
        this->n = n;
        for (int i = 1; i <= n; i++)
            par[i] = i;
        return ;
    }
} djs;

int T, n;
int dat[maxn][3];
set<int> st;
int arr[maxn];

int search(int val)
{
    return lower_bound(arr + 1, arr + arr[0] + 1, val) - arr;
}

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        scanf("%d", &n);
        st.clear();
        for (int i = 1; i <= n; i++) {
            scanf("%d%d%d", &dat[i][0], &dat[i][1], &dat[i][2]);
            st.insert(dat[i][0]);
            st.insert(dat[i][1]);
        }
        // Concatencating items, in order
        arr[0] = 0;
        for (set<int>::iterator i = st.begin(); i != st.end(); i++)
            arr[++arr[0]] = *i;
        // Joining items (forced offline)
        djs.init(arr[0]);
        for (int i = 1; i <= n; i++) if (dat[i][2] == 1) {
            int x = search(dat[i][0]),
                y = search(dat[i][1]);
            djs.join(x, y);
        }
        // Checking if correct
        bool correct = true;
        for (int i = 1; i <= n; i++) if (dat[i][2] == 0) {
            int x = search(dat[i][0]),
                y = search(dat[i][1]);
            x = djs.find(x);
            y = djs.find(y);
            if (x == y) {
                correct = false;
                break;
            }
        }
        printf("%s\n", correct ? "YES" : "NO");
    }
    return 0;
}