#include <iostream>
#include<bits/stdc++.h>

using namespace std;
int main() {
	int n,e;
	cin>>n>>e;
	vector<int> g[n+1];
	vector<int> val(n+1);
	for(int i=1;i<=n;i++){
		cin>>val[i];
		
	}

	for(int i=1;i<=e;i++){
		int u;
		int v;
		cin>>u>>v;

		g[u].push_back(v);
		g[v].push_back(u);
	}

	int s;
	cin>>s;
	queue<int> q;
	q.push(s);
	vector<int> level(n+1,-1);
	level[s]=0;
	

	
	vector<int> visited(n+1,0);
	visited[s]=1;
	
	vector<int> shortest(n+1,0);
	shortest[s]=0;
	
	

	vector<int> five_count(n+1,0);
	
		if(val[s]==5){
		five_count[s]=1;
	}
	
	


	while(!q.empty()){
       int a = q.front();
	   
	   
	   q.pop();


	   for(auto it : g[a]){
           if(!visited[it]){
			q.push(it);
			visited[it]=1;
			shortest[it] = shortest[a]+1;
			if(val[it]==5){
				five_count[it] = five_count[a] + 1;
			}
			else{
					five_count[it] = five_count[a];
			}
		   }
		   else{
		   	if(shortest[it]==shortest[a]+1){
		   		if(val[it]==5){
		   			five_count[it] = max(five_count[it],five_count[a]+1);
		   		}else{
		   			five_count[it] = max(five_count[it],five_count[a]);
		   		}
		   	}
		   }
	   }
	}

	for(int i=1;i<=n;i++){
		if (visited[i] == 0) {
            cout << -1 << " " << -1 << "\n"; 
        } else {
            cout << shortest[i] << " " << five_count[i] << "\n"; 
        }
		

	}
}