SPOJ Türkiye

Size 1, 2, 3, ..., N şeklinde tamsayılarla isimlendirilmiş ve pozitif tamsayı ağırlıkları olan bir altın boncuklardan oluşan bir gerdanlık veriliyor. Gerdanlıktaki boncuklar birbirlerine ağırlıkları olmayan ve her biri sadece iki boncuğu birbirine bağlayan iplerle bağlanmış durumda. Bu bağlama işlemi öyle yapılmış ki herhangi bir boncuktan diğer herhangi bir boncuğa mutlaka iplerle ulaşılabilen bir (ne az ne de fazla) yol bulunuyor. Sizden istenilen gerdanlığı öyle dengeli iki parçaya bölmeniz ki sonuçda elde edilen 2 ayrı gerdanlığın toplam ağırlıkları arasındaki fark en aza indirilmiş olsun. Gerdanlığı 2 parçaya bölmek için sadece bir ipin kesilmesi / çıkarılması gerekiyor. Sizden bu şekilde çıkarılması gereken ipin hangi boncukları bağladığını bulmanızı istiyoruz.

KISITLAR

Girdi

İlk satırda altın boncuk sayısı (N) verilir. Sonraki N satırda boncukların ağırlıkları yer alır: i (2 ≤ i ≤ N+1)’nci satırda i-1 numaralı boncuğun ağırlığını belirten 1 ile 100 arasında bir tamsayı bulunur. Yani 2. satır 1. boncuğun, 3. satır 2. boncuğun, ... , (N+1). satır N. boncuğun ağırlıklarını içerir. (N+2) ile (2N+1) arasındaki satırlar iki adet 1 ile N arasında tamsayı içerir ve her satır iki boncuk numarası cinsinden bir ipi tanımlar. Toplam (N-1) adet ip tanımlanır.

Çıktı

Çıktıda 1. tamsayı oluşturulan 2 gerdanlığın ağırlık toplamları arsındaki farkı (en aza indirilmek istenilen değeri) verir. 2. ve 3. tamsayılar gerdanlıkta kesilmesi / çıkarılması gereken ipi, bağladığı boncuk numaraları cinsinden tanımlar. Boncuk numaralarından küçük başta büyük sonda olmalıdır.

Örnek

Girdi:
6
10
6
8
11
3
5
1 5
1 4
5 6
5 2
3 2

Çıktı:
1 1 5