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 ≤ n ≤ 5 · 10³, n − 1 ≤ m ≤ 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⁴.

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.  ‍50% Punts ‍

• Cas B:  ‍ Casos de tot tipus.  ‍50% Punts ‍

Observació

Us recomanem resoldre aquest problema en C++.