Jalan Tol Menuju Roma

Batas Waktu	 1 detik
Batas Memori	 16 MB
Seorang pengelana yang mengendarai mobil berada di sebuah kota, dan ingin menuju kota Roma. Di negara Italia, ada N (1 ≤ N ≤ 500) buah kota, dan kota-kota ini dihubungkan oleh L buah ruas jalan (1 ≤ L ≤ 125000), di mana sebuah ruas jalan menghubungkan dua kota yang berbeda. Selain itu, ada juga T (1 ≤ T ≤ 125000) buah ruas jalan tol, di mana sebuah ruas jalan tol menghubungkan dua kota yang berbeda. Setiap pasang kota dapat dihubungkan hanya oleh sebuah ruas jalan biasa, atau hanya oleh sebuah ruas jalan tol, atau tidak dihubungkan oleh ruas jalan.

Sang pengelana ingin mencapai kota Roma dalam waktu yang secepat-cepatnya. Sang pengelana tahu bahwa sebuah ruas jalan biasa atau jalan tol dapat ditempuh dalam waktu 1 jam. Namun, sang pengelana hanya memiliki satu buah tiket jalan tol, yang hanya dapat digunakan untuk melintasi satu ruas jalan tol saja. Selebihnya, sang pengelana harus menggunakan jalan biasa. Sang pengelana juga boleh saja untuk tidak memakai tiket jalan tolnya, jika dia dapat mencapai kota Roma dalam waktu yang secepat-cepatnya.

Buatlah program yang dapat mengeluarkan banyak jam paling sedikit untuk mencapai kota Roma dari kota asal.

Format Masukan

Baris pertama berisi lima buah bilangan bulat, masing-masing dipisahkan oleh sebuah spasi: N, L, T, nomor kota awal, dan nomor kota Roma. Kota-kota dinomori 1 sampai dengan N.

L baris berikutnya masing-masing mendeskripsikan sebuah ruas jalan. Setiap baris terdiri atas dua buah kota, yaitu nomor kedua kota yang dihubungkan oleh ruas jalan tersebut.

T baris berikutnya masing-masing mendeskripsikan sebuah ruas jalan tol. Setiap baris terdiri atas dua buah kota, yaitu nomor kedua kota yang dihubungkan oleh ruas jalan tol tersebut.

Format Keluaran

Baris pertama berisi sebuah bilangan bulat, yaitu banyak jam paling sedikit untuk mencapai kota Roma dari kota asal, dengan atau tanpa menggunakan satu-satunya tiket jalan tol. Dijamin pasti ada rute dari kota asal ke kota Roma.

Contoh Masukan

7 9 2 1 7
1 2
1 3
3 2
2 4
4 3
4 5
4 6
5 7
6 7
3 6
5 6
Contoh Keluaran

3
Penjelasan

Contoh masukan dapat diilustrasikan dengan gambar di bawah ini. Ruas garis berwarna biru berarti jalan tol. Rute tercepat adalah dari 1 ke 3 ke 6 ke 7.


Tips

Coba pikirkan apakah yang disebut sebuah state dalam masalah pencarian ini.