<prompt> Kuna mti ambao haujaelekezwa na usio na mizizi na nodi za n zilizoorodheshwa kutoka 0 hadi n - 1. Unapewa nambari kamili n na safu kamili ya kingo za 2D za urefu n - 1, ambapo kingoi ai, bi huonyesha kuwa kuna ukingo kati ya nodi ai na bi. katika mti. Pia umepewa safu sarafu za ukubwa n ambapo sarafui zinaweza kuwa 0 au 1, ambapo 1 inaonyesha kuwepo kwa sarafu katika kipeo i.Awali, unachagua kuanza kwenye vertex yoyote kwenye mti. Kisha, unaweza kufanya shughuli zifuatazo mara kadhaa: Kusanya sarafu zote ambazo ziko umbali wa angalau 2 kutoka kwenye kipeo cha sasa, au Sogeza kwenye kipeo chochote cha karibu kwenye mti.Tafuta _idadi ya chini zaidi ya kingo unazohitaji kupitia ili kukusanya sarafu zote na kurudi kwenye kipeo cha kwanza_.Kumbuka kwamba ikiwa unapita makali mara kadhaa, unahitaji kuhesabu kwenye jibu mara kadhaa.Mfano wa 1:Ingizo: sarafu 1,0,0,0,0,1, kingo 0,1,1,2,2,3 ,3,4,4,5Pato: 2Maelezo: Anzia kwenye kipeo cha 2, kusanya sarafu kwenye kipeo cha 0, nenda kwenye kipeo cha 3, kusanya sarafu kwenye kipeo cha 5 kisha rudi kwenye kipeo cha 2.Mfano wa 2:Ingizo: sarafu 0,0,0,1,1,0,0,0,1, kingo 0,1,0,2, 1,3,1,4,2,5,5,6,5,7Pato: 2Maelezo: Anzia kwenye kipeo cha 0, kusanya sarafu kwenye kipeo cha 4 na 3, nenda kwenye kipeo cha 2, kusanya sarafu kwenye kipeo cha 7, kisha rudi nyuma hadi kwenye kipeo cha 0.Vikwazo: n sarafu.urefu 1 n 3 104 0 sarafui 1 edges.length n - 1 kingoi.urefu 2 0 ai, bi n ai ! bi kingo inawakilisha mti halali.  <response>: kutoka kwa makusanyo leta defaultdictdef min_edges_to_collect_coinssarafu, kingo: adj defaultdictorodha kwa a, b katika kingo: adja.ongezab adjb.ongezaa rudisha dfsadj, sarafu, 0, -11 2def dfsadj, sarafu, nodi, mzazi: sum_coins sarafu nodi umbali 0 kwa jirani katika adjnodi: ikiwa jirani ! mzazi: matokeo dfsadj, sarafu, jirani, nodi jumla_coins matokeo0 umbali 2 tokeo0 tokeo1 kurudi jumla_sarafu, umbali 