AAC2 - Atul and Aastha Chronicles 2

no tags 

Atul loves gifting choclates and Aastha loves eating them but excess of anything is bad and same goes for choclates. Eating all those chocolates has made Aastha overweight and she needs to watch her weight now. So she has to classify the chocolates based on their sugar content. She gave this task to Jaya. After completing the task Jaya is still not confident. She wants you to check whether her classification is correct or not. Basically if two chocolates have the same sugar level they are represented as a=b else they are represented as a!=b. You are given a list of binary relations, equalities and inequalities, like a = b, a != d, b = c etc. Your task is to output YES if the classification is correct , that you can satisfy all equalities and inequalities. Otherwise you should output NO.

Input

 

In the first line there is one integer T denoting the number of test cases. Description of T test cases follow. Each one have two integers N and K given in the first line denoting the number of variables and the number of relations between them for this test case. All variables are represented by integers in range [1, N]. K lines follow. Each of them is of the form "x1 R x2" where x1 and x2 are integers representing variables 
and R is either "=" or "!=" and denotes the kind of relation between these variables.

In the first line there is one integer T denoting the number of test cases. Description of T test cases follow. Each one have two integers N and K given in the first line denoting the number of variables and the number of relations between them for this test case. All variables are represented by integers in range [1, N]. K lines follow. Each of them is of the form "x1 R x2" where x1 and x2 are integers representing variables and R is either "=" or "!=" and denotes the kind of relation between these variables.

 

Output

Output exactly T lines. In i-th of them, output the answer to the i-th test case.

 

1<=N,K<=10^6

Example

Input:
2
2 2
1 = 2
1 != 2
3 2
1 = 2
2 != 3
Output:
NO
YES

hide comments
nadstratosfer: 2017-12-19 03:43:24

Visleck is correct! The chocolate story doesn't make sense, you need to query inequalities only on graph's current state!

2
3 3
1 = 2
2 != 3
3 = 1
3 4
1 = 2
2 != 3
3 = 1
2 != 3
---
YES
NO

Simes: 2017-10-14 17:26:00

@visleck
How can the answer be yes? Chocolates 1 and 5 have the same sugar level, as do chocolates 5 and 6. This mean chocolates 1 and 6 must also have the same sugar level, but there is the 1 != 6 relationship, so the data set is inconsistent.

If on the other hand, the problem is to verify each relationship with the data known up to that point, then the answer would be yes, but on my reading, that's not what the problem is asking for.

Last edit: 2017-10-14 20:33:54
visleck: 2017-08-03 21:29:48

@sushovan ans is YES

Sushovan Sen: 2016-06-23 09:56:03

what is expected output for
1
6 8
1 = 3
2 =4
5 = 6
1 != 4
1 != 6
2 != 3
2 != 6
1 = 5

Is it "NO"?

Dewang Sultania: 2016-04-20 00:04:10

@Blue.Mary updated sorry for the inconvinience

[Rampage] Blue.Mary: 2016-03-27 01:13:24

The range of N & K?


Added by:Dewang Sultania
Date:2016-03-24
Time limit:1s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ADA95 ASM32-GCC ASM32 ASM64 GAWK BASH BF C-CLANG CPP14-CLANG CLPS CLOJURE COBOL D-CLANG GOSU JS-MONKEY OBJC-CLANG OCAML
Resource:codemonk