F. Polycarp and Satellites

Codeforces

IDCF10083F

Time2000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Polycarp likes build space satellites. He learned ideas of projects from Provectus Inc. He knows, that one big satellite is very expensive and is requred to launch a rocket, but N small satellites is cheaper and you can launch satellites, just using special airplane. In that case Polycarp should organize a transmission of data among satellites. He can make two way channel of data transmission between any two different satellites. But a channel requires to install expensive devices on satellites and therefore Polycarp wants to make at most 4·N channels to his satellites. Between any pair of satellites can not be more than 1 channel. Polycarp wants to know which pairs of satellites he should connect with channels, such that if any K channels are destroyed, then we can find path from any satellite to any another one maybe via other satellites. The input contains only one line with two integer numbers N and K: 3 ≤ N ≤ 20, 1 ≤ K ≤ 5. Solution always exists. The first line contains M — the number of channels. M lines follow, each contains ai and bi — numbers of satellites are connected by i channel, M ≤ 4·N. ## Input The input contains only one line with two integer numbers N and K: 3 ≤ N ≤ 20, 1 ≤ K ≤ 5. Solution always exists. ## Output The first line contains M — the number of channels. M lines follow, each contains ai and bi — numbers of satellites are connected by i channel, M ≤ 4·N. [samples]

**Definitions** Let $ N \in \mathbb{Z} $ be the number of satellites, $ K \in \mathbb{Z} $ be the maximum number of channels that can be destroyed. Let $ G = (V, E) $ be an undirected graph where $ V = \{1, 2, \dots, N\} $ represents satellites and $ E \subseteq \binom{V}{2} $ represents communication channels. **Constraints** 1. $ 3 \leq N \leq 20 $ 2. $ 1 \leq K \leq 5 $ 3. $ |E| \leq 4N $ 4. $ |E| \geq \binom{N}{2} $ is not required; $ E $ may be sparse. 5. $ G $ must remain connected after the removal of any $ K $ edges (i.e., $ G $ is $ (K+1) $-edge-connected). **Objective** Find a set $ E $ of edges such that $ G = (V, E) $ is $ (K+1) $-edge-connected and $ |E| \leq 4N $. Output $ |E| $, followed by the $ |E| $ pairs $ (a_i, b_i) \in E $.

API Response (JSON)

{
  "problem": {
    "name": "F. Polycarp and Satellites",
    "description": {
      "content": "Polycarp likes build space satellites. He learned ideas of projects from Provectus Inc. He knows, that one big satellite is very expensive and is requred to launch a rocket, but N small satellites is ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10083F"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Polycarp likes build space satellites. He learned ideas of projects from Provectus Inc. He knows, that one big satellite is very expensive and is requred to launch a rocket, but N small satellites is ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ N \\in \\mathbb{Z} $ be the number of satellites, $ K \\in \\mathbb{Z} $ be the maximum number of channels that can be destroyed.  \nLet $ G = (V, E) $ be an undirected graph where ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments