{"raw_statement":[{"iden":"statement","content":"Lord Michael is having a hard time – the continuous increase of tax rates has led the people of Valeostan to rebel against his tyranny. A great number of citizens formed a demonstration which marches along Valeostan's streets. Up to one street can be occupied by the demonstration at any time.\n\nTo appease the people, Michael decided to improve Valeostan's infrastructure, and build a number of roads in the country. As a royal engineer, your task is to process two types of queries: \n\nThe first line of input consists of a single integer – the number of test cases.\n\nThe first line of every test case contains two integers: n - the number of cites (1 ≤ n ≤ 100000, and q - the number of queries (1 ≤ q ≤ 700000). Next q lines contain queries in the format described above, one per line.\n\nFor every  query output a single line - 'NO' if safe connection between two cities provided in the query doesn't exist. 'SI' otherwise.\n\n"},{"iden":"input","content":"The first line of input consists of a single integer – the number of test cases.The first line of every test case contains two integers: n - the number of cites (1 ≤ n ≤ 100000, and q - the number of queries (1 ≤ q ≤ 700000). Next q lines contain queries in the format described above, one per line."},{"iden":"output","content":"For every  query output a single line - 'NO' if safe connection between two cities provided in the query doesn't exist. 'SI' otherwise."},{"iden":"examples","content":"Input18 14BUILD 1 2BUILD 1 3CHECK 1 3BUILD 2 3CHECK 1 3BUILD 4 5BUILD 4 6BUILD 5 6BUILD 1 4CHECK 2 5BUILD 3 6CHECK 2 5BUILD 7 8CHECK 7 8OutputNOSINOSINO"}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ t \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case:  \n- Let $ n \\in \\mathbb{Z} $ denote the number of cities, with $ 1 \\leq n \\leq 100000 $.  \n- Let $ q \\in \\mathbb{Z} $ denote the number of queries, with $ 1 \\leq q \\leq 700000 $.  \n- Let $ G = (V, E) $ be an undirected graph, where $ V = \\{1, 2, \\dots, n\\} $ is the set of cities and $ E $ is the set of roads (initially empty).  \n\n**Constraints**  \n1. $ 1 \\leq t \\leq \\text{unknown} $ (implied by input format).  \n2. For each test case:  \n   - $ 1 \\leq n \\leq 100000 $  \n   - $ 1 \\leq q \\leq 700000 $  \n   - Each query is one of two types:  \n     - **Type 1 (Road Construction)**: Add an undirected edge between two distinct cities $ u, v \\in V $.  \n     - **Type 2 (Connectivity Query)**: Given two distinct cities $ u, v \\in V $, determine if there exists a path between them in $ G $.  \n\n**Objective**  \nFor each query of Type 2, output:  \n- `SI` if $ u $ and $ v $ are in the same connected component of $ G $,  \n- `NO` otherwise.","simple_statement":"You are given n cities and q queries.  \nTwo types of queries:  \n1. Connect two cities with a road.  \n2. Ask if two cities are connected (directly or indirectly).  \n\nFor each query of type 2, output \"SI\" if connected, \"NO\" if not.","has_page_source":false}