i use O((n-1)!* n^2) and got AC in 0.109 s.
just use o(n^2) memory.
for all permutation check its valid or not, for example for this test:
4
3
1 2
2 3
3 4

the permutation 1 2 3 4 is valid but 1 3 4 2 is nonvalid.

GOOD LUCK!!!