L. Useful Roads

Codeforces

IDCF10051L

Time4000ms

Memory512MB

Difficulty—

English · Original

Formal · Original

Berland capital contains n junctions and m roads connecting pairs of junctions. All roads are one-way. As you probably know Berland has two misfortunes: fools and roads. It is one month before mayoral election. So it is time for current government to make the city better. To show that they care both about the infrastructure and about the budget, the government decided to repair only _useful_ roads. Current mayor thinks that a road from a junction u to a junction v is useful if there exists a simple path from City Hall to some junction containing the road (u, v). A path is called simple if it does not have any repeated junctions, i.e. contains each junction at most once. The City Hall is located at the junction 1. Help Ministry of Road Transport and Highways to find all useful roads in the city. The input contains several test cases. Each test case starts with a line containing two integers n, m (2 ≤ n ≤ 2·105;1 ≤ m ≤ 2·105) — the number of junctions and the number of roads in the city. The following m lines contain road descriptions, one description per line. A description consists of a pair of space-separated integers ui, vi (1 ≤ ui, vi ≤ n;ui ≠ vi) meaning that the i-th road leads from the junction ui to the junction vi. The junctions are numbered from 1 to n. The City Hall is located at the junction 1. It is guaranteed that there is at most one road between a pair of junctions in each direction. There is a blank line after each test case. The sum of n over all test cases in the input doesn't exceed 2·105. The same is true for m: the sum of m over all test cases in the input doesn't exceed 2·105. Print two lines for each test case. On the first line print the number of useful roads. The second line should contain the indices of useful roads in ascending order. The roads are indexed from 1 to m in order of appearance in the input. Leave the second line empty if there are no useful roads in the city. ## Input The input contains several test cases. Each test case starts with a line containing two integers n, m (2 ≤ n ≤ 2·105;1 ≤ m ≤ 2·105) — the number of junctions and the number of roads in the city. The following m lines contain road descriptions, one description per line. A description consists of a pair of space-separated integers ui, vi (1 ≤ ui, vi ≤ n;ui ≠ vi) meaning that the i-th road leads from the junction ui to the junction vi. The junctions are numbered from 1 to n. The City Hall is located at the junction 1.It is guaranteed that there is at most one road between a pair of junctions in each direction.There is a blank line after each test case. The sum of n over all test cases in the input doesn't exceed 2·105. The same is true for m: the sum of m over all test cases in the input doesn't exceed 2·105. ## Output Print two lines for each test case. On the first line print the number of useful roads. The second line should contain the indices of useful roads in ascending order. The roads are indexed from 1 to m in order of appearance in the input. Leave the second line empty if there are no useful roads in the city. [samples]

**Definitions** Let $ n \in \mathbb{Z} $ be the length of the encrypted string. Let $ E = (e_1, e_2, \dots, e_n) $ be the sequence of ASCII codes of the encrypted string, where $ e_i \in \{0, 1, \dots, 255\} $ for all $ i \in \{1, \dots, n\} $. **Constraints** 1. $ 7 \leq n \leq 10^5 $ 2. $ 0 \leq e_i \leq 255 $ for all $ i \in \{1, \dots, n\} $ 3. The original string consists solely of lowercase English letters (ASCII codes 97 to 122). **Objective** Recover the original string $ S = (s_1, s_2, \dots, s_n) $, where each $ s_i $ is the character with ASCII code $ d_i $, and $ d_i $ is derived from $ e_i $ via the decryption algorithm. Assume the encryption was a constant additive shift: $$ d_i = e_i - k \quad \text{for some fixed } k \in \mathbb{Z} $$ such that $ 97 \leq d_i \leq 122 $ for all $ i $. Output the string $ S $ where $ s_i = \text{chr}(d_i) $.

API Response (JSON)

{
  "problem": {
    "name": "L. Useful Roads",
    "description": {
      "content": "Berland capital contains n junctions and m roads connecting pairs of junctions. All roads are one-way. As you probably know Berland has two misfortunes: fools and roads. It is one month before mayora",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF10051L"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Berland capital contains n junctions and m roads connecting pairs of junctions. All roads are one-way. As you probably know Berland has two misfortunes: fools and roads.\n\nIt is one month before mayora...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z} $ be the length of the encrypted string.  \nLet $ E = (e_1, e_2, \\dots, e_n) $ be the sequence of ASCII codes of the encrypted string, where $ e_i \\in \\{0, 1, \\...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments