H. Real Magic

Codeforces

IDCF10048H

Time1000ms

Memory256MB

Difficulty—

English · Original

Formal · Original

People like magic. Magic is powerful, interesting and mysterious. However, the real magicians are not more than talented cheaters. One of the most famous magicians is David Foolfield. For example, suppose there is a room with a tied magician. Then the doors are closed, opened again - there is no magician and he appears in some other room. The thing we don’t know that there are secret doors that connect rooms with each other. Of course, he may use another cheap trick - to hide in the same room and his assistant that looks the same appears in the other room. However, we assume that there are no assistants in this problem. We finally figured out the secret paths between the rooms. Now we want to calculate in how many rooms (other than the initial) the magician can appear. The magician can appear in any room which can be reached from the starting room directly or indirectly. The first line contains the number of test cases _T_ (T ≤ 30). The first line of each test case contains the number of rooms in the building n and the number of secret paths _m_ (1 ≤ n, m ≤ 104). The following _m_ lines contains numbers _a_ and _b_ (1 ≤ a ≤ b ≤ n), meaning that rooms _a_ and _b_ are connected. For each test case output one line containing “_Case #tc:_”, where _tc_ is the number of the test case (starting from 1). Then output one additional line containing _n_ numbers separated by spaces which show in how many rooms the magician can appear if he starts at the _i_-th room (for all _i_ from 1 to _n_). ## Input The first line contains the number of test cases _T_ (T ≤ 30). The first line of each test case contains the number of rooms in the building n and the number of secret paths _m_ (1 ≤ n, m ≤ 104). The following _m_ lines contains numbers _a_ and _b_ (1 ≤ a ≤ b ≤ n), meaning that rooms _a_ and _b_ are connected. ## Output For each test case output one line containing “_Case #tc:_”, where _tc_ is the number of the test case (starting from 1). Then output one additional line containing _n_ numbers separated by spaces which show in how many rooms the magician can appear if he starts at the _i_-th room (for all _i_ from 1 to _n_). [samples]

**Definitions** Let $ T \in \mathbb{Z} $ be the number of test cases. For each test case $ k \in \{1, \dots, T\} $: - Let $ n_k \in \mathbb{Z} $ be the number of rooms. - Let $ m_k \in \mathbb{Z} $ be the number of undirected secret paths. - Let $ G_k = (V_k, E_k) $ be an undirected graph where $ V_k = \{1, 2, \dots, n_k\} $ and $ E_k \subseteq \binom{V_k}{2} $, with each edge $ \{a, b\} \in E_k $ satisfying $ 1 \le a \le b \le n_k $. **Constraints** 1. $ 1 \le T \le 30 $ 2. For each test case $ k $: - $ 1 \le n_k \le 10^4 $ - $ 1 \le m_k \le 10^4 $ - Each edge $ \{a, b\} \in E_k $ satisfies $ 1 \le a \le b \le n_k $ **Objective** For each test case $ k $, compute an array $ R_k = (r_{k,1}, r_{k,2}, \dots, r_{k,n_k}) $, where for each room $ i \in V_k $: $$ r_{k,i} = |\{ j \in V_k \mid j \ne i \text{ and } j \text{ is reachable from } i \text{ in } G_k \}| $$ That is, $ r_{k,i} $ is the number of rooms (excluding room $ i $) reachable from room $ i $ via any path in the undirected graph $ G_k $.

API Response (JSON)

{
  "problem": {
    "name": "H. Real Magic",
    "description": {
      "content": "People like magic. Magic is powerful, interesting and mysterious. However, the real magicians are not more than talented cheaters. One of the most famous magicians is David Foolfield. For example, su",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10048H"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "People like magic. Magic is powerful, interesting and mysterious. However, the real magicians are not more than talented cheaters. One of the most famous magicians is David Foolfield.\n\nFor example, su...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ T \\in \\mathbb{Z} $ be the number of test cases.  \nFor each test case $ k \\in \\{1, \\dots, T\\} $:  \n- Let $ n_k \\in \\mathbb{Z} $ be the number of rooms.  \n- Let $ m_k \\in \\mathbb...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments