{"problem":{"name":"E. PolandBall and White-Red graph","description":{"content":"PolandBall has an undirected simple graph consisting of _n_ vertices. Unfortunately, it has no edges. The graph is very sad because of that. PolandBall wanted to make it happier, adding some red edges","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":262144},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF755E"},"statements":[{"statement_type":"Markdown","content":"PolandBall has an undirected simple graph consisting of _n_ vertices. Unfortunately, it has no edges. The graph is very sad because of that. PolandBall wanted to make it happier, adding some red edges. Then, he will add white edges in every remaining place. Therefore, the final graph will be a clique in two colors: white and red.\n\nColorfulness of the graph is a value _min_(_d__r_, _d__w_), where _d__r_ is the diameter of the red subgraph and _d__w_ is the diameter of white subgraph. The diameter of a graph is a largest value _d_ such that shortest path between some pair of vertices in it is equal to _d_. If the graph is not connected, we consider its diameter to be _\\-1_.\n\nPolandBall wants the final graph to be as neat as possible. He wants the final colorfulness to be equal to _k_. Can you help him and find any graph which satisfies PolandBall's requests?\n\n## Input\n\nThe only one input line contains two integers _n_ and _k_ (2 ≤ _n_ ≤ 1000, 1 ≤ _k_ ≤ 1000), representing graph's size and sought colorfulness.\n\n## Output\n\nIf it's impossible to find a suitable graph, print _\\-1_.\n\nOtherwise, you can output any graph which fulfills PolandBall's requirements. First, output _m_ — the number of red edges in your graph. Then, you should output _m_ lines, each containing two integers _a__i_ and _b__i_, (1 ≤ _a__i_, _b__i_ ≤ _n_, _a__i_ ≠ _b__i_) which means that there is an undirected red edge between vertices _a__i_ and _b__i_. Every red edge should be printed exactly once, you can print the edges and the vertices of every edge in arbitrary order.\n\nRemember that PolandBall's graph should remain simple, so no loops or multiple edges are allowed.\n\n[samples]\n\n## Note\n\nIn the first sample case, no graph can fulfill PolandBall's requirements.\n\nIn the second sample case, red graph is a path from 1 to 5. Its diameter is 4. However, white graph has diameter 2, because it consists of edges _1-3_, _1-4_, _1-5_, _2-4_, _2-5_, _3-5_.","is_translate":false,"language":"English"},{"statement_type":"Markdown","content":"PolandBall 有一个包含 #cf_span[n] 个顶点的无向简单图。遗憾的是，它没有边。由于这个原因，这个图非常悲伤。PolandBall 希望让它更快乐一些，于是添加了一些红色边。接着，他会在所有剩余的位置添加白色边。因此，最终的图将是一个由红色和白色两种颜色构成的完全图。\n\n图的“丰富度”定义为 #cf_span[min(dr, dw)]，其中 #cf_span[dr] 是红色子图的直径，#cf_span[dw] 是白色子图的直径。图的直径是指图中任意两点间最短路径的最大值 #cf_span[d]。如果图不连通，则认为其直径为 _-1_。\n\nPolandBall 希望最终的图尽可能整洁。他希望最终的丰富度恰好等于 #cf_span[k]。你能帮助他，找出一个满足 PolandBall 要求的图吗？\n\n输入仅有一行，包含两个整数 #cf_span[n] 和 #cf_span[k]（#cf_span[2 ≤ n ≤ 1000]，#cf_span[1 ≤ k ≤ 1000]），分别表示图的大小和期望的丰富度。\n\n如果不存在满足条件的图，请输出 _-1_。\n\n否则，你可以输出任意一个满足 PolandBall 要求的图。首先输出 #cf_span[m] —— 你图中红色边的数量。然后输出 #cf_span[m] 行，每行包含两个整数 #cf_span[ai] 和 #cf_span[bi]（#cf_span[1 ≤ ai, bi ≤ n]，#cf_span[ai ≠ bi]），表示顶点 #cf_span[ai] 和 #cf_span[bi] 之间有一条无向红色边。每条红色边只能输出一次，边及其端点的输出顺序可以任意。\n\n请记住，PolandBall 的图必须保持简单，不允许自环或多重边。\n\n在第一个样例中，不存在满足 PolandBall 要求的图。\n\n在第二个样例中，红色图是一条从 #cf_span[1] 到 #cf_span[5] 的路径，其直径为 #cf_span[4]。然而，白色图的直径为 #cf_span[2]，因为它包含边 _1-3_、_1-4_、_1-5_、_2-4_、_2-5_、_3-5_。\n\n## Input\n\nThe only one input line contains two integers #cf_span[n] and #cf_span[k] (#cf_span[2 ≤ n ≤ 1000], #cf_span[1 ≤ k ≤ 1000]), representing graph's size and sought colorfulness.\n\n## Output\n\nIf it's impossible to find a suitable graph, print _-1_. Otherwise, you can output any graph which fulfills PolandBall's requirements. First, output #cf_span[m] — the number of red edges in your graph. Then, you should output #cf_span[m] lines, each containing two integers #cf_span[ai] and #cf_span[bi], (#cf_span[1 ≤ ai, bi ≤ n], #cf_span[ai ≠ bi]) which means that there is an undirected red edge between vertices #cf_span[ai] and #cf_span[bi]. Every red edge should be printed exactly once, you can print the edges and the vertices of every edge in arbitrary order. Remember that PolandBall's graph should remain simple, so no loops or multiple edges are allowed.\n\n[samples]\n\n## Note\n\n在第一个样例中，不存在满足 PolandBall 要求的图。\n在第二个样例中，红色图是一条从 #cf_span[1] 到 #cf_span[5] 的路径，其直径为 #cf_span[4]。然而，白色图的直径为 #cf_span[2]，因为它包含边 _1-3_、_1-4_、_1-5_、_2-4_、_2-5_、_3-5_。","is_translate":true,"language":"Chinese"},{"statement_type":"Markdown","content":"**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the number of vertices, $ k \\in \\mathbb{Z} $ the target colorfulness.  \nLet $ G = (V, E) $ be a complete graph on $ n $ vertices, partitioned into two edge-disjoint subgraphs:  \n- $ G_r = (V, E_r) $: red subgraph,  \n- $ G_w = (V, E_w) $: white subgraph, where $ E_w = \\binom{V}{2} \\setminus E_r $.  \n\nLet $ d_r = \\text{diam}(G_r) $, $ d_w = \\text{diam}(G_w) $, with $ \\text{diam}(G) = -1 $ if $ G $ is disconnected.  \nDefine colorfulness as $ \\min(d_r, d_w) $.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 1000 $  \n2. $ 1 \\leq k \\leq 1000 $  \n3. $ G_r $ and $ G_w $ are simple, undirected, no loops or multiple edges.  \n4. $ E_r \\cap E_w = \\emptyset $, $ E_r \\cup E_w = \\binom{V}{2} $  \n\n**Objective**  \nFind any $ E_r \\subseteq \\binom{V}{2} $ such that $ \\min(d_r, d_w) = k $, or output $-1$ if impossible.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF755E","tags":["constructive algorithms","graphs","shortest paths"],"sample_group":[["4 1","\\-1"],["5 2","4\n1 2\n2 3\n3 4\n4 5"]],"created_at":"2026-03-03 11:00:39"}}