Spotify Shuffle

You are curating a custom music playlist that starts with one specific track and ends with another. You have a list of songs, each associated with a set of genres. You must select a sequence of songs, starting from a given start song and ending at a given target song, such that any consecutive pair of songs in the sequence shares at least two genres. Your task is to find any valid path that satisfies these constraints. If multiple valid paths exist, any one is acceptable. If no such path exists, report that it is impossible.

Details:

You are given:

1. A starting song name.
2. A target song name.
3. A list of available songs (including the start and target), each with a set of genres.
4. A transition from one song to another is valid if and only if the two songs share at least two genres in common.

Input Format:

The first line contains two strings, S and T:

• The name of the starting song and the name of the target song.

The second line contains two integers N and G:

• N is the number of songs available (including the start and target).
• G is the maximum number of genres any song might have.

The next N lines each describe a song:

• The line starts with the song name (a string with no spaces), followed by an integer k (the number of genres that song has), and then k strings representing the genres of that song.
• Each song name is unique, and each genre is a string with no spaces. Assume all genres for a given song are distinct.

Output Format:

If it is possible to reach the target song starting from the start song by following the valid transitions, print the number of songs in the path, followed by each song name in the order they should be played.
If there is no such path, print -1.
Constraints:
$1 ≤ N ≤ 2,000$

$1 ≤ k ≤ G ≤ 10$ (each song can have between 1 and G genres, inclusive)

Song names and genre names are reasonably short strings (e.g., length ≤ 20).

The start and target songs are guaranteed to appear in the list of songs.

Sample Input 1

Sample Output 1

Explanation:

• Start song: SongA
• Target song: SongD
• Song list and their genres:
  1. SongA: Rock, Pop, Jazz
  2. SongB: Rock, Pop, Blues
  3. SongC: Pop, Jazz, Classical
  4. SongD: Jazz, Blues, Classical

---

Sample Input 2

Sample Output 2

---

Explanation:

• Start song: SongX
• Target song: SongY
• Songs and their genres:
  1. SongX: Rock, Blues
  2. SongZ: Jazz, Classical
  3. SongY: Jazz, Blues

Graph Construction:

• SongX → SongZ: No shared genres → No connection.
• SongX → SongY: Only 1 shared genre (Blues) → No connection.
• SongZ → SongY: No shared genres → No connection.

No valid path exists between SongX and SongY.

---