#N. 程序自动分析

    Type: Default 1000ms 256MiB

程序自动分析

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

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

考虑一个约束满足问题的简化版本:假设x1, x2, x3, ...代表程序中出现的变量,给定 n 个形如 xi = xj 或 xi != xj的变量相等/不等的约束条件,请判定是否可以分别为每一个变量赋予恰当的值,使得上述所有约束条件同时被满足。例如,一个问题中的约束条件为:x1 = x2 ,x2=x3, x3 = x4, x4 != x1,这些约束条件显然是不可能同时被满足的,因此这个问题应判定为不可被满足。

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

数据似乎有点问题,部分AC代码过不了,之后会全部重测,给大家造成麻烦了

数据更新 by mibbp

Format

Input

输入的第一行包含一个正整数 tt,表示需要判定的问题个数。注意这些问题之间是相互独立的。

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

第一行包含一个正整数 nn,表示该问题中需要被满足的约束条件个数。接下来 n 行,每行包括三个整数 i,j,e,描述一个相等/不等的约束条件,相邻整数之间用单个空格隔开。若 e=1,则该约束条件为xi = xj, 若e=0,则该约束条件为xi != xj

Output

输出包括 t 行。

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

Samples

2
2
1 2 1
1 2 0
2
1 2 1
2 1 1
NO
YES
2
3
1 2 1
2 3 1
3 1 1
4
1 2 1
2 3 1
3 4 1
1 4 0
YES
NO

Hint

Limitation

1s, 1024KiB for each test case.

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45