B. Demonstrations

Codeforces

IDCF10029B

Time12000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

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. To 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: 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. For every query output a single line - 'NO' if safe connection between two cities provided in the query doesn't exist. 'SI' otherwise. ## Input 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. ## Output For every query output a single line - 'NO' if safe connection between two cities provided in the query doesn't exist. 'SI' otherwise. [samples]

**Definitions** Let $ t \in \mathbb{Z} $ be the number of test cases. For each test case: - Let $ n \in \mathbb{Z} $ denote the number of cities, with $ 1 \leq n \leq 100000 $. - Let $ q \in \mathbb{Z} $ denote the number of queries, with $ 1 \leq q \leq 700000 $. - 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). **Constraints** 1. $ 1 \leq t \leq \text{unknown} $ (implied by input format). 2. For each test case: - $ 1 \leq n \leq 100000 $ - $ 1 \leq q \leq 700000 $ - Each query is one of two types: - **Type 1 (Road Construction)**: Add an undirected edge between two distinct cities $ u, v \in V $. - **Type 2 (Connectivity Query)**: Given two distinct cities $ u, v \in V $, determine if there exists a path between them in $ G $. **Objective** For each query of Type 2, output: - `SI` if $ u $ and $ v $ are in the same connected component of $ G $, - `NO` otherwise.

API Response (JSON)

{
  "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 ...",
      "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 \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments