Portallar#11238
Besi n ədəd 1..n ilə işarələnmiş zirvələrdən və 2n ədəd 1..2n ilə işarələnmiş portallardan ibarət şəbəkədə yerləşir. Hər bir portal iki fərqli zirvəni u və v (u ≠ v) birləşdirir. Portal dəsti müəyyən bir zirvə cütünü birləşdirə bilər.
Hər bir v zirvəsi dörd fərqli portalla qonşudur. Zirvənin v portal siyahısı p[v] = p[v,1], p[v,2], p[v,3], p[v,4] kimi verilir.
Cari vəziyyətiniz (current vertex, current portal) cütü ilə təmsil oluna bilər; yəni (v, p[v,i]) cütü, burada 1 ≤ v ≤ n və 1 ≤ i ≤ 4. Cari vəziyyətinizi dəyişmək üçün aşağıdakı əməliyyatlardan birini istifadə edə bilərsiniz:
Cari zirvəni cari portal vasitəsilə dəyişdirin.
Cari portalı dəyişdirin. Hər bir zirvədə siyahıdakı ilk iki portal bir cütlə birləşdirilir və siyahıdakı son iki portal da bir cütlə birləşdirilir. Buna görə də, əgər cari vəziyyətiniz (v, p[v,2])dirsə, portalı (v, p[v,1]) istifadə etmək üçün dəyişə bilərsiniz və əksinə. Eyni şəkildə, əgər cari vəziyyətiniz (v, p[v,3])dirsə, portalı (v, p[v,4]) dəyişə bilərsiniz və əksinə. Başqa dəyişikliklər icazə verilmir (məsələn, p[v,2] portalından p[v,4] portalına keçə bilməzsiniz).
Ümumilikdə 4n fərqli vəziyyət mövcuddur. Təəssüf ki, verilmiş əməliyyatlar ardıcıllığı ilə hər hansı bir vəziyyətin digərinə keçməsi mümkün olmaya bilər. Buna görə də, v zirvəsinin qonşu portal siyahısını istədiyiniz qaydada dəyişdirmək üçün c[v] (1 ≤ c[v] ≤ 1000) mun ödəyə bilərsiniz. Bundan sonra siyahıdakı ilk iki portal bir cütlə, son iki portal isə başqa bir cütlə birləşdirilir.
Məsələn, əgər v zirvəsinin portallarını [p[v,3], p[v,1], p[v,2], p[v,4]] qaydasında dəyişdirsəniz, bu deməkdir ki, əgər v zirvəsindəsiniz,
Əgər p[v,1] portalındasınızsa, p[v,3] portalına keçə bilərsiniz və əksinə
Əgər p[v,2] portalındasınızsa, p[v,4] portalına keçə bilərsiniz və əksinə
İndi p[v,1] portalından p[v,2] portalına və ya p[v,3] portalından p[v,4] portalına keçə bilməzsiniz və əksinə.
Hər bir vəziyyətin digərindən keçməsini mümkün etmək üçün şəbəkəni dəyişdirmək üçün tələb olunan minimal mun sayını hesablayın. Test məlumatlarının şəbəkəni dəyişdirməyin ən azı bir yolu olduğu təmin edilir.
Birinci sətir n (2 ≤ n ≤ 10^5) ehtiva edir.
Növbəti n sətirin hər biri bir zirvəni təsvir edir. v + 1 sətiri 5 tam ədəd ehtiva edir: c[v], p[v,1], p[v,2], p[v,3], p[v,4].
Hər bir v üçün bütün p[v,1], p[v,2], p[v,3], p[v,4] fərqlidir və hər bir portal dəqiq iki zirvənin siyahısında görünür.
Bir sətir, hər bir vəziyyətin digərindən keçməsini mümkün etmək üçün şəbəkəni dəyişdirmək üçün tələb olunan minimal mun sayını ehtiva edir.
Zirvələrin 1 və 4 siyahılarını dəyişdirmək kifayətdir. Bu, c[1] + c[4] = 13 mun tələb edir. Dəyişikliklər belədir: p[1] = [1, 9, 4, 8] və p[4] = [7, 4, 6, 3].
Nümunə 1