# solution by https://w...content-available-to-author-only...n.com/in/eldan-abdrashim/
# https://l...content-available-to-author-only...e.com/problems/all-paths-from-source-to-target/
 
 
"""
Идея заключается в том чтобы рекурсивно бегать по массивом связей(граф), и добавлять их в буффер(path). 
Когда весь путь будет пройден (базовое условие из выхода рекурсии) тогда запишем все в массив результатов, почему .copy? потому что 
массивы в Python передаются по ссылке на память, значит при следующим обращении он будет меняться. Из за этого будем использовать 
легкое копирование(shallow copy .copy()) чтобы избежать ошибку.
 
Массив graph, это матрица смежности (связей) которая говорит кто и с кем связен. 
Как говорит? вот так: если 0 индекс хранит массив [1, 2], значит он (0 вершина) имеет путь от 0 -> 1 и 0 -> 2;
Это связку можно называть графом связи, где 0, 1 и 2 это вершины графа, а их пути это массив путей (как в примере). 
 
 
Если не совсем ясна идея, то пишите 
telegram: @eldvn
instagram: @eldvn1
"""
class Solution:
 
    def depth_search(self, node, graph, path, result):
        if node == len(graph) - 1:
            result.append(path.copy())
            return
 
        for next_node in graph[node]:
            path.append(next_node)
            self.depth_search(next_node, graph, path, result)
            path.pop()
 
    def allPathsSourceTarget(self, graph: list[list[int]]) -> list[list[int]]:
        result = []
        path = [0]
 
        self.depth_search(0, graph, path, result)
 
        return result
 
 
 

IyBzb2x1dGlvbiBieSBodHRwczovL3cuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLm4uY29tL2luL2VsZGFuLWFiZHJhc2hpbS8KIyBodHRwczovL2wuLi5jb250ZW50LWF2YWlsYWJsZS10by1hdXRob3Itb25seS4uLmUuY29tL3Byb2JsZW1zL2FsbC1wYXRocy1mcm9tLXNvdXJjZS10by10YXJnZXQvCgoKIiIiCtCY0LTQtdGPINC30LDQutC70Y7Rh9Cw0LXRgtGB0Y8g0LIg0YLQvtC8INGH0YLQvtCx0Ysg0YDQtdC60YPRgNGB0LjQstC90L4g0LHQtdCz0LDRgtGMINC/0L4g0LzQsNGB0YHQuNCy0L7QvCDRgdCy0Y/Qt9C10Lko0LPRgNCw0YQpLCDQuCDQtNC+0LHQsNCy0LvRj9GC0Ywg0LjRhSDQsiDQsdGD0YTRhNC10YAocGF0aCkuIArQmtC+0LPQtNCwINCy0LXRgdGMINC/0YPRgtGMINCx0YPQtNC10YIg0L/RgNC+0LnQtNC10L0gKNCx0LDQt9C+0LLQvtC1INGD0YHQu9C+0LLQuNC1INC40Lcg0LLRi9GF0L7QtNCwINGA0LXQutGD0YDRgdC40LgpINGC0L7Qs9C00LAg0LfQsNC/0LjRiNC10Lwg0LLRgdC1INCyINC80LDRgdGB0LjQsiDRgNC10LfRg9C70YzRgtCw0YLQvtCyLCDQv9C+0YfQtdC80YMgLmNvcHk/INC/0L7RgtC+0LzRgyDRh9GC0L4gCtC80LDRgdGB0LjQstGLINCyIFB5dGhvbiDQv9C10YDQtdC00LDRjtGC0YHRjyDQv9C+INGB0YHRi9C70LrQtSDQvdCwINC/0LDQvNGP0YLRjCwg0LfQvdCw0YfQuNGCINC/0YDQuCDRgdC70LXQtNGD0Y7RidC40Lwg0L7QsdGA0LDRidC10L3QuNC4INC+0L0g0LHRg9C00LXRgiDQvNC10L3Rj9GC0YzRgdGPLiDQmNC3INC30LAg0Y3RgtC+0LPQviDQsdGD0LTQtdC8INC40YHQv9C+0LvRjNC30L7QstCw0YLRjCAK0LvQtdCz0LrQvtC1INC60L7Qv9C40YDQvtCy0LDQvdC40LUoc2hhbGxvdyBjb3B5IC5jb3B5KCkpINGH0YLQvtCx0Ysg0LjQt9Cx0LXQttCw0YLRjCDQvtGI0LjQsdC60YMuCgrQnNCw0YHRgdC40LIgZ3JhcGgsINGN0YLQviDQvNCw0YLRgNC40YbQsCDRgdC80LXQttC90L7RgdGC0LggKNGB0LLRj9C30LXQuSkg0LrQvtGC0L7RgNCw0Y8g0LPQvtCy0L7RgNC40YIg0LrRgtC+INC4INGBINC60LXQvCDRgdCy0Y/Qt9C10L0uIArQmtCw0Log0LPQvtCy0L7RgNC40YI/INCy0L7RgiDRgtCw0Lo6INC10YHQu9C4IDAg0LjQvdC00LXQutGBINGF0YDQsNC90LjRgiDQvNCw0YHRgdC40LIgWzEsIDJdLCDQt9C90LDRh9C40YIg0L7QvSAoMCDQstC10YDRiNC40L3QsCkg0LjQvNC10LXRgiDQv9GD0YLRjCDQvtGCIDAgLT4gMSDQuCAwIC0+IDI7CtCt0YLQviDRgdCy0Y/Qt9C60YMg0LzQvtC20L3QviDQvdCw0LfRi9Cy0LDRgtGMINCz0YDQsNGE0L7QvCDRgdCy0Y/Qt9C4LCDQs9C00LUgMCwgMSDQuCAyINGN0YLQviDQstC10YDRiNC40L3RiyDQs9GA0LDRhNCwLCDQsCDQuNGFINC/0YPRgtC4INGN0YLQviDQvNCw0YHRgdC40LIg0L/Rg9GC0LXQuSAo0LrQsNC6INCyINC/0YDQuNC80LXRgNC1KS4gCgoK0JXRgdC70Lgg0L3QtSDRgdC+0LLRgdC10Lwg0Y/RgdC90LAg0LjQtNC10Y8sINGC0L4g0L/QuNGI0LjRgtC1IAp0ZWxlZ3JhbTogQGVsZHZuCmluc3RhZ3JhbTogQGVsZHZuMQoiIiIKY2xhc3MgU29sdXRpb246CiAgICAKICAgIGRlZiBkZXB0aF9zZWFyY2goc2VsZiwgbm9kZSwgZ3JhcGgsIHBhdGgsIHJlc3VsdCk6CiAgICAgICAgaWYgbm9kZSA9PSBsZW4oZ3JhcGgpIC0gMToKICAgICAgICAgICAgcmVzdWx0LmFwcGVuZChwYXRoLmNvcHkoKSkKICAgICAgICAgICAgcmV0dXJuCiAgICAgICAgCiAgICAgICAgZm9yIG5leHRfbm9kZSBpbiBncmFwaFtub2RlXToKICAgICAgICAgICAgcGF0aC5hcHBlbmQobmV4dF9ub2RlKQogICAgICAgICAgICBzZWxmLmRlcHRoX3NlYXJjaChuZXh0X25vZGUsIGdyYXBoLCBwYXRoLCByZXN1bHQpCiAgICAgICAgICAgIHBhdGgucG9wKCkKICAgICAgICAKICAgIGRlZiBhbGxQYXRoc1NvdXJjZVRhcmdldChzZWxmLCBncmFwaDogbGlzdFtsaXN0W2ludF1dKSAtPiBsaXN0W2xpc3RbaW50XV06CiAgICAgICAgcmVzdWx0ID0gW10KICAgICAgICBwYXRoID0gWzBdCiAgICAgICAgCiAgICAgICAgc2VsZi5kZXB0aF9zZWFyY2goMCwgZ3JhcGgsIHBhdGgsIHJlc3VsdCkKICAgICAgICAKICAgICAgICByZXR1cm4gcmVzdWx0CiAgICAKICAgIAo=