#include <queue>
#include <vector> 
#include <cstring>
#include <iostream>
#include <algorithm>

#define endl '\n'
#define int long long
#define inf 0x3f3f3f3f
#define lnf 0x3f3f3f3f3f3f3f3f

//#pragma GCC optimize(1)
//#pragma GCC optimize(2)
//#pragma GCC optimize(3)
//#pragma GCC optimize("Os")
//#pragma GCC optimize("Ofast")

using namespace std;

inline bool input (int& x) {
	x = 0;
	int f = 1;
	bool flag = 0;
	char c = getchar ();
	
	while (!isdigit(c)) {
		if (c == '-') {
			c = getchar ();
			
			if (isdigit (c)) {
				f = -1;
				break;
			}
		} else {
			c = getchar ();
		}
	}
	
	while (isdigit (c)) {
		flag = 1;
		x = (x << 3) + (x << 1) + (c ^ 48);
		c = getchar ();
	}
	
	x *= f;
	return flag;
}

inline bool output (int x) {
	if (x < 0) {
		putchar ('-');
		x = -x;
	}
	
	char write[25], cnt = 0;
	
	do {
		write[++ cnt] = x % 10;
		x /= 10;
	} while (x);
	
	do {
		putchar (write[cnt --] | 48);
	} while (cnt);
	
	return x;
}

const int N = 1e5;

void init ();

int n, m, q, val[N + 5], u, v;
vector <int> map[N + 5];
queue <pair <int, int>, vector <pair <int, int>>> a;
pair <int, int> _;

void BFS () {
	a.push ({1, 0});
	
	while (a.size ()) {
		_ = a.front ();
		a.pop ();
		val[_.first] = _.second;
		
		for (int i = 0; i < map[_.first].size (); ++ i) {
			if (val[map[_.first][i]] == -1) {
				a.push ({map[_.first][i], _.second + 1});
			}
		}
	}
}

signed main () {
	init ();
	input (n);
	input (m);
	input (q);
	
	while (m --) {
		input (u);
		input (v);
		
		map[u].push_back (v);
		map[v].push_back (u);
	}
	
	for (int k = 1; k <= n; ++ k) {
		cout << k << ": ";
		
		for (int i = 0; i < map[k].size (); ++ i) {
			cout << map[k][i] << ' ';
		}
		
		cout << endl;
	}
	
	BFS ();
	
	for (int i = 1; i <= n; ++ i) {
		cout << "val[" << i << "] = " << val[i] << endl;
	}
	
	return 0;
}

void init () {
	memset (val, -1, sizeof (val));
//	freopen (".in", "r", stdin);
//	freopen (".out", "w", stdout);
//	ios::sync_with_stdio (false);
//	cin.tie (0);
//	cout.tie (0);
}