When I read this problem, I was thinking about Edmonds' algorithm, but it runs in , which is not OK for the last 10 tests. Besides, in graph_generator.py, there are no conditions that guarantee there exists a perfect matching. So, we can't…

We are asked to calculate the number of ways to make a valid pattern on Android lock screen. This problem is equivalent to counting different simple Hamiltonian paths on a graph. Since the number of nodes are small (but big enough so that …