My solution works 5.5 sec on the following test. I believe my computer is faster than yours. So, please add this test and make me lose AC.
10 27
a b
a c
a d
a e
a f
a g
a h
a i
a j
d h
d i
d j
e f
e g
e h
e i
e j
f g
f h
f i
f j
g h
g i
g j
h i
h j
i j
a

Why did you add the test which is not formatted correctly ?

I had go to my old pascal code, install some compiler for it and then it appears that the input format of that test is incorrect and that's why my solution fails.