Camí màxim P50411

Considereu un graf dirigit sense cicles amb $n$ vèrtexs i $m$ arcs. Els vèrtexs estan numerats entre 1 i $n$. Sigui $\ell$ la longitud del camí més llarg que acaba en el vèrtex $n$. Des de quants vèrtexs surt un camí de mida $\ell$ que acabi en el vèrtex $n$?

Entrada

L’entrada consisteix en diversos casos, cadascun amb $n$ i $m$, seguit d’$m$ parells $x$ $y$ indicant un arc d’$x$ a $y$, amb $x \ne y$. Suposeu $2 \le n \le 10^5$, $0 \le m \le 5n$, i que no hi ha arcs repetits.

Sortida

Per a cada cas, escriviu el nombre de vèrtexs des dels quals surt un camí de mida $\ell$ que arriba al vèrtex $n$.

Observació

Recomanem resoldre aquest problema en C++.