12. Reorder Routes to Make All Paths Lead to the City Zero

Medium

Problem Statement

There are n cities numbered from 0 to n - 1 and n - 1 roads. You need to reorient some roads such that each city can visit the city 0. Return the minimum number of edges changed.

Examples

1Example 1

Input:

{
  "n": 6,
  "connections": [
    [
      0,
      1
    ],
    [
      1,
      3
    ],
    [
      2,
      3
    ],
    [
      4,
      0
    ],
    [
      4,
      5
    ]
  ]
}

Output:

3

2Example 2

Input:

{
  "n": 5,
  "connections": [
    [
      1,
      0
    ],
    [
      1,
      2
    ],
    [
      3,
      2
    ],
    [
      3,
      4
    ]
  ]
}

Output:

2

3Example 3

Input:

{
  "n": 3,
  "connections": [
    [
      1,
      0
    ],
    [
      2,
      0
    ]
  ]
}

Output:

0