Path Existence in a Railway Network

Given a railway network with \(n\) stations and \(m\) bidirectional tracks, each track connects two stations in an undirected manner. Your task is to determine whether there exists a path between a given start station and a given destination station. This problem can be modeled as an undirected graph where stations represent vertices and tracks represent edges. A common approach is to use Breadth-First Search (BFS) to explore the network.

Input Format: The first line contains two integers \(n\) and \(m\), where \(n\) is the number of stations and \(m\) is the number of tracks. Each of the following \(m\) lines contains two integers \(A\) and \(B\) denoting that there is a track connecting station \(A\) and station \(B\). The last line contains two integers \(start\) and \(end\) which represent the starting and destination stations respectively.

Output Format: Output a single line containing True if there exists a path from \(start\) to \(end\), otherwise output False.

inputFormat

The input is read from standard input (stdin) and consists of multiple lines. The first line contains two space-separated integers (n) and (m) denoting the number of stations and tracks respectively. The next (m) lines each contain two space-separated integers (A) and (B), representing a track connecting station (A) to station (B). The final line contains two integers (start) and (end), the starting station and the destination station.

outputFormat

Output a single line to standard output (stdout) containing either True if a path exists from the start station to the destination station or False if no such path exists.## sample

5
4
1 2
2 3
4 5
3 5
1 5

True