Graph Path Finder

You are given a graph represented as an adjacency list. Your task is to implement several functionalities for the graph including:

• Finding the shortest path between two specified nodes using Breadth First Search (BFS). If one or both of the specified nodes do not exist, output an error message: One or both of the specified nodes do not exist in the graph.
• Checking connectivity of the graph. A graph is connected if there exists a path between any two nodes.
• Adding an edge between any two nodes. If a node does not exist in the graph, it should be added automatically.

Additionally, during graph initialization, you must validate that:

• The graph is not empty. If it is empty, output Graph is empty.
• Every neighbor listed for a node exists in the graph. Otherwise, output an error in the format: Node X in connection from Y does not exist in the graph.

Note: All input and output should be via standard input (stdin) and standard output (stdout). When performing the SP (shortest path) query, if a path exists, output the nodes in the path separated by a single space. If no path is found, output No path found.

inputFormat

The input begins with an integer n indicating the number of nodes in the initial graph. Each of the next n lines contains information for a node in the following format:

NodeName k Neighbor1 Neighbor2 ... Neighbork

After the graph definition, an integer q is given representing the number of queries. Each of the next q lines is a query command of one of the following types:

• SP startNode endNode — Find and output the shortest path from startNode to endNode.
• IC — Check if the graph is connected. Output True or False.
• AE node1 node2 — Add an edge between node1 and node2. If any node does not exist, add it to the graph. After adding, output Edge added.

Validation during initialization:

• If n is 0, output Graph is empty. and terminate.
• For each neighbor listed, if the neighbor is not among the defined nodes, output Node X in connection from Y does not exist in the graph. (where X and Y are the neighbor and the node respectively) and terminate.

outputFormat

For each query, output the result on a separate line:

• For the SP query, output the shortest path as a sequence of node names separated by a space. If no path exists, output No path found.
• For the IC query, output True if the graph is connected or False otherwise.
• For the AE query, output Edge added after the edge is added.
• If an error occurs during initialization or query processing (e.g. node not found), output the corresponding error message.
## sample

6
A 2 B C
B 3 A D E
C 2 A F
D 1 B
E 2 B F
F 2 C E
1
SP A F

A C F