Silinmə dəyəri

Verilmiş döngüsüz və çoxlu kənarları olmayan istiqamətsiz qrafda zirvələr iki növdədir: qara və ağ. Əgər qara zirvənin heç bir qonşu ağ zirvəsi yoxdursa, o dərhal yox olur. Eyni qayda ilə, əgər ağ zirvənin qara qonşuları yoxdursa, o da yox olur. Hər bir zirvənin silinmə dəyəri məlumdur. Bütün zirvələrin silinməsi üçün minimal dəyəri tapın.

Giriş məlumatları

İki ədəd n və k (1 ≤ n ≤ 100, 0 ≤ k ≤ n · (n - 1) / 2) - qrafda zirvələrin və kənarların sayı. Sonra n sıra gəlir, hər birində iki ədəd t, c (1 ≤ c ≤ 10^6) - zirvənin növü (0 - ağ, 1 - qara) və onun silinmə dəyəri. Daha sonra k sıra gəlir, hər birində iki ədəd - a, b (1 ≤ a, b ≤ n) - kənarla birləşdirilmiş zirvələrin nömrələri.

Çıxış məlumatları

Bütün zirvələrin silinməsi üçün minimal dəyəri çıxarın.