We have `n` cities and `m` bi-directional `roads` where `roads[i] = [ai, bi]` connects city `ai` with city `bi`. Each city has a name consisting of exactly three upper-case English letters given in the string array `names`. Starting at any city `x`, you can reach any city `y` where `y != x` (i.e., the cities and the roads are forming an undirected connected graph).

You will be given a string array `targetPath`. You should find a path in the graph of the **same length** and with the **minimum edit distance** to `targetPath`.

You need to return _the order of the nodes in the path with the minimum edit distance_. The path should be of the same length of `targetPath` and should be valid (i.e., there should be a direct road between `ans[i]` and `ans[i + 1]`). If there are multiple answers return any one of them.

The **edit distance** is defined as follows:

**Example 1:**

**Input:** n = 5, roads = \[\[0,2\],\[0,3\],\[1,2\],\[1,3\],\[1,4\],\[2,4\]\], names = \[ "ATL ", "PEK ", "LAX ", "DXB ", "HND "\], targetPath = \[ "ATL ", "DXB ", "HND ", "LAX "\]
**Output:** \[0,2,4,2\]
**Explanation:** \[0,2,4,2\], \[0,3,0,2\] and \[0,3,1,2\] are accepted answers.
\[0,2,4,2\] is equivalent to \[ "ATL ", "LAX ", "HND ", "LAX "\] which has edit distance = 1 with targetPath.
\[0,3,0,2\] is equivalent to \[ "ATL ", "DXB ", "ATL ", "LAX "\] which has edit distance = 1 with targetPath.
\[0,3,1,2\] is equivalent to \[ "ATL ", "DXB ", "PEK ", "LAX "\] which has edit distance = 1 with targetPath.

**Example 2:**

**Input:** n = 4, roads = \[\[1,0\],\[2,0\],\[3,0\],\[2,1\],\[3,1\],\[3,2\]\], names = \[ "ATL ", "PEK ", "LAX ", "DXB "\], targetPath = \[ "ABC ", "DEF ", "GHI ", "JKL ", "MNO ", "PQR ", "STU ", "VWX "\]
**Output:** \[0,1,0,1,0,1,0,1\]
**Explanation:** Any path in this graph has edit distance = 8 with targetPath.

**Example 3:**

**Input:** n = 6, roads = \[\[0,1\],\[1,2\],\[2,3\],\[3,4\],\[4,5\]\], names = \[ "ATL ", "PEK ", "LAX ", "ATL ", "DXB ", "HND "\], targetPath = \[ "ATL ", "DXB ", "HND ", "DXB ", "ATL ", "LAX ", "PEK "\]
**Output:** \[3,4,5,4,3,2,1\]
**Explanation:** \[3,4,5,4,3,2,1\] is the only path with edit distance = 0 with targetPath.
It's equivalent to \[ "ATL ", "DXB ", "HND ", "DXB ", "ATL ", "LAX ", "PEK "\]

**Constraints:**

*   `2 <= n <= 100`
*   `m == roads.length`
*   `n - 1 <= m <= (n * (n - 1) / 2)`
*   `0 <= ai, bi <= n - 1`
*   `ai != bi`
*   The graph is guaranteed to be **connected** and each pair of nodes may have **at most one** direct road.
*   `names.length == n`
*   `names[i].length == 3`
*   `names[i]` consists of upper-case English letters.
*   There can be two cities with **the same** name.
*   `1 <= targetPath.length <= 100`
*   `targetPath[i].length == 3`
*   `targetPath[i]` consists of upper-case English letters.


n`개의 도시와 `m`개의 양방향 `도로`가 있는데, 여기서 `도로[i] = [ai, bi]`는 도시 `ai`와 도시 `bi`를 연결합니다. 각 도시는 문자열 배열 `names`에 주어진 정확히 세 개의 대문자로 구성된 이름을 갖습니다. 임의의 도시 `x`에서 시작하여 `y != x`인 임의의 도시 `y`에 도달할 수 있습니다(즉, 도시와 도로가 방향이 없는 연결 그래프를 형성하고 있음).

문자열 배열 `targetPath`가 주어집니다. 그래프에서 `같은 길이`의 경로를 찾아야 하며, `targetPath`까지의 `최소 편집 거리`를 가져야 합니다.

최소 편집 거리를 가진 경로의 노드 순서를 반환해야 합니다. 경로는 `targetPath`와 길이가 같아야 하며 유효해야 합니다(즉, `ans[i]`와 `ans[i + 1]` 사이에 직접 경로가 있어야 합니다). 답이 여러 개 있으면 그 중 하나를 반환합니다.

편집 거리**는 다음과 같이 정의됩니다:

**예제 1:**

**Input:** n = 5, roads = \[\[0,2\],\[0,3\],\[1,2\],\[1,3\],\[1,4\],\[2,4\]\], names = \[ "ATL ", "PEK ", "LAX ", "DXB ", "HND"\], targetPath = \[ "ATL ", "DXB ", "HND ", "LAX"\]
**출력:** \[0,2,4,2\]
**설명:** \[0,2,4,2\], \[0,3,0,2\] 및 \[0,3,1,2\]가 정답입니다.
\0,2,4,2\]는 \["ATL ","LAX ","HND ","LAX"\]와 같으며, 대상 경로에서 편집 거리 = 1입니다.
\0,3,0,2\]는 \["ATL ","DXB ","ATL ","LAX"\]와 같으며 targetPath에서 편집 거리가 1입니다.
\0,3,1,2\]는 \["ATL ","DXB ","PEK ","LAX"\]와 같으며, 대상 경로와 편집 거리 = 1입니다.

**예제 2:**

**입력:** n = 4, roads = \[\[1,0\],\[2,0\],\[3,0\],\[2,1\],\[3,1\],\[3,2\]\], names = \["ATL ", "PEK ", "LAX ", "DXB"\], targetPath = \["ABC ", "DEF ", "GHI ", "JKL ", "MNO ", "PQR ", "STU ", "VWX"\]
**Output:** \[0,1,0,1,0,1,0,1\]
**설명:** 이 그래프의 모든 경로는 대상 경로와 편집 거리 = 8입니다.

**예제 3:**

**입력:** n = 6, roads = \[\[0,1\],\[1,2\],\[2,3\],\[3,4\],\[4,5\]\], names = \[ "ATL ", "PEK ", "LAX ", "ATL ", "DXB ", "HND"\], targetPath = \[ "ATL ", "DXB ", "HND ", "DXB", "ATL ", "LAX ", "PEK"\]
**출력:** \[3,4,5,4,3,2,1\]
**설명:** \[3,4,5,4,3,2,1\]은 대상 경로에서 편집 거리 = 0인 유일한 경로입니다.
이는 \["ATL ", "DXB ", "HND ", "DXB ", "ATL ", "LAX ", "PEK"\]와 동일합니다.

**제약 조건:**

* `2 <= n <= 100`
* `m == roads.length`
* `n - 1 <= m <= (n * (n - 1) / 2)`
* `0 <= ai, bi <= n - 1`
* `ai != bi`
* 그래프는 **연결**되어 있으며 각 노드 쌍은 **최대 하나의** 직접 경로를 가질 수 있습니다.
* `names.length == n`
* `names[i].length == 3`
* `names[i]`는 영문 대문자로 구성됩니다.
* 이름이 **같은** 도시가 두 개 있을 수 있습니다.
* `1 <= targetPath.length <= 100`
* `targetPath[i].length == 3`
* `targetPath[i]`는 영문 대문자로 구성됩니다.

