{"problem":{"name":"B. Demonstrations","description":{"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 ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":12000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10029B"},"statements":[{"statement_type":"Markdown","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## Input\n\nThe 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.\n\n## Output\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[samples]","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"**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.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10029B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}