{"raw_statement":[{"iden":"statement","content":"There are $n$ islands laid out on a circle. An agency is responsible for the control of a set of $m$ bidirectional bridges, numbered from $0$ to $m -1$, that are located on the center of the islands and can join any two pair of them. The agency might need to restrict traffic on some bridges in case that maintenance is needed to ensure safety of everyone who crosses it. When that happens, the agency select a subset of bridges to be free for crossing. Besides that, it is needed to know if it is possible to go from one given island $a$ to another island $b$ using only those bridges, so that the population can plan their trips accordingly.\n\nThe agency must process $q$ queries, which have four types: \n\nAt the beginning, all bridges are free.\n\nLatache, a student at CIn, while doing his internship at this agency, he received the task of creating a program capable of quickly processing the given queries. However, since Latache was called for so many internships, he didn't have enough time to complete the task before going to work on a different country. But Latache knows how good you are at programming, so you must help him and not let him down (otherwise, he won't help you get interviews).\n\nThe first line contain $3$ integers $n$, $m$ and $q$ $(2 <= n <= 250, 1 <= m <= 10^5, 1 <= q <= 2 dot.op 10^4)$.\n\nThen, $m$ lines follow, containing a pair of numbers $a_i$, $b_i$ $(0 <= a_i, b_i < n, a_i eq.not b_i)$, indicating the pair of islands connected by the $i$-th bridge.\n\nFinally, we have $q$ more lines: the requisitions, according to the description given on the statement, with the following restrictions:\n\n$0 <= l <= r < m$\n\n$0 <= x < m$\n\n$0 <= u, v < n, u eq.not v$\n\nYour program must output, after each query of types _1_, _2_ and _3_, the number of connected components on the graph formed by the islands and bridges, considering only the bridges that are not under maintenance.\n\nFor queries of type _4_, output \"_YES_\" or \"_NO_\" (without quotes).\n\n"},{"iden":"input","content":"The first line contain $3$ integers $n$, $m$ and $q$ $(2 <= n <= 250, 1 <= m <= 10^5, 1 <= q <= 2 dot.op 10^4)$.Then, $m$ lines follow, containing a pair of numbers $a_i$, $b_i$ $(0 <= a_i, b_i < n, a_i eq.not b_i)$, indicating the pair of islands connected by the $i$-th bridge.Finally, we have $q$ more lines: the requisitions, according to the description given on the statement, with the following restrictions:$0 <= l <= r < m$$0 <= x < m$$0 <= u, v < n, u eq.not v$"},{"iden":"output","content":"Your program must output, after each query of types _1_, _2_ and _3_, the number of connected components on the graph formed by the islands and bridges, considering only the bridges that are not under maintenance.For queries of type _4_, output \"_YES_\" or \"_NO_\" (without quotes)."}],"translated_statement":null,"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the size of the square chessboard (rows and columns labeled $ 1 $ to $ n $).  \nLet $ R = \\{r_1, r_2, \\dots, r_n\\} $ be the set of $ n $ rooks, where $ r_k $ denotes the $ k $-th rook.  \nLet $ p_k(t) = (x_k(t), y_k(t)) \\in \\{1, \\dots, n\\}^2 $ be the position of rook $ r_k $ at step $ t $, with initial positions given.\n\n**Constraints**  \n1. $ 1 \\leq n, m \\leq 3 \\times 10^5 $ per test case; total $ \\sum n, \\sum m \\leq 10^6 $ across all test cases.  \n2. Initially, each row and each column contains exactly one rook:  \n   $$\n   \\forall i \\ne j, \\quad x_i(0) \\ne x_j(0) \\quad \\text{and} \\quad y_i(0) \\ne y_j(0)\n   $$  \n3. Commands are of four types:  \n   - `U k`: Move rook $ r_k $ upward as far as possible, but at most $ k $ squares (stopping at boundary).  \n   - `D k`: Move rook $ r_k $ downward as far as possible, but at most $ k $ squares.  \n   - `L k`: Move rook $ r_k $ leftward as far as possible, but at most $ k $ squares.  \n   - `R k`: Move rook $ r_k $ rightward as far as possible, but at most $ k $ squares.  \n4. Queries are of two types:  \n   - `? k`: Output current position $ (x_k, y_k) $ of rook $ r_k $.  \n   - `!`: Output number of unordered pairs $ \\{i, j\\} $ with $ i < j $ such that $ p_i = p_j $.\n\n**Objective**  \nProcess $ m $ commands and queries in chronological order. For each query:  \n- If `? k`, output $ (x_k, y_k) $.  \n- If `!`, output $ \\sum_{1 \\leq i < j \\leq n} \\mathbf{1}_{p_i = p_j} $.","simple_statement":"Lewis has n rooks on an n×n chessboard, one per row and one per column at start.  \nHe gives commands to move all rooks in one of four directions (up, down, left, right) by k squares — but they stop at the board edge.  \nHe also asks two types of queries:  \n- \"? k\" → tell the current position of rook k  \n- \"!\" → count how many pairs of rooks are on the same square  \n\nAnswer each query in order.","has_page_source":false}