/*
	?§£????????????:Connected Components - Bridges
	(http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=GRL_3_B&lang=jp)

	Status:Runtime Error(?????????????????????????????????)

	??????:
		????????????????????§????????°????????§???????????????????????¨???????????¨????°???\????????????????????????????????£?????????????????????????£????????????????????????????????????¢????????¨?????????
		http://www.npca.jp/works/magazine/2014_1/?????????????????????????????????pdf??????????????????
		??????????????????????£????????????????????????????????????§????????¨????????????????????????????????????????????£???????????????
		?????°???????????????????????????????????????????????????????????????????????????????????????????????????????????????????????¨????±????????????????????????¨???????????§???????????¨???????????????

*/
var log = console.log;
if (typeof process != "undefined") {
    var input = "";
    process.stdin.resume();
    process.stdin.setEncoding('utf8');
    process.stdin.on('data', function(chunk) {
        input += chunk;
    });
    process.stdin.on('end', function() {
        var lines = input.split("\n");
        main(lines);
    });
}


function main(lines) {
    lines = lines.map(function(line) {
        return line.split(" ").map(function(e) {
            return Number(e);
        });
    });
    var V = lines[0][0];
    lines.shift();
    lines = lines.map(function(line) {
        return line.slice(2).map(function(e) {
            return e - 1;
        });
    })
    var visited = [0];
    var stack = [
        [0, 0]
    ];
    var list = [0];
    while (visited.length < V) {
        var now = stack.shift();
        lines[now[0]].forEach(function(e) {
            if (visited.indexOf(e) == -1) {
                //?¨??????????????????????
                stack.push([e, now[1] + 1]);
                list[e] = now[1] + 1;
                visited.push(e);
            }
        });
    }
    for (var i = 0; i < V; i++) {
        log((i + 1) + " " + list[i]);
    }
}