Camí màxim P38244

Donat un graf no dirigit, calculeu-ne el camí més llarg, amb una restricció: des de cada vèrtex $x$ només us podeu moure als vèrtexs adjacents $y$ tals que $y > x$.

Entrada

L’entrada consisteix en diversos casos. Cada cas comença amb el nombre de vèrtexs $n$ i el nombre d’arestes $m$, seguits d’$m$ parells $x$ $y$ descrivint una aresta entre $x$ i $y$, amb $x \ne y$. Suposeu $1 \le n \le 10^5$, $0 \le m \le 5n$, que els vèrtexs es numeren a partir de 0, i que no hi ha més d’una aresta entre cada parell $x$ $y$.

Sortida

Per a cada graf, primer escriviu la longitud del camí més llarg (mesurat com el nombre de vèrtexs). A continuació, escriviu ‘:’, i els vèrtexs d’aquest camí separats amb espais. En cas d’empat, trieu el camí lexicogràficament més gran.