#include <iostream>
#include <algorithm>
#include <vector>
#include <list>
using namespace std;

#define MAX 1000
#define pb push_back

class Graph{
			int nodes;
			int x = 0;
			vector <int> *edges;
		public:
			Graph(int vertex){
				this->nodes = vertex;
				edges = new vector <int>[MAX];
			}
			void addEdge(int src, int to){
				edges[src].pb(to);
				edges[to].pb(src);
			}
			//General BFS implementation
			void BFS(list <int> *q, bool *visited, int *parent){
				int curr = q->front();
				q->pop_front();
				for(auto it=edges[curr].begin(); it!=edges[curr].end(); it++){
					if(!visited[*it]){
						parent[*it] = curr;
						visited[*it] = true;
						q->pb(*it);
					}
				}
			}
			int checkIntersection(bool *sourceFlag, bool *destFlag){
				int intersect = -1;
				for(int i=0; i<nodes; i++)
					if(sourceFlag[i] && destFlag[i]) //Dua-duanya visit titik yang sama = udah ketemu pathnya
						return i;
				return -1;
			}
			void BDS(int from, int to){
				bool startVisited[nodes] = {0}, endVisited[nodes] = {0}; //Nyimpen node yang udh divisit
				int startParent[nodes], endParent[nodes]; //Nyimpen parent node kedua sisi
				list <int> startQueue, endQueue;
				int intersect;
				//Inisialisasi default value kedua sisi
				startQueue.pb(from);
				startVisited[from] = true;
				startParent[from] = -1;
				endQueue.pb(to);
				endVisited[to] = true;
				endParent[to] = -1;
				//Main loop
				while(!startQueue.empty() && !endQueue.empty()){
					//BFS dari kedua sisi
					BFS(&startQueue, startVisited, startParent);
					BFS(&endQueue, endVisited, endParent);
					//Cek kalo udah ketemu atau blm
					intersect = checkIntersection(startVisited, endVisited);
					if(intersect != -1){
						cout << "Path found! Intersect at node " << intersect << endl; 
						printPath(startParent, endParent, from, to, intersect);
						return;
					}
				}
				cout << "Path not found!" << endl;
			}
			void printPath(int *startParent, int *endParent, int from, int to, int intersect){
				int *prev = startParent;
				vector <int> paths;
				for(int i=0; i<2; i++){ //Satu dari titik asal, satu dari titik akhir
					int meetPoint = intersect;
					while(meetPoint != -1){
						paths.pb(meetPoint);
						int prevNode = prev[meetPoint];
						meetPoint = prevNode;
					}
					prev = endParent;
				}
				//Print Path
				for(auto i = paths.begin() + 1; i != paths.end(); i++){
					cout << *i << (i == paths.end() - 1 ? "" : "->");
				}
			}
};

int main(){
	int edges, from, to;
	cout << "How many edges ? ";
	cin >> edges;
	Graph graph(edges);
	cout << "Enter " << edges << " edeges (from-to) separated by a space:" << endl;
	while(edges--){
		cin >> from >> to;
		graph.addEdge(from, to);
	}
	cout << "Enter source and destination node: ";
	cin >> from >> to;
	graph.BDS(from, to);
	return 0;
}