E. Party

Codeforces

IDCF907E

Time1000ms

Memory256MB

Difficulty—

bitmasksbrute forcedpgraphs

English · Original

Chinese · Translation

Formal · Original

Arseny likes to organize parties and invite people to it. However, not only friends come to his parties, but friends of his friends, friends of friends of his friends and so on. That's why some of Arseny's guests can be unknown to him. He decided to fix this issue using the following procedure. At each step he selects one of his guests _A_, who pairwise introduces all of his friends to each other. After this action any two friends of _A_ become friends. This process is run until all pairs of guests are friends. Arseny doesn't want to spend much time doing it, so he wants to finish this process using the minimum number of steps. Help Arseny to do it. ## Input The first line contains two integers _n_ and _m_ (1 ≤ _n_ ≤ 22; ) — the number of guests at the party (including Arseny) and the number of pairs of people which are friends. Each of the next _m_ lines contains two integers _u_ and _v_ (1 ≤ _u_, _v_ ≤ _n_; _u_ ≠ _v_), which means that people with numbers _u_ and _v_ are friends initially. It's guaranteed that each pair of friends is described not more than once and the graph of friendship is connected. ## Output In the first line print the minimum number of steps required to make all pairs of guests friends. In the second line print the ids of guests, who are selected at each step. If there are multiple solutions, you can output any of them. [samples] ## Note In the first test case there is no guest who is friend of all other guests, so at least two steps are required to perform the task. After second guest pairwise introduces all his friends, only pairs of guests (4, 1) and (4, 2) are not friends. Guest 3 or 5 can introduce them. In the second test case guest number 1 is a friend of all guests, so he can pairwise introduce all guests in one step.

Arseny 喜欢组织聚会并邀请人们参加。然而，不仅他的朋友会来参加聚会，他的朋友的朋友、朋友的朋友的朋友等等也会来。因此，一些 Arseny 的客人可能他并不认识。他决定使用以下程序来解决这个问题。在每一步中，他选择一位客人 #cf_span[A]，让这位客人将他所有的朋友彼此相互介绍。经过这一操作后，#cf_span[A] 的任意两位朋友都会成为朋友。这个过程将持续进行，直到所有客人之间都成为朋友。 Arseny 不想花太多时间做这件事，因此他希望用最少的步骤完成这个过程。请帮助 Arseny 实现这一目标。第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 22]; ) —— 聚会的客人数量（包括 Arseny 自己）以及初始时朋友对的数量。接下来的 #cf_span[m] 行每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n]; #cf_span[u ≠ v])，表示编号为 #cf_span[u] 和 #cf_span[v] 的人初始时是朋友。保证每对朋友最多只出现一次，且友谊图是连通的。第一行输出使所有客人彼此成为朋友所需的最少步骤数。第二行输出每一步被选中的客人编号。如果有多个解，输出任意一个即可。在第一个测试用例中，没有一位客人是所有其他客人的朋友，因此至少需要两步才能完成任务。在第二位客人将他的所有朋友彼此介绍后，只有客人对 #cf_span[(4, 1)] 和 #cf_span[(4, 2)] 仍不是朋友。客人 #cf_span[3] 或 #cf_span[5] 可以完成剩余的介绍。在第二个测试用例中，客人 #cf_span[1] 是所有客人的朋友，因此他可以在一步内将所有客人彼此介绍。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[m] (#cf_span[1 ≤ n ≤ 22]; ) —— 聚会的客人数量（包括 Arseny 自己）以及初始时朋友对的数量。接下来的 #cf_span[m] 行每行包含两个整数 #cf_span[u] 和 #cf_span[v] (#cf_span[1 ≤ u, v ≤ n]; #cf_span[u ≠ v])，表示编号为 #cf_span[u] 和 #cf_span[v] 的人初始时是朋友。保证每对朋友最多只出现一次，且友谊图是连通的。 ## Output 第一行输出使所有客人彼此成为朋友所需的最少步骤数。第二行输出每一步被选中的客人编号。如果有多个解，输出任意一个即可。 [samples] ## Note 在第一个测试用例中，没有一位客人是所有其他客人的朋友，因此至少需要两步才能完成任务。在第二位客人将他的所有朋友彼此介绍后，只有客人对 #cf_span[(4, 1)] 和 #cf_span[(4, 2)] 仍不是朋友。客人 #cf_span[3] 或 #cf_span[5] 可以完成剩余的介绍。在第二个测试用例中，客人 #cf_span[1] 是所有客人的朋友，因此他可以在一步内将所有客人彼此介绍。

**Definitions** Let $ n \in \mathbb{Z}^+ $ be the number of guests, $ m \in \mathbb{Z}^+ $ the number of initial friendship edges. Let $ G = (V, E) $ be an undirected graph with $ V = \{1, 2, \dots, n\} $ and $ E \subseteq \binom{V}{2} $, $ |E| = m $, representing initial friendships. $ G $ is connected. **Constraints** 1. $ 1 \leq n \leq 22 $ 2. $ 1 \leq m \leq \binom{n}{2} $ 3. $ G $ is connected and has no duplicate edges. **Objective** Find the minimum number of steps $ k $ and a sequence of vertices $ S = (v_1, v_2, \dots, v_k) $ such that: - In each step $ i $, selecting $ v_i $ adds all edges between pairs of neighbors of $ v_i $ (i.e., makes the neighborhood of $ v_i $ a clique). - After $ k $ steps, the graph becomes a complete graph $ K_n $. Output the minimal $ k $ and any such sequence $ S $.

Samples

Input #1

Output #1

2
2 3

Input #2

Output #2

1
1

API Response (JSON)

{
  "problem": {
    "name": "E. Party",
    "description": {
      "content": "Arseny likes to organize parties and invite people to it. However, not only friends come to his parties, but friends of his friends, friends of friends of his friends and so on. That's why some of Ars",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF907E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Arseny likes to organize parties and invite people to it. However, not only friends come to his parties, but friends of his friends, friends of friends of his friends and so on. That's why some of Ars...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "Arseny 喜欢组织聚会并邀请人们参加。然而，不仅他的朋友会来参加聚会，他的朋友的朋友、朋友的朋友的朋友等等也会来。因此，一些 Arseny 的客人可能他并不认识。他决定使用以下程序来解决这个问题。\n\n在每一步中，他选择一位客人 #cf_span[A]，让这位客人将他所有的朋友彼此相互介绍。经过这一操作后，#cf_span[A] 的任意两位朋友都会成为朋友。这个过程将持续进行，直到所有客人之间都...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $ be the number of guests, $ m \\in \\mathbb{Z}^+ $ the number of initial friendship edges.  \nLet $ G = (V, E) $ be an undirected graph with $ V = \\{1, 2, \\dot...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments