#include <bits/stdc++.h>
using namespace std;
 
int main() {
	// your code goes here
	int n,m;
	cin>>n>>m;
	vector<vector<int>>g(n+10);
	vector<int>visited(n+10);
	vector<int>level(n+10);
	vector<int>ways(n+10);
	queue<int>q;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		g[x].push_back(y);
		g[y].push_back(x);
	}
	int source;
	cin>>source;
	q.push(source);
	visited[source]=1;
	ways[source]=1;
	while(!q.empty())
	{
		int removed=q.front();
		cout<<removed<<" "<<ways[removed]<<endl;
		q.pop();
		for(auto u:g[removed])
		{
			if(visited[u]==0)
			{
				q.push(u);
				visited[u]=1;
				level[u]=level[removed]+1;
				ways[u]=ways[removed];
			}
			else
			{
				if(level[removed]+1==level[u])
				{
					ways[u]+=ways[removed];
				}
			}
		}
	}
 
	return 0;
}

I2luY2x1ZGUgPGJpdHMvc3RkYysrLmg+CnVzaW5nIG5hbWVzcGFjZSBzdGQ7CgppbnQgbWFpbigpIHsKCS8vIHlvdXIgY29kZSBnb2VzIGhlcmUKCWludCBuLG07CgljaW4+Pm4+Pm07Cgl2ZWN0b3I8dmVjdG9yPGludD4+ZyhuKzEwKTsKCXZlY3RvcjxpbnQ+dmlzaXRlZChuKzEwKTsKCXZlY3RvcjxpbnQ+bGV2ZWwobisxMCk7Cgl2ZWN0b3I8aW50PndheXMobisxMCk7CglxdWV1ZTxpbnQ+cTsKCWZvcihpbnQgaT0xO2k8PW07aSsrKQoJewoJCWludCB4LHk7CgkJY2luPj54Pj55OwoJCWdbeF0ucHVzaF9iYWNrKHkpOwoJCWdbeV0ucHVzaF9iYWNrKHgpOwoJfQoJaW50IHNvdXJjZTsKCWNpbj4+c291cmNlOwoJcS5wdXNoKHNvdXJjZSk7Cgl2aXNpdGVkW3NvdXJjZV09MTsKCXdheXNbc291cmNlXT0xOwoJd2hpbGUoIXEuZW1wdHkoKSkKCXsKCQlpbnQgcmVtb3ZlZD1xLmZyb250KCk7CgkJY291dDw8cmVtb3ZlZDw8IiAiPDx3YXlzW3JlbW92ZWRdPDxlbmRsOwoJCXEucG9wKCk7CgkJZm9yKGF1dG8gdTpnW3JlbW92ZWRdKQoJCXsKCQkJaWYodmlzaXRlZFt1XT09MCkKCQkJewoJCQkJcS5wdXNoKHUpOwoJCQkJdmlzaXRlZFt1XT0xOwoJCQkJbGV2ZWxbdV09bGV2ZWxbcmVtb3ZlZF0rMTsKCQkJCXdheXNbdV09d2F5c1tyZW1vdmVkXTsKCQkJfQoJCQllbHNlCgkJCXsKCQkJCWlmKGxldmVsW3JlbW92ZWRdKzE9PWxldmVsW3VdKQoJCQkJewoJCQkJCXdheXNbdV0rPXdheXNbcmVtb3ZlZF07CgkJCQl9CgkJCX0KCQl9Cgl9CgkKCXJldHVybiAwOwp9

NSAKNgoxIDIKMSAzCjEgNQoxIDQgCjMgNiAKNCA3IAox

5 
6
1 2
1 3
1 5
1 4 
3 6 
4 7 
1