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.

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