I got AC with a somehow optimized backtracking that generated partitions for N. When I reached a partition with K critical edges -> solution. But with a value of K well chosen (maximum K for which we do not have all pairs critical) this approach should TLE.
Test is N = 100, K = 4947

Your test was added.

Finally AC, very nice problem! Replaced the backtracking with a recursive formula, used also the first two of the Viete relations.

Edited by author 14.07.2011 19:33