#include <iostream>
#include <fstream>
#include <vector>
#include <deque>
using namespace std;
class Graf{
public:
struct edge{
int from;
int to;
int cost;
};
Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList);
Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList, bool isCostGraph);
void test();
vector<int> bfs(int start);
private:
//date membre
int m_nrNodes;
int m_nrEdges;
bool m_isOriented;
bool m_isCostGraph;
vector<vector<int>> m_adjacencyList;
vector<edge> m_edges;
//functii ajutatoare
};
Graf::Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList) {
m_nrNodes = nrNodes;
m_nrEdges = nrEdges;
m_isOriented = isOriented;
m_isCostGraph = false;
edge crtEdge;
m_adjacencyList.resize(nrNodes + 1);
for(int i = 1; i <= nrNodes; i++){
for(int j = 0; j < adjacencyList[i].size(); j++){
m_adjacencyList[i].push_back(adjacencyList[i][j]);
crtEdge.from = i;
crtEdge.to = adjacencyList[i][j];
crtEdge.cost = 0;
m_edges.push_back(crtEdge);
}
}
}
void Graf::test(){
cout << m_nrNodes << " " << m_nrEdges << '\n';
for(int i = 1; i <= m_nrNodes; i++){
cout<<i<<": ";
for(int j : m_adjacencyList[i]){
cout<<j<<", ";
}
cout<<'\n';
}
}
Graf::Graf(int nrNodes, int nrEdges, bool isOriented, vector<vector<int>> &adjacencyList, bool isCostGraph) {
//cand ajungem la costuri
}
vector<int> Graf::bfs(int start) {
vector<int> result;
const int n = m_nrNodes + 1;
vector<bool> visited;
for(int i=1; i<=m_nrNodes+1; i++){
visited.push_back(false);
}
deque<int> dq;
vector<int> prev;
for(int i=1; i<=m_nrNodes+1; i++){
prev.push_back(0);
}
dq.push_back(start);
visited[start] = true;
while(!dq.empty()){
int crt = dq.front();
dq.pop_front();
for(int i : m_adjacencyList[crt]){
if(!visited[i]){
dq.push_back(i);
visited[i] = true;
prev[i] = crt;
}
}
}
for(int f = 1; f <= m_nrNodes; f++){
int steps = 0;
int lastVisited;
for(int i = f; i != 0; i = prev[i]){
steps++;
lastVisited = i;
}
if(lastVisited != start) { result.push_back(-1); }
else { result.push_back(steps - 1); }
}
return result;
}
void bfsInfoArena(){
ifstream fin("bfs.in");
ofstream fout("bfs.out");
int n, m, x, from, to;
vector<vector<int>> la;
fin>>n>>m>>x;
la.resize(n+1);
for(int i = 0; i < m; i++){
fin>>from>>to;
la[from].push_back(to);
}
Graf graf = Graf(n, m, true, la);
vector<int> res = graf.bfs(x);
for(int i : res){
fout<<i<<" ";
}
}
int main() {
bfsInfoArena();
return 0;
}