Problem Description

This problem consists of two independent parts, both involving graph traversal.

Part A: Unweighted Shortest Path

You are given an undirected, unweighted graph with vertices labeled from 0 to n-1 and an edge list. Given a start node s and a target node t, your task is to return both the length of a shortest path and one actual shortest path (as a list of vertices). If no path exists between s and t, return an empty list.

You should discuss your chosen algorithm and analyze its time and space complexity.

Part B: Path Matching a Label Sequence with Minimal Mismatches

Each vertex i in the graph has an associated string label, name[i]. You are given a sequence target[0..m-1] of labels. Your task is to find a path v_0, v_1, ..., v_{m-1} such that:

1. Consecutive vertices v_i and v_{i+1} are adjacent in the graph for all 0 <= i < m-1.
2. The number of indices i where name[v_i] != target[i] is minimized.

Return one such optimal vertex sequence.

You should explain your approach, describe how you reconstruct the path, and analyze the time and space complexity for the given constraints:

• n (number of vertices) up to 10^4
• edges (number of edges) up to 10^4
• m (length of target sequence) up to 10^3