E. Mister B and Flight to the Moon

Codeforces

IDCF819E

Time2000ms

Memory256MB

Difficulty—

constructive algorithmsgraphs

English · Original

Chinese · Translation

Formal · Original

In order to fly to the Moon Mister B just needs to solve the following problem. There is a complete indirected graph with _n_ vertices. You need to cover it with several simple cycles of length 3 and 4 so that each edge is in exactly 2 cycles. We are sure that Mister B will solve the problem soon and will fly to the Moon. Will you? ## Input The only line contains single integer _n_ (3 ≤ _n_ ≤ 300). ## Output If there is no answer, print _\-1_. Otherwise, in the first line print _k_ (1 ≤ _k_ ≤ _n_2) — the number of cycles in your solution. In each of the next _k_ lines print description of one cycle in the following format: first print integer _m_ (3 ≤ _m_ ≤ 4) — the length of the cycle, then print _m_ integers _v_1, _v_2, ..., _v__m_ (1 ≤ _v__i_ ≤ _n_) — the vertices in the cycle in the traverse order. Each edge should be in exactly two cycles. [samples]

为了飞往月球，Mister B 只需解决以下问题。有一个包含 #cf_span[n] 个顶点的完全无向图。你需要用若干个长度为 #cf_span[3] 和 #cf_span[4] 的简单环覆盖它，使得每条边恰好出现在 #cf_span[2] 个环中。我们相信 Mister B 很快就能解决这个问题并飞往月球。你呢？输入仅包含一个整数 #cf_span[n]（#cf_span[3 ≤ n ≤ 300]）。如果无解，请输出 _-1_。否则，第一行输出 #cf_span[k]（#cf_span[1 ≤ k ≤ n2]）——你解中环的数量。接下来的 #cf_span[k] 行中，每行描述一个环：首先输出整数 #cf_span[m]（#cf_span[3 ≤ m ≤ 4]）——环的长度，然后输出 #cf_span[m] 个整数 #cf_span[v1, v2, ..., vm]（#cf_span[1 ≤ vi ≤ n]）——按遍历顺序排列的环上顶点。每条边必须恰好出现在两个环中。 ## Input 输入仅包含一个整数 #cf_span[n]（#cf_span[3 ≤ n ≤ 300]）。 ## Output 如果无解，请输出 _-1_。否则，第一行输出 #cf_span[k]（#cf_span[1 ≤ k ≤ n2]）——你解中环的数量。接下来的 #cf_span[k] 行中，每行描述一个环：首先输出整数 #cf_span[m]（#cf_span[3 ≤ m ≤ 4]）——环的长度，然后输出 #cf_span[m] 个整数 #cf_span[v1, v2, ..., vm]（#cf_span[1 ≤ vi ≤ n]）——按遍历顺序排列的环上顶点。每条边必须恰好出现在两个环中。 [samples]

**Definitions** Let $ n \in \mathbb{Z} $ with $ 3 \leq n \leq 300 $. Let $ K_n = (V, E) $ be the complete undirected graph with vertex set $ V = \{1, 2, \dots, n\} $ and edge set $ E = \binom{V}{2} $. **Constraints** Each edge $ e \in E $ must appear in exactly two cycles, where each cycle is simple and has length either 3 or 4. **Objective** Find a multiset $ \mathcal{C} $ of cycles (each of length 3 or 4) such that: - Every edge in $ E $ is covered exactly twice. - Output the cycles in $ \mathcal{C} $, or output $-1$ if no such collection exists.

Samples

Input #1

Output #1

2
3 1 2 3
3 1 2 3

Input #2

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Mister B and Flight to the Moon",
    "description": {
      "content": "In order to fly to the Moon Mister B just needs to solve the following problem. There is a complete indirected graph with _n_ vertices. You need to cover it with several simple cycles of length 3 and",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF819E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "In order to fly to the Moon Mister B just needs to solve the following problem.\n\nThere is a complete indirected graph with _n_ vertices. You need to cover it with several simple cycles of length 3 and...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "为了飞往月球，Mister B 只需解决以下问题。\n\n有一个包含 #cf_span[n] 个顶点的完全无向图。你需要用若干个长度为 #cf_span[3] 和 #cf_span[4] 的简单环覆盖它，使得每条边恰好出现在 #cf_span[2] 个环中。\n\n我们相信 Mister B 很快就能解决这个问题并飞往月球。你呢？\n\n输入仅包含一个整数 #cf_span[n]（#cf_span[3 ≤ n...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ with $ 3 \\leq n \\leq 300 $.  \nLet $ K_n = (V, E) $ be the complete undirected graph with vertex set $ V = \\{1, 2, \\dots, n\\} $ and edge set $ E = \\binom{V}{2...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments