Hello, Codeforces! Recently I have been reading about relationship between flows and matchings and I've decided to solve a couple of problems related to this topic. So, before starting the problems, I implemented Hopcroft-Karp algorithm for matching in bipartite graphs and tested it here: Link.

While solving the "Dominoes" problem (unfortunately, I haven't found this problem somewhere except eolymp: this or this, they are completely same), it turned out, that my implementation actually TLEs on a certain testcases. Since constraints are small enough, I tried to find matching with Dinic and then with Kuhn, and these submissions got AC as they should.

So, I felt in doubt about correctness of my Hopcroft-Karp implementation — since it TLEs, there must be an infinite cycle. I've spent hours to prove for myself that my implementation is actually correct, and seems that it is — I'm unable to find the mistake. I have no clue what is wrong with it, and I don't have any testcase which make Hopcroft-Karp to work infinitely.

Kuhn AC Dinic AC Hopcroft-Karp TLE

Note: the main logic is completely the same. Any help would be appreciated. Thanks in advance.