# [Frog Position](https://leetcode.com/problems/frog-position-after-t-seconds/)

from collections import defaultdict, deque

class Solution:
    def frogPosition(self, n: int, edges: List[List[int]], t: int, target: int) -> float:
        graph = self.buildGraph(edges)
        queue = deque()
        queue.append((1, 1.0))
        timeLeft = t
        while len(queue) > 0 and timeLeft >= 0:
            for _ in range(len(queue)):
                currNode, currProbability = queue.popleft()
                if currNode == target:
                    if timeLeft == 0 or len(graph[currNode]) == 0:
                        return currProbability
                else:
                    for neighbor in graph[currNode]:
                        queue.append((neighbor, currProbability * (1 / len(graph[currNode]))))
                        graph[neighbor].remove(currNode)
            timeLeft -= 1
        return 0.0
    
    def buildGraph(self, edges):
        graph = defaultdict(set)
        for (source, dest) in edges:
            graph[source].add(dest)
            graph[dest].add(source)
        return graph