C. Crooked Cycles
time limit per test
3 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Mr. Nežmah has a peculiar taste in triples. He likes $$$m$$$ unordered triples of pairwise distinct numbers $$$(a_i, b_i, c_i)$$$.

A cycle of length $$$k$$$ is a sequence of (not necessarily distinct) numbers $$$v_1, \ldots, v_k$$$ where every three consecutive numbers form a triple Nežmah likes, as well as $$$(v_{k-1}, v_k, v_1)$$$ and $$$(v_k, v_1, v_2)$$$.

A cycle is crooked if its length is not divisible by 3. Check whether there exists a crooked cycle.

Input

The first line contains a single integer $$$t$$$ ($$$1 \leq t \leq 2 \cdot 10^4$$$), the number of test cases.

The first line of each test case contains a single integer $$$m$$$ ($$$1 \leq m \leq 2 \cdot 10^5$$$).

The following $$$m$$$ lines contain integers $$$a_i$$$, $$$b_i$$$, and $$$c_i$$$ ($$$1 \leq a_i, b_i, c_i \leq 2 \cdot 10^5$$$). The numbers $$$a_i$$$, $$$b_i$$$, and $$$c_i$$$ are pairwise distinct for each $$$i$$$, and all unordered triples are distinct.

It is guaranteed that the sum of $$$m$$$ over all test cases does not exceed $$$2 \cdot 10^5$$$.

Output

For each test case, output $$$\texttt{yes}$$$ if there exists a crooked cycle; otherwise, output $$$\texttt{no}$$$.

Example
Input
3
4
1 2 3
2 3 4
3 4 1
4 1 2
8
3 2 5
6 3 7
7 3 2
1 5 6
5 2 6
7 4 6
3 2 6
3 2 1
7
7 4 6
2 3 7
7 2 4
5 4 6
3 6 7
5 3 6
1 4 6
Output
yes
yes
no
Note

In the second test case $$$(2\,3\,5\,2\,6\,3\,2\,7\,3\,6)$$$ forms a crooked cycle (although there are smaller ones as well).