# Water Jug Problem using DFS

def dfs_water_jug(jug1, jug2, target):
    stack = [((0, 0), [])]
    visited = set()

    while stack:
        (x, y), path = stack.pop()

        if (x, y) in visited:
            continue

        visited.add((x, y))
        path = path + [(x, y)]

        if x == target or y == target:
            return path

        next_states = [
            (jug1, y),
            (x, jug2),
            (0, y),
            (x, 0),
            (max(0, x - (jug2 - y)), min(jug2, y + x)),
            (min(jug1, x + y), max(0, y - (jug1 - x)))
        ]

        for state in next_states:
            if state not in visited:
                stack.append((state, path))

    return None

jug1 = 4
jug2 = 3
target = 2

result = dfs_water_jug(jug1, jug2, target)

print("Solution Path:")
for step in result:
    print(step)