E. Lucky Country

Codeforces

IDCF95E

Time1000ms

Memory256MB

Difficulty—

dpdsugraphs

English · Original

Chinese · Translation

Formal · Original

Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, 17, 467 are not. One night Petya was sleeping. He was dreaming of being the president of some island country. The country is represented by islands connected by two-way roads. Between some islands there is no road way, even through other islands, that's why the country is divided into several regions. More formally, each island belongs to exactly one region, there is a path between any two islands located in the same region; there is no path between any two islands from different regions. A region is lucky if the amount of islands in it is a lucky number. As a real president, Petya first decided to build a presidential palace. Being a lucky numbers' fan, Petya wants to position his palace in one of the lucky regions. However, it is possible that initially the country has no such regions. In this case Petya can build additional roads between different regions, thus joining them. Find the minimum number of roads needed to build to create a lucky region. ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 105). They are the number of islands and the number of roads correspondingly. Next _m_ lines contain road descriptions. Each road is defined by the numbers of islands that it connects: that is, by two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_). Some roads can connect an island with itself; there can be more than one road between a pair of islands. Numbers in each line are separated by exactly one space character. ## Output If there's no solution, output the only number "-1" (without the quotes). Otherwise, output the minimum number of roads _r_ that need to be built to get a lucky region. [samples]

Petya 喜欢幸运数字。众所周知，正整数是 #cf_span(class=[tex-font-style-underline], body=[lucky]) 的，当且仅当其十进制表示中不包含除 #cf_span[4] 和 #cf_span[7] 以外的数字。例如，数字 #cf_span[47]、#cf_span[744]、#cf_span[4] 是幸运的，而 #cf_span[5]、#cf_span[17]、#cf_span[467] 则不是。一天夜里，Petya 在睡觉。他梦见自己成为某个岛国的总统。这个国家由通过双向道路连接的岛屿组成。某些岛屿之间没有道路，即使通过其他岛屿也无法到达，因此该国被划分为若干区域。更正式地，每个岛屿恰好属于一个区域，同一区域内的任意两个岛屿之间存在路径；不同区域的任意两个岛屿之间不存在路径。如果一个区域中的岛屿数量是一个幸运数，则称该区域为幸运区域。作为真正的总统，Petya 首先决定建造一座总统府。由于他热爱幸运数字，Petya 希望将他的宫殿建在一个幸运区域中。然而，最初国家可能没有这样的区域。在这种情况下，Petya 可以在不同区域之间修建额外的道路，从而将它们合并。请找出为创建一个幸运区域所需修建的最少道路数量。第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 105])，分别表示岛屿数量和道路数量。接下来的 #cf_span[m] 行每行描述一条道路，由该道路连接的两个岛屿编号给出：即两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n])。某些道路可能连接同一个岛屿；一对岛屿之间可能存在多条道路。每行中的数字由恰好一个空格字符分隔。如果没有解，请仅输出 "-1"（不含引号）。否则，请输出为获得一个幸运区域所需修建的最少道路数量 #cf_span[r]。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n, m ≤ 105])，分别表示岛屿数量和道路数量。接下来的 #cf_span[m] 行每行描述一条道路，由该道路连接的两个岛屿编号给出：即两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n])。某些道路可能连接同一个岛屿；一对岛屿之间可能存在多条道路。每行中的数字由恰好一个空格字符分隔。 ## Output 如果没有解，请仅输出 "-1"（不含引号）。否则，请输出为获得一个幸运区域所需修建的最少道路数量 #cf_span[r]。 [samples]

**Definitions** Let $ n, m \in \mathbb{Z} $ be the number of islands and roads, respectively. Let $ G = (V, E) $ be an undirected multigraph with $ |V| = n $, $ |E| = m $, where self-loops and multiple edges are allowed. Let $ C_1, C_2, \dots, C_k $ be the connected components of $ G $, and let $ s_i = |C_i| $ be the size (number of vertices) of component $ C_i $, for $ i \in \{1, \dots, k\} $. Let $ L \subseteq \mathbb{Z}^+ $ be the set of *lucky numbers*: positive integers whose decimal digits contain only '4' and '7'. **Constraints** 1. $ 1 \le n, m \le 10^5 $ 2. Each edge connects two vertices in $ V $. 3. $ s_i \ge 1 $ for all $ i $, and $ \sum_{i=1}^k s_i = n $. **Objective** Find the minimum number of edges $ r $ to add such that some connected component has size $ \ell \in L $. Equivalently: partition the set of component sizes $ \{s_1, \dots, s_k\} $ into disjoint subsets, and merge components within each subset to form a new component of size equal to some $ \ell \in L $. The cost of merging components of sizes $ s_{i_1}, \dots, s_{i_j} $ is $ j - 1 $ (number of edges needed). Minimize total $ r $ over all possible ways to form at least one component of size $ \ell \in L $, using any subset of the existing components. If no such $ \ell \in L $ satisfies $ \ell \le n $, output $ -1 $.

Samples

Input #1

Output #1

Input #2

Output #2

\-1

API Response (JSON)

{
  "problem": {
    "name": "E. Lucky Country",
    "description": {
      "content": "Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF95E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Petya loves lucky numbers. Everybody knows that positive integers are lucky if their decimal representation doesn't contain digits other than 4 and 7. For example, numbers 47, 744, 4 are lucky and 5, ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Petya 喜欢幸运数字。众所周知，正整数是 #cf_span(class=[tex-font-style-underline], body=[lucky]) 的，当且仅当其十进制表示中不包含除 #cf_span[4] 和 #cf_span[7] 以外的数字。例如，数字 #cf_span[47]、#cf_span[744]、#cf_span[4] 是幸运的，而 #cf_span[5]、#cf_sp...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n, m \\in \\mathbb{Z} $ be the number of islands and roads, respectively.  \nLet $ G = (V, E) $ be an undirected multigraph with $ |V| = n $, $ |E| = m $, where self-loops and mul...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments