Minimum Follows Propagation

You are given a social network with N users labelled from 1 to N. There are M directed connections, where each connection is given as a pair of integers (u, v) indicating that user u follows user v.

Starting from user 1, a message is propagated to his/her followers, and then further along the network. Your task is to determine the minimum number of "follows" required for the message to reach every user who is reachable from user 1. If a user is not reachable from user 1, it should not be included in the output.

In mathematical terms, for each user i reachable from 1, you are to compute the minimum distance d(i) such that there exists a sequence of users \[ 1 = v_0, v_1, \ldots, v_{d(i)} = i \] with the property that for each step, the corresponding relation \( (v_k, v_{k-1}) \) exists (i.e. user \(v_k\) follows user \(v_{k-1}\)).

If no user is reachable (other than user 1), output None.

inputFormat

The first line of input contains two integers N and M separated by a space, representing the number of users and the number of follow relationships respectively.
Each of the following M lines contains two integers u and v (separated by a space) denoting that user u follows user v.

Constraints: 2 ≤ N, 0 ≤ M.

outputFormat

For each user that is reachable from user 1 (excluding user 1), output a line containing two integers separated by a space: the user ID and the minimum number of follows required to reach that user. The output should be sorted in increasing order of user ID.
If no user is reachable from user 1, output a single line with the string None.

## sample

4 3
4 3
3 2
2 1

2 1
3 2
4 3

</p>