using namespace std;
#include <bits/stdc++.h>
typedef vector<vector<int>> GRAPH;
const int OO = 1000000;
vector<int> BFS(GRAPH &graph, int start)
{
vector<int> len((int)graph.size(), OO);
queue<int> queue;
queue.push(start);
len[start] = 0;
while (!queue.empty())
{
int cur = queue.front();
queue.pop();
for (auto &w : graph[cur])
{
if (len[w] == OO)
{
len[w] = 0;
len[w] = len[cur] + 1;
queue.push(w);
}
}
}
return len;
}
void solve()
{
int nodes, edges;
cin >> nodes >> edges;
GRAPH graph(nodes);
for (int i = 0; i < edges; ++i)
{
int from, to;
cin >> from >> to;
graph[from].push_back(to);
graph[to].push_back(from);
}
vector<int> shortest_path = BFS(graph, 0);
int start;
cin >> start;
for (int i = 1; i < nodes; ++i)
{
cout << "SP from " << start << " to " << i << " = " << shortest_path[i] << endl;
}
}
int main()
{
int t{1};
// cin >> t;
while (t--)
solve();
return 0;
}