#include <iostream>
#include <vector>
#include <queue>
using namespace std;
class Graph {
public:
int vertices;
vector<vector<int>> adjList;
Graph(int V) : vertices(V), adjList(V) {}
void addEdge(int u, int v) {
adjList[u].push_back(v);
adjList[v].push_back(u);
}
vector<int> shortestPathBFS(int start, int end) {
vector<int> distance(vertices, -1);
queue<int> q;
distance[start] = 0;
q.push(start);
while (!q.empty()) {
int current = q.front();
q.pop();
for (int neighbor : adjList[current]) {
if (distance[neighbor] == -1) {
distance[neighbor] = distance[current] + 1;
q.push(neighbor);
}
}
}
return distance;
}
};
int main() {
int V, E;
cout << "Enter the number of vertices and edges: ";
cin >> V >> E;
Graph graph(V);
cout << "Enter the edges (format: u v):" << endl;
for (int i = 0; i < E; ++i) {
int u, v;
cin >> u >> v;
graph.addEdge(u, v);
}
int start, end;
cout << "Enter the start and end vertices for shortest path: ";
cin >> start >> end;
vector<int> distance = graph.shortestPathBFS(start, end);
cout << "Shortest distance from " << start << " to " << end << " is: " << distance[end] << endl;
return 0;
}