<prompt> Programu inapaswa kuchukua katika grafu kama pembejeo, na grafu inapaswa kuwakilishwa kama matrix adjacency.  <response>: Programu inapaswa kuwa na uwezo wa kufanya utafutaji wa kina kwanza DFS kwenye grafu, kuanzia kwenye ncha maalum DAG, na kupata njia fupi kati ya ncha mbili za grafu kwa kutumia algorithm ya Dijkstra, na kupata sehemu ndogo za mzunguko kwenye grafu kwa kutumia algorithm ya Primorsky, na kupata pembe katika grafu kwa kutumia algorithm ya Kruskal. 