ACM Coding Data

SmartIO collaborates with recognized ACM contest Online Judge (OJ) from universities to collect and clean the Leetcode style code data. We have licensed and cleaned the following OJ data sources.

Data Sources

University	Number of Problems	Online Judge (OJ)
HDU	6000	https://acm.hdu.edu.cn/
SJTU	19950	https://acm.sjtu.edu.cn/OnlineJudge/
PKU	3000	http://poj.org/problemlist

Data Format

Problem description in markdown format, e.g., statement.md
Solution to the problem in cpp source code format, e.g., main.cpp
Test cases (input and output) in text format, e.g., 7300.in, 7300.out

Example Problem

https://acm.hdu.edu.cn/showproblem.php?pid=7300

Magma Cave

Time Limit: 12000/12000 MS (Java/Others)
Memory Limit: 524288/524288 K (Java/Others)
Total Submission(s): 173
Accepted Submission(s): 68

Problem Description

Little Q is researching an active volcano. There are n caves inside the volcano, labeled by 1,2,…,n. At the very beginning, before the first volcanic activity event, there is no magma path between these caves. You will be given q operations, each operation is one of the following:- ''𝟷 𝚞 𝚟 𝚠'' (1≤u,v≤n, u≠v, 1≤w≤q): A volcanic activity event comes such that a new magma path between the u-th cave and the v-th cave occurs, whose length is w. Here w is used for identifying the magma path, so w will always be pairwise different.- ''𝟸 𝚔 𝚠'' (1≤k<n, 1≤w≤q): Assume it is a undirected graph with n vertices, each magma path denoting an edge, Little Q is wondering whether there exists a spanning tree whose k-th shortest edge is of length w. You are the partner of Little Q, please write a program to answer his question.

Input

The first line contains a single integer T (1≤T≤100), the number of test cases. For each test case:The first line contains two integers n and q (2≤n≤50000, 1≤q≤200000), denoting the number of caves and the number of operations.Each of the next q lines describes an operation in formats described in the statement above.It is guaranteed that the sum of all n is at most 300000, and the sum of all q is at most 1000000.

Output

For each question, print a single line. If it is possible, print ''𝚈𝙴𝚂'', otherwise print ''𝙽𝙾''.

Sample Input

2 3 7 1 1 2 1 2 1 1 1 2 3 5 1 1 3 4 2 2 4 2 2 5 2 2 3 2 4 1 1 2 1 1 1 2 2 2 1 1 2 1 2

Sample Output

NO YES YES NO YES YES