Metro

Şəhər meriyəsi nəhayət Kotalandiyadakı metro şəbkəsini qurmağa razı oldu. İndi bu şəbəkənin tik quraqsını tamamlayaraq, xərcləri minimuma endirmək üçün bir plan hazırlayır.

Bu metro şəbəkəsi müəyyən bir sayda stansiyadan ibarət olacaq və bu stansiyalar arasında tunellər olacaq. Hər bir stansiya arasında tunellər vasitəsiylə bir əlaqə olmalıdır. Bu şəbkə bir növ ağac qrafı kimi işləyəcək, yəni hər stansiyaya bir yolla çatmaq mümkündür.

Bu metro şəbkəsində sərnişinlər bir stansiyaya giriş üçün müəyyən bir məbləq ödüyəcəklər. Bu məbləq həmin stansiyaya çatmaq üçün keçilən tunellərin sayına bərabərdir.

Şəhər meriyəsi bu şəbkəni qura bilmək üçün müəyyən şərtləri yerinə yetirməlidir. Məsələn, meriyə sevimli rəqəmləri olan A və B rəqəmləri arasında olmalıdır. Əgər bu şərtlər yerinə yetməsəsə, metro şəbkəsi qurulmayacaq.

Tapşırıq

Bu şərtləri nəzərə alaraq, metro şəbkəsinin minimal stansiya sayını tapın və ya bu şəbkənin qurulmasının mümkün olmadığını müəyyən edin.

Giriş məlumatları

Giriş məlumatları aşağıdakı kimi veriləcək:

• İlk sətir: N və M rəqəmləri, yəni meriyə sevimli və nifrət etdiyi rəqəmlər.

• İkinci sətir: N rəqəmləri, meriyə sevimli olan rəqəmlər.

• Üçüncü sətir: M rəqəmləri, meriyə nifrət etdiyi rəqəmlər.

Çıxış məlumatları

Çıxış məlumatları aşağıdakı kimi olacaq:

• Yalnız bir sətir: metro şəbkəsinin minimal stansiya sayını göstərən bir rəqəb. Əgər bu şəbkə qurulması mümkün deyilsə, -1 rəqəbi.

Nümunələr

Qiymətləndirmə

Test dəstləri iki hissiyə bölünür və aşağıdakı şərtləri yerinə yetirir:

1. 50 % xal: 1 ≤ N, M, A[i], B[i] ≤ 2000.

2. 50 % xal: 1 ≤ N, M, A[i], B[i] ≤ 100,000.