Also, your code works.

You may be running your code with the print statements. If you print while running your code and your code is too slow, ofc it will time out. What are you trying to print, if your code times out? The input, maybe one test is causing the trouble, but there's also the probability that your code in general isn't fast enough. I tried doing print(n), and it works

@CloudClique: try with this print("Hello world!", flush=True)

EDIT: @hobovsky: I just tried it and it works.

Try flushing stdout after each print, and please let me know if it helps. I am interested if flushing helps to display truncated output in Python runner.

Any resources to share on graph theory and how that helped you find the solution? Its been a decade since I took Discrete.

100 random tests and 5 assertions per test. I let you do the maths.