Railway Network Management

This problem involves managing a railway network consisting of stations and bi-directional connections between them. You need to implement a system that supports the following operations:

• ADD name: Adds a new station with the given name. Outputs True if the station is successfully added, or False if it already exists.
• REMOVE name: Removes the station with the given name and all its connections. Outputs True if the station existed and was removed, or False otherwise.
• CONNECT station1 station2: Connects two stations with a bi-directional connection. Outputs True if the connection is created successfully, or False if either station does not exist or if the connection already exists.
• DISCONNECT station1 station2: Removes the connection between two stations. Outputs True if the disconnection is successful, or False if either station does not exist or if there was no connection.
• HAS station1 station2: Checks if there is a direct connection between station1 and station2. Outputs True if there is a connection, or False otherwise.
• ROUTE start end: Finds the shortest route (in terms of the number of stations) from the start station to the end station using breadth-first search. If a route exists, output the station names separated by a single space; otherwise, output None.

Note: All operations are executed sequentially and the output for each operation should be printed on a separate line.

The underlying algorithm for finding a route is based on breadth-first search (BFS). In mathematical terms, if we denote our railway network as an undirected graph \( G = (V, E) \), the problem of finding a route from station \( s \) to station \( t \) becomes finding a path in \( G \) from \( s \) to \( t \). If a path exists, BFS guarantees to find the shortest one.

inputFormat

The input is read from stdin. The first line contains an integer N (1 ≤ N ≤ 1000), representing the number of operations. The following N lines each contain an operation in one of these formats:

ADD name REMOVE name CONNECT station1 station2 DISCONNECT station1 station2 HAS station1 station2 ROUTE start end

outputFormat

For each operation, output the corresponding result on a new line to stdout. For boolean results, output exactly True or False. For the ROUTE operation, if a valid route exists, output the station names separated by a single space; otherwise, output None.## sample

7
ADD A
ADD B
CONNECT A B
HAS A B
ROUTE A B
DISCONNECT A B
HAS A B

True
True
True
True
A B
True
False