頂点 \(1\) から順に BFS していきます。BFS では現在行ける未訪問の頂点のうち最も頂点番号が小さい頂点を探索することにします。

ここで、ある \(k_0\) が存在し既に訪問済みの頂点の集合が \(\lbrace 1,2,\ldots,k_0\rbrace\) と一致するなら \(k=k_0\) の場合の答えは \(\lbrace 1,2,\ldots,k_0\rbrace\) からちょうど \(1\) 本の辺を使って到達可能な未訪問の頂点の個数と一致します。この事実より、訪問済みの頂点の集合と未訪問だが訪問済みの頂点からちょうど \(1\) 本の辺を使って到達可能な頂点の集合をそれぞれ持ち、条件を満たすか都度判定すれば良いです。

計算量は \(O(N\log N+M)\) です。

以下の実装では、訪問済みの頂点の集合を s_pq で保持し、未訪問だが訪問済みの頂点からちょうど \(1\) 本の辺を使って到達可能な頂点の集合を pq で保持しています。 pq では BFS で頂点番号が小さい順に探索できるように昇順に値を持つ優先度付きキューを用いています。また、頂点の集合が \(\lbrace 1,2,\ldots,k_0\rbrace\) と一致するかの判定は降順に値を持つ優先度付きキューの先頭の値がサイズと一致するかで判定できるため、 s_pq では降順に値を持つ優先度付きキューを用いています。（Python にそのようなライブラリは存在しないため、\(x\) に対し \(-x\) を昇順に値を持つ優先度付きキューに入れることで仮想的に降順に値を持っています。）

実装例(Python3)

import heapq
import sys

input = sys.stdin.readline
n, m = map(int, input().split())
g = [[] for _ in range(n)]
for _ in range(m):
    u, v = map(int, input().split())
    g[u - 1].append(v - 1)
used = [False] * n
used[0] = True
pq = [0]
ans = [-1] * n
ans[0] = len(pq)
s_pq = []
while pq:
    x = heapq.heappop(pq)
    heapq.heappush(s_pq, -x)
    for to in g[x]:
        if used[to]:
            continue
        used[to] = True
        heapq.heappush(pq, to)
    top = -s_pq[0]
    if top == len(s_pq) - 1:
        ans[top] = len(pq)
print("\n".join(map(str, ans)))