Retransmissió P90287

És la final de la Copa d’Europa, i el Govern ha decidit posar dues pantalles gegants per poder seguir en directe el partit. Una pantalla se situarà a la ciutat $x$, i l’altra a la ciutat $y$.

El país té $n$ ciutats, connectades amb $m$ vies de tramvia. Habitualment els tramvies de cada via es mouen en les dues direccions, de manera que hi ha $2m$ línies. Aquestes línies permeten anar des de qualsevol ciutat a qualsevol altra. Com que el partit serà molt tard, a una hora en la que en un dia normal ja no funciona cap tramvia, la Conselleria de Territori ha decidit establir un servei especial.

Per estalviar, s’ha decidit obrir el mínim nombre de línies que asseguri que des de qualsevol ciutat del país es pugui arribar tant a la ciutat $x$ com a la ciutat $y$. No cal garantir que després es pugui tornar a la ciutat de sortida. Quin és el mínim nombre de línies que s’han d’obrir?

Entrada

L’entrada conté diversos casos, cadascun amb una línia amb $n$ i $m$, seguides d’una línia amb $m$ parells d’enters $u$ $v$ indicant una via de tramvia entre $u$ i $v$. Finalment, tenim una línia amb $x$ i $y$. Suposeu $1 \le n \le 5 \cdot 10^3$, $n - 1 \le m \le 5n$, que les ciutats es numeren a partir de 0, que no hi ha vies repetides, i que la suma de les $n$ de tots els casos no supera $10^4$.

Sortida

Per a cada cas, escriviu el mínim nombre de línies de tramvia que s’han d’obrir.

Puntuació

• Cas A:   Casos amb $m = n - 1$, com a l’exemple d’entrada 2.

• Cas B:   Casos de tot tipus.

Observació

Us recomanem resoldre aquest problema en C++.