<prompt> Umepewa nambari chanya n inayowakilisha idadi ya nodi katika grafu isiyoelekezwa. Nodi zimewekwa lebo kutoka 1 hadi n.Pia umepewa safu kamili ya 2D kingo, ambapo kingoi ai, bi huonyesha kuwa kuna ukingo wa kuelekeza pande mbili kati ya vifundo ai na bi. Angalia kwamba grafu iliyotolewa inaweza kukatwa.Gawa nodi za grafu katika vikundi m 1-indexed ili: Kila nodi kwenye grafu ni ya kundi moja haswa. Kwa kila jozi ya nodi kwenye grafu ambazo zimeunganishwa kwa ukingo ai, bi, ikiwa ai ni ya kikundi chenye faharasa x, na bi ni ya kikundi chenye faharasa y. , kisha y - x 1.Rejesha _idadi ya juu zaidi ya vikundi yaani, upeo_ m_ ambamo unaweza kugawanya nodi_. Rudisha -1 _ikiwa haiwezekani kuweka nodi katika vikundi kwa masharti uliyopewa_.Mfano wa 1:Ingizo: n 6, kingo 1,2,1,4,1,5,2,6,2, 3,4,6Pato: 4Maelezo: Kama inavyoonyeshwa kwenye picha sisi:- Ongeza nodi 5 kwa kundi la kwanza.- Ongeza nodi 1 kwa kundi la pili.- Ongeza nodi 2 na 4 kwa kundi la tatu.- Ongeza nodi 3 na 6 kwa kundi la nne.Tunaweza kuona kwamba kila makali yameridhika.Inaweza kuonyeshwa kwamba ikiwa tutaunda kikundi cha tano na kuhamisha nodi yoyote kutoka kwa kundi la tatu au la nne hadi kwake, angalau juu ya kingo haitaridhika.Mfano wa 2:Ingizo: n 3, kingo 1,2,2,3,3,1Pato: -1Maelezo: Tukiongeza nodi 1 kwenye kundi la kwanza, nodi 2 kwenye kundi la pili, na nodi 3 kwa kundi la tatu ili kutosheleza kingo mbili za kwanza, tunaweza kuona kwamba makali ya tatu hayatatosheka.Inaweza kuonyeshwa kuwa hakuna kikundi kinachowezekana.Vikwazo: 1 n 500 1 edges.length 104 kingoi.urefu 2 1 ai, bi n ai ! bi Kuna angalau ukingo mmoja kati ya jozi yoyote ya wima.  <response>: kutoka kwa makusanyo leta defaultdict, dequedef maxGroupsn, edges: grafu defaultdictorodha rangi 0 n 1 kwa makali katika kingo: grafumakali0.ambatanishamakali1 grafumakali1.ambatanishamakali0 max_group 0 kwa i katika masafa 1, n 1: ikiwa rangii 0: q dequei rangi i 1 wakati q: nodi q.popleft max_group maxmax_group, colornodi kwa jirani kwenye graphnodi: ikiwa rangijirani 0: rangijirani ranginodi 1 q.ongeza jirani elif colorjirani ranginodi: kurudi -1 rudisha max_group 