Graph Operations: Cycle Detection and Shortest Path

This problem requires you to implement a graph data structure with the following operations:

• Add a vertex
• Add an edge (undirected)
• Remove an edge
• Detect if the graph contains a cycle
• Find the shortest path between two vertices

Specifically, when processing the graph you will receive a series of commands. Some commands (like cycle detection and shortest path queries) should produce output. All input is read from standard input and all output is sent to standard output.

For the cycle detection, use a DFS-based algorithm, and for finding the shortest path, use BFS. In your output, for cycle detection, print True if a cycle exists and False otherwise. For shortest path queries, print the list of vertices (space separated) comprising the shortest path. If no valid path exists or if one of the endpoints does not exist, output an empty line.

All formulas (if any) must be in LaTeX format. For example, a path from vertex $u$ to vertex $v$ can be denoted as \( u \rightarrow \dots \rightarrow v \).

inputFormat

The input starts with an integer T representing the number of operations. The following T lines each contain a command. The commands are defined as follows:

• AV x: Add a vertex with label x (an integer).
• AE u v: Add an undirected edge between vertices u and v.
• RE u v: Remove the edge between vertices u and v.
• HC: Query whether the current graph contains a cycle. Print True or False.
• SP u v: Query the shortest path from vertex u to vertex v. Output the sequence of vertices in the shortest path separated by spaces. If no path exists, print an empty line.

Process the commands in order.

outputFormat

For every query command (HC and SP), output the result in a new line. For the HC command, output either True or False. For the SP command, output the vertices of the shortest path separated by a single space. If no path exists, output an empty line.

## sample

5
AV 0
AV 1
AE 0 1
HC
SP 0 1

False
0 1

</p>