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 ℓ la longitud del camí més llarg que acaba en el vèrtex n. Des de quants vèrtexs surt un camí de mida ℓ 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 ≠ y. Suposeu 2 ≤ n ≤ 10⁵, 0 ≤ m ≤ 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 ℓ que arriba al vèrtex n.

Observació

Recomanem resoldre aquest problema en C++.