Description

刁姹接到一个任务, 为税务部门调查一位商人的账本, 看看账本是不是伪造的. 账本上记录了 \(n\) 个月以来的收入情况, 其中第 \(i\) 个月的收入额为 \(a_i\). 当 \(a_i \gt 0\) 时表示这个月盈利 \(a_i\) 元, 当 \(a_i \lt 0\) 时表示这个月亏损 \(a_i\) 元. 所谓一段时间内的 总收入, 就是这段时间内每个月的收入额的总和.

刁姹的任务是秘密进行的, 为了调查商人的账本, 她只好跑到商人那里打工. 她趁商人不在 时去偷看账本, 可是她无法将账本偷出来, 每次偷看账本时她都只能看某段时间内账本上 记录的收入情况, 并且她只能记住这段时间内的总收入. 现在, 刁姹总共偷看了 \(m\) 次账本, 当然也就记住了 \(m\) 段时间内的总收入, 你的任务是根据记住的这些信息来判断账本是不是 假的.

Input

第一行为一个正整数 \(w\), 其中 \(w \lt 100\), 表示有 \(w\) 组数据, 即 \(w\) 个账本, 需要 你判断.

每组数据的第一行为两个正整数 \(n\) 和 \(m\), 分别表示对应的账本记录了多少个月的收入情况以及偷看了多少次账本.

接下来的 \(m\) 行表示刁姹偷看 \(m\) 次账本后记住的 \(m\) 条信息, 每条信息占一行, 有三个整数 \(s, t, v\), 表示从第 \(s\) 个月到第 \(t\) 个月 (包含第 \(t\) 个月) 的总收入为 \(v\), 这里假设 \(s \leq t\).

Output

包含 \(w\) 行, 每行是 true 或 false, 其中第 \(i\) 行为 true 当且仅当第 \(i\) 组数据, 即第 \(i\) 个账本不是假的; 第 \(i\) 行为 false 当且仅当第 \(i\) 组数据, 即第 \(i\) 个账本是假的.

Sample Input

2
3 3
1 2 10
1 3 -5
3 3 -15
5 3
1 5 100
3 5 50
1 2 51

Sample Output

true
false

Data Range

对于所有数据, 满足:\(n \lt 100, m \lt 1000\)

Explanation

每一次合并 \(x-1, y\), 记偏移量为 \(z\), 维护一个并查集.

做法有点像差分约束系统, 但是由于差分约束系统维护的是大小关系, 需要有一定的宽容度, 而此处维护的是等于关系, 所以可以直接上并查集.

如果突然发现合并时出现偏移量异常, 则这组数据是假的, 否则为真.

Source Code


#include <iostream>
#include <cstdlib>
#include <cstdio>

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

class DisjointSet
{
public:
    int n, par[maxn], dist[maxn];
    int find(int p)
    {
        if (par[p] == p)
            return p;
        int q = find(par[p]);
        dist[p] += dist[par[p]];
        par[p] = q;
        return q;
    }
    bool join(int p, int q, int dis)
    {
        int x = find(p), y = find(q);
        if (x == y) {
            if (dist[q] - dist[p] != dis)
                return false;
        } else {
            par[x] = y;
            dist[x] = dist[q] - dist[p] - dis;
        }
        return true;
    }
    void init(int n)
    {
        this->n = n;
        for (int i = 0; i <= n; i++)
            dist[i] = 0, par[i] = i;
        return ;
    }
} djs;

int T, n, m;

int main(int argc, char** argv)
{
    scanf("%d", &T);
    for (int idx = 1; idx <= T; idx++) {
        scanf("%d%d", &n, &m);
        djs.init(n);
        bool flag = true;
        for (int i = 1, x, y, z; i <= m; i++) {
            scanf("%d%d%d", &x, &y, &z);
            flag &= djs.join(x - 1, y, z);
        }
        printf("%s\n", flag ? "true" : "false");
    }
    return 0;
}