Graph Connectivity and Shortest Path Analysis

You are given an undirected graph along with two special nodes, \(A\) and \(B\). The graph is specified by its number of edges followed by a list of edges. Your task is to:

• Determine whether the graph is connected, i.e. there exists a path between every pair of nodes in the graph.
• Find the shortest path from node \(A\) to node \(B\). If such a path exists, output it as a list. Otherwise, indicate that there is no path between \(A\) and \(B\>.

The output should consist of two lines. The first line reports the connectivity status of the graph, while the second line either shows the shortest path or indicates that no path exists.

inputFormat

The input is read from standard input and has the following format:

• The first line contains an integer \(E\) representing the number of edges in the graph.
• The next \(E\) lines each contain two integers \(u\) and \(v\), indicating an undirected edge between nodes \(u\) and \(v\).
• The last line contains two integers, \(A\) and \(B\), which are the start and end nodes for the shortest path query.

outputFormat

The output should be printed to standard output and consist of two lines:

• The first line should be either Graph is connected or Graph is not connected indicating the connectivity status of the graph.
• The second line should be one of the following:
  • If a path between \(A\) and \(B\) exists, print: Shortest path between A and B: [path] where [path] is a list of node numbers.
  • If no path exists, print: No path between A and B

## sample

7
1 2
1 3
2 4
3 4
2 5
5 6
6 7
1 7

Graph is connected
Shortest path between 1 and 7: [1, 2, 5, 6, 7]

</p>