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