WA in POUR1 in Python 3

I am trying to solve the problem POUR1 which needs the extended Euclidean Algorithm. I have implemented it from Wikipedia but am getting a WA. Please help me find the error in the code. Here, are my solutions.

The bottom 4 are an implementation of Euclidean Algorithm in which I got a WA so I tried the BFS search which gave me TLE in the next 4 submissions. I have realized that BFS would never work as it fails in test cases as simple as


Please help me debug my code for Extended Euclidean Algorithm here.

Please help.