{"problem":{"name":"D. Chemical table","description":{"content":"Innopolis University scientists continue to investigate the periodic table. There are _n_·_m_ known elements and they form a periodic table: a rectangle with _n_ rows and _m_ columns. Each element can","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":1000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF1013D"},"statements":[{"statement_type":"Markdown","content":"Innopolis University scientists continue to investigate the periodic table. There are _n_·_m_ known elements and they form a periodic table: a rectangle with _n_ rows and _m_ columns. Each element can be described by its coordinates (_r_, _c_) (1 ≤ _r_ ≤ _n_, 1 ≤ _c_ ≤ _m_) in the table.\n\nRecently scientists discovered that for every four different elements in this table that form a rectangle with sides parallel to the sides of the table, if they have samples of three of the four elements, they can produce a sample of the fourth element using nuclear fusion. So if we have elements in positions (_r_1, _c_1), (_r_1, _c_2), (_r_2, _c_1), where _r_1 ≠ _r_2 and _c_1 ≠ _c_2, then we can produce element (_r_2, _c_2).\n\nSamples used in fusion are not wasted and can be used again in future fusions. Newly crafted elements also can be used in future fusions.\n\nInnopolis University scientists already have samples of _q_ elements. They want to obtain samples of all _n_·_m_ elements. To achieve that, they will purchase some samples from other laboratories and then produce all remaining elements using an arbitrary number of nuclear fusions in some order. Help them to find the minimal number of elements they need to purchase.\n\n## Input\n\nThe first line contains three integers _n_, _m_, _q_ (1 ≤ _n_, _m_ ≤ 200 000; 0 ≤ _q_ ≤ _min_(_n_·_m_, 200 000)), the chemical table dimensions and the number of elements scientists already have.\n\nThe following _q_ lines contain two integers _r__i_, _c__i_ (1 ≤ _r__i_ ≤ _n_, 1 ≤ _c__i_ ≤ _m_), each describes an element that scientists already have. All elements in the input are different.\n\n## Output\n\nPrint the minimal number of elements to be purchased.\n\n[samples]\n\n## Note\n\nFor each example you have a picture which illustrates it.\n\nThe first picture for each example describes the initial set of element samples available. Black crosses represent elements available in the lab initially.\n\nThe second picture describes how remaining samples can be obtained. Red dashed circles denote elements that should be purchased from other labs (the optimal solution should minimize the number of red circles). Blue dashed circles are elements that can be produced with nuclear fusion. They are numbered in order in which they can be produced.\n\n**Test 1**\n\nWe can use nuclear fusion and get the element from three other samples, so we don't need to purchase anything.\n\n**Test 2**\n\nWe cannot use any nuclear fusion at all as there is only one row, so we have to purchase all missing elements.\n\n**Test 3**\n\nThere are several possible solutions. One of them is illustrated below.\n\nNote that after purchasing one element marked as red it's still not possible to immidiately produce the middle element in the bottom row (marked as 4). So we produce the element in the left-top corner first (marked as 1), and then use it in future fusions.\n\n","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"Innopolis 大学的科学家们正在继续研究元素周期表。目前共有 $n\\cdot m$ 种已知元素，它们构成一个周期表：一个包含 $n$ 行和 $m$ 列的矩形。每个元素可以用其在表中的坐标 $(r,\\,c)$（$1\\le r\\le n$，$1\\le c\\le m$）来描述。\n\n最近，科学家们发现：对于表中任意四个构成矩形（边与表的边平行）的不同元素，如果已拥有其中三个元素的样本，就可以通过核聚变生成第四个元素的样本。也就是说，如果我们拥有位于 $(r_1,\\,c_1)$、$(r_1,\\,c_2)$、$(r_2,\\,c_1)$ 的元素（其中 $r_1\\ne r_2$ 且 $c_1\\ne c_2$），那么我们就可以生成位于 $(r_2,\\,c_2)$ 的元素。\n\n用于聚变的样本不会被消耗，可以重复用于未来的聚变。新生成的元素也可以用于未来的聚变。\n\nInnopolis 大学的科学家们已经拥有 $q$ 种元素的样本。他们希望获得所有 $n\\cdot m$ 种元素的样本。为此，他们将从其他实验室购买一些样本，然后通过任意顺序的若干次核聚变生成其余所有元素。请帮助他们找出最少需要购买的元素数量。\n\n第一行包含三个整数 $n$、$m$、$q$（$1\\le n,\\,m\\le 200\\,000$；$0\\le q\\le \\min(n\\cdot m,\\,200\\,000)$），分别表示化学表的行数、列数以及科学家们已拥有的元素数量。\n\n接下来的 $q$ 行，每行包含两个整数 $r_i$、$c_i$（$1\\le r_i\\le n$，$1\\le c_i\\le m$），描述一个科学家已拥有的元素。输入中的所有元素互不相同。\n\n请输出最少需要购买的元素数量。\n\n每个示例都附有一张图来说明。\n\n每个示例的第一张图描述了初始可用的元素样本集合。黑色十字表示实验室初始拥有的元素。\n\n第二张图描述了如何获取剩余样本。红色虚线圆圈表示需要从其他实验室购买的元素（最优解应最小化红色圆圈的数量）；蓝色虚线圆圈表示可以通过核聚变生成的元素，它们按可生成的顺序编号。\n\n*测试 1*\n\n我们可以使用核聚变，通过其他三个样本获得目标元素，因此无需购买任何元素。\n\n*测试 2*\n\n由于只有一行，无法进行任何核聚变，因此必须购买所有缺失的元素。\n\n*测试 3*\n\n存在多种可能的解决方案，其中一种如下图所示。\n\n请注意，在购买一个标记为红色的元素后，仍无法立即生成底部行中间的元素（标记为 4）。因此，我们首先生成左上角的元素（标记为 1），然后在未来的聚变中使用它。\n\n## Input\n\n第一行包含三个整数 $n$、$m$、$q$（$1\\le n,\\,m\\le 200\\,000$；$0\\le q\\le \\min(n\\cdot m,\\,200\\,000)$），分别表示化学表的行数、列数以及科学家们已拥有的元素数量。接下来的 $q$ 行，每行包含两个整数 $r_i$、$c_i$（$1\\le r_i\\le n$，$1\\le c_i\\le m$），每个描述一个科学家已拥有的元素。输入中的所有元素互不相同。\n\n## Output\n\n请输出最少需要购买的元素数量。\n\n[samples]\n\n## Note\n\n每个示例都附有一张图来说明。每个示例的第一张图描述了初始可用的元素样本集合。黑色十字表示实验室初始拥有的元素。第二张图描述了如何获取剩余样本。红色虚线圆圈表示需要从其他实验室购买的元素（最优解应最小化红色圆圈的数量）；蓝色虚线圆圈表示可以通过核聚变生成的元素，它们按可生成的顺序编号。\n\n*测试 1*\n\n我们可以使用核聚变，通过其他三个样本获得目标元素，因此无需购买任何元素。\n\n*测试 2*\n\n由于只有一行，无法进行任何核聚变，因此必须购买所有缺失的元素。\n\n*测试 3*\n\n存在多种可能的解决方案，其中一种如下图所示。\n\n请注意，在购买一个标记为红色的元素后，仍无法立即生成底部行中间的元素（标记为 4）。因此，我们首先生成左上角的元素（标记为 1），然后在未来的聚变中使用它。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions** \nLet $ n, m \\in \\mathbb{Z}^+ $ denote the number of rows and columns of the periodic table. \nLet $ Q \\subseteq \\{1, \\dots, n\\} \\times \\{1, \\dots, m\\} $ be the set of initial element positions already available, with $ |Q| = q $. \n\nA *rectangle rule* applies: for any two distinct rows $ r_1, r_2 $ and two distinct columns $ c_1, c_2 $, if three of the four positions $ (r_1,c_1), (r_1,c_2), (r_2,c_1) $ are available, then the fourth position $ (r_2,c_2) $ can be generated. \n\n**Constraints** \n1. $ 1 \\leq n, m \\leq 200{,}000 $ \n2. $ 0 \\leq q \\leq \\min(nm, 200{,}000) $ \n3. All elements in $ Q $ are distinct. \n\n**Objective** \nFind the minimum number of additional elements to purchase such that, using arbitrary applications of the rectangle rule, all $ nm $ elements in the table can be generated. \n\n**Key Insight** \nThe problem reduces to a connected components problem on a bipartite graph: \n- Construct a bipartite graph $ G = (R \\cup C, E) $, where $ R = \\{r_1, \\dots, r_n\\} $ are row nodes, $ C = \\{c_1, \\dots, c_m\\} $ are column nodes. \n- For each available element at $ (r_i, c_j) \\in Q $, add an edge between $ r_i \\in R $ and $ c_j \\in C $. \n\nThe rectangle rule implies: if rows $ r_i, r_k $ and columns $ c_j, c_\\ell $ are such that three of the four edges $ (r_i,c_j), (r_i,c_\\ell), (r_k,c_j) $ exist, then the fourth edge $ (r_k,c_\\ell) $ can be inferred. This is equivalent to: **if two rows are connected to a common column, and one of them is connected to another column, then the other row can be connected to that column via transitivity**. \n\nThus, the entire table can be generated if and only if the bipartite graph is connected *within each connected component*: for any two rows and two columns in the same connected component, the edge between them can be inferred. \n\nTherefore, the number of elements that must be purchased equals the number of connected components in the bipartite graph minus one: \n$$\n\\text{Answer} = (\\text{number of connected components in } G) - 1\n$$\n\n**Final Formulation** \nLet $ G = (R \\cup C, E) $ be the bipartite graph defined above. \nLet $ k $ be the number of connected components of $ G $. \nThen the minimal number of elements to purchase is: \n$$\n\\boxed{k - 1}\n$$","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF1013D","tags":["dfs and similar","graphs","matrices"],"sample_group":[["2 2 3\n1 2\n2 2\n2 1","0"],["1 5 3\n1 3\n1 1\n1 5","2"],["4 3 6\n1 2\n1 3\n2 2\n2 3\n3 1\n3 3","1"]],"created_at":"2026-03-03 11:00:39"}}