I was trying to solve problem D from past tourist's contest using Hopcroft-Karp's algorithm. Here's my code

Yeah, I know that this problem has an easier greedy solution but I just want to check if it is possible to solve such a problem with a complicated algorithm at all. I've done some randomized tests for my code and they showed that on test cases where t = 1 and n = 2e5 my submission would get AC 62ms but on test cases where t = 1e4 and n = 20 my code exceeds 15 sec.

I don't know what the problem is. Time complexity of Hopcroft-Karp is O(E*sqrt(V)) which is O(t * N*sqrt(N)) in my case. I have a suggestion that it can be explained by high hidden constant of the algorithm.