## NOI '15 P1 - Automated Program Analyzer

View as PDF

Points: 12 (partial)
Time limit: 2.0s
Memory limit: 512M

Problem type

Let be variables. constraints of form or are given. The task asks for whether it is possible to assign values to the variables so that all constraints can be satisfied. For example, if the constraints are , then those constraints cannot be satisfied simultaneously.

#### Input Specification

The first line of the input is an integer representing the number of instances to solve. The instances are independent. For each instance, the first line is an integer representing the number of constraints to be satisfied. In the following lines, each line has three integers representing an equality/inequality constraint. If , the constraint shall be . If , the constraint shall be .

#### Output Specification

The output has lines. The -th line of the output is a string YES or NO. Output YES if the constraints in that instance can be satisfied and NO otherwise.

#### Sample Input 1

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

#### Sample Output 1

NO
YES

#### Sample Input 2

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

#### Sample Output 2

YES
NO

1
2
3
4
5
6
7
8
9
10