{"problem":{"name":"E. Timofey and our friends animals","description":{"content":"After his birthday party, Timofey went to his favorite tree alley in a park. He wants to feed there his favorite birds — crows. It's widely known that each tree is occupied by a single crow family. T","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":7000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF763E"},"statements":[{"statement_type":"Markdown","content":"After his birthday party, Timofey went to his favorite tree alley in a park. He wants to feed there his favorite birds — crows.\n\nIt's widely known that each tree is occupied by a single crow family. The trees in the alley form a row and are numbered from 1 to _n_. Some families are friends to each other. For some reasons, two families can be friends only if they live not too far from each other, more precisely, there is no more than _k_ - 1 trees between any pair of friend families. Formally, the family on the _u_\\-th tree and the family on the _v_\\-th tree can be friends only if |_u_ - _v_| ≤ _k_ holds.\n\nOne of the friendship features is that if some family learns that Timofey is feeding crows somewhere, it notifies about this all friend families. Thus, after Timofey starts to feed crows under some tree, all the families that are friends to the family living on this tree, as well as their friends and so on, fly to the feeding place. Of course, the family living on the tree also comes to the feeding place.\n\nToday Timofey came to the alley and noticed that all the families that live on trees with numbers strictly less than _l_ or strictly greater than _r_ have flown away. Thus, it is not possible to pass the information about feeding through them. Moreover, there is no need to feed them. Help Timofey to learn what is the minimum number of trees under which he has to feed crows so that all the families that have remained will get the information about feeding. You are given several situations, described by integers _l_ and _r_, you need to calculate the answer for all of them.\n\n## Input\n\nThe first line contains integers _n_ and _k_ (1 ≤ _n_ ≤ 105, 1 ≤ _k_ ≤ 5), where _n_ is the number of trees, and _k_ is the maximum possible distance between friend families.\n\nThe next line contains single integer _m_ (0 ≤ _m_ ≤ _n_·_k_) — the number of pair of friend families.\n\nEach of the next _m_ lines contains two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ 105), that means that the families on trees _u_ and _v_ are friends. It is guaranteed that _u_ ≠ _v_ and |_u_ - _v_| ≤ _k_. All the given pairs are distinct.\n\nThe next line contains single integer _q_ (1 ≤ _q_ ≤ 105) — the number of situations you need to calculate the answer in.\n\nEach of the next _q_ lines contains two integers _l_ and _r_ (1 ≤ _l_ ≤ _r_ ≤ 105), that means that in this situation families that have flown away lived on such trees _x_, so that either _x_ < _l_ or _x_ > _r_.\n\n## Output\n\nPrint _q_ lines. Line _i_ should contain single integer — the answer in the _i_\\-th situation.\n\n[samples]\n\n## Note\n\nIn the first example the following family pairs are friends: (1, 3), (2, 3) and (4, 5).\n\n*   In the first situation only the first family has remained, so the answer is 1.\n*   In the second situation the first two families have remained, and they aren't friends, so the answer is 2.\n*   In the third situation the families 2 and 3 are friends, so it is enough to feed any of them, the answer is 1.\n*   In the fourth situation we can feed the first family, then the third family will get the information from the first family, and the second family will get the information from the third. The answer is 1.\n*   In the fifth situation we can feed the first and the fifth families, so the answer is 2.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"在生日派对之后，蒂莫菲来到公园里他最喜欢的树荫小道，打算喂他最喜欢的鸟——乌鸦。\n\n众所周知，每棵树上都住着一个乌鸦家庭。小道上的树排成一行，编号从 #cf_span[1] 到 #cf_span[n]。有些家庭是彼此的朋友。出于某些原因，两个家庭只有在相距不远时才能成为朋友，更准确地说，任意一对朋友家庭之间至多有 #cf_span[k - 1] 棵树。形式化地，位于第 #cf_span[u] 棵树上的家庭与位于第 #cf_span[v] 棵树上的家庭只有在满足 #cf_span[|u - v| ≤ k] 时才能成为朋友。\n\n其中一项友谊特性是：如果某个家庭得知蒂莫菲在某处喂乌鸦，它会将此信息通知所有朋友家庭。因此，当蒂莫菲在某棵树下开始喂乌鸦时，与该树上家庭是朋友的所有家庭，以及它们的朋友、朋友的朋友等，都会飞到喂食地点。当然，该树上的家庭本身也会前来。\n\n今天蒂莫菲来到小道，发现所有居住在编号严格小于 #cf_span[l] 或严格大于 #cf_span[r] 的树上的家庭都已飞走。因此，无法通过这些家庭传递喂食信息，也不需要喂它们。请帮助蒂莫菲计算：为了确保所有剩余的家庭都能获得喂食信息，他至少需要在多少棵树下喂乌鸦？你将得到若干由整数 #cf_span[l] 和 #cf_span[r] 描述的情形，你需要为所有情形计算答案。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105]，#cf_span[1 ≤ k ≤ 5]），其中 #cf_span[n] 表示树的数量，#cf_span[k] 表示朋友家庭之间的最大距离。\n\n第二行包含一个整数 #cf_span[m]（#cf_span[0 ≤ m ≤ n·k]）——朋友家庭对的数量。\n\n接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ 105]），表示位于第 #cf_span[u] 和第 #cf_span[v] 棵树上的家庭是朋友。保证 #cf_span[u ≠ v] 且 #cf_span[|u - v| ≤ k]。所有给出的对都是互不相同的。\n\n接下来一行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 105]）——你需要计算答案的情形数量。\n\n接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ l ≤ r ≤ 105]），表示在该情形中，飞走的家庭居住在满足 #cf_span[x < l] 或 #cf_span[x > r] 的树 #cf_span[x] 上。\n\n请输出 #cf_span[q] 行。第 #cf_span[i] 行应包含一个整数——第 #cf_span[i] 个情形的答案。\n\n在第一个示例中，朋友家庭对为：#cf_span[(1, 3)]、#cf_span[(2, 3)] 和 #cf_span[(4, 5)]。\n\n## Input\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[1 ≤ n ≤ 105]，#cf_span[1 ≤ k ≤ 5]），其中 #cf_span[n] 表示树的数量，#cf_span[k] 表示朋友家庭之间的最大距离。第二行包含一个整数 #cf_span[m]（#cf_span[0 ≤ m ≤ n·k]）——朋友家庭对的数量。接下来的 #cf_span[m] 行，每行包含两个整数 #cf_span[u] 和 #cf_span[v]（#cf_span[1 ≤ u, v ≤ 105]），表示位于第 #cf_span[u] 和第 #cf_span[v] 棵树上的家庭是朋友。保证 #cf_span[u ≠ v] 且 #cf_span[|u - v| ≤ k]。所有给出的对都是互不相同的。接下来一行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 105]）——你需要计算答案的情形数量。接下来的 #cf_span[q] 行，每行包含两个整数 #cf_span[l] 和 #cf_span[r]（#cf_span[1 ≤ l ≤ r ≤ 105]），表示在该情形中，飞走的家庭居住在满足 #cf_span[x < l] 或 #cf_span[x > r] 的树 #cf_span[x] 上。\n\n## Output\n\n请输出 #cf_span[q] 行。第 #cf_span[i] 行应包含一个整数——第 #cf_span[i] 个情形的答案。\n\n[samples]\n\n## Note\n\n在第一个示例中，朋友家庭对为：#cf_span[(1, 3)]、#cf_span[(2, 3)] 和 #cf_span[(4, 5)]。在第一个情形中，只有第一个家庭留下，因此答案为 #cf_span[1]。在第二个情形中，前两个家庭留下，但它们不是朋友，因此答案为 #cf_span[2]。在第三个情形中，第 #cf_span[2] 和第 #cf_span[3] 家庭是朋友，因此只需喂其中任意一家即可，答案为 #cf_span[1]。在第四个情形中，我们可以喂第一个家庭，然后第三个家庭会从第一个家庭获得信息，第二个家庭会从第三个家庭获得信息，答案为 #cf_span[1]。在第五个情形中，我们可以喂第一个和第五个家庭，因此答案为 #cf_span[2]。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions:**\n\n- Let $ G = (V, E) $ be an undirected graph where $ V = \\{1, 2, \\dots, n\\} $, representing trees.\n- An edge $ (u, v) \\in E $ exists if and only if $ |u - v| \\leq k $ and the pair $ (u, v) $ is given as a friendship.\n- The graph $ G $ has at most $ n \\cdot k $ edges (as given).\n\n**Given:**\n\n- For each query $ (l, r) $, consider the induced subgraph $ G_{l,r} = G[\\{l, l+1, \\dots, r\\}] $, i.e., the subgraph induced by vertices in $ [l, r] $.\n- The goal is to find the **minimum number of vertices** (trees) to select in $ [l, r] $ such that **every vertex in $ [l, r] $** is reachable from at least one selected vertex via a path in $ G_{l,r} $.\n\n**Objective:**\n\nFor each query $ (l, r) $, compute the **minimum number of vertices** required to **dominate** (via connected components) the induced subgraph $ G_{l,r} $. That is, the number of **connected components** in $ G_{l,r} $.\n\n**Formal Statement:**\n\nLet $ G = (V, E) $ be a graph with $ V = \\{1, \\dots, n\\} $, and edge set $ E $ defined by the input friendships satisfying $ |u - v| \\leq k $.\n\nFor each query $ (l, r) $, define:\n\n$$\nV_{l,r} = \\{ v \\in V \\mid l \\leq v \\leq r \\}\n$$\n$$\nE_{l,r} = \\{ (u, v) \\in E \\mid u, v \\in V_{l,r} \\}\n$$\n\nLet $ C_{l,r} $ be the number of **connected components** in the subgraph $ (V_{l,r}, E_{l,r}) $.\n\nThen, the answer for query $ (l, r) $ is:\n\n$$\n\\boxed{C_{l,r}}\n$$\n\n**Justification:**\n\n- Since information spreads through friendship edges (i.e., connected components), feeding **one tree per connected component** ensures all families in that component receive the information.\n- Feeding fewer than one per component is insufficient.\n- Feeding more than one per component is not minimal.\n- Thus, the minimum number of feeding points equals the number of connected components in the induced subgraph $ G_{l,r} $.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF763E","tags":["data structures","divide and conquer","dsu"],"sample_group":[["5 3\n3\n1 3\n2 3\n4 5\n5\n1 1\n1 2\n2 3\n1 3\n1 5","1\n2\n1\n1\n2"]],"created_at":"2026-03-03 11:00:39"}}