In this morning training, our team was given this problem from Prologin contest — 2015 Regional event (unfortunately, the statement is written in French, but I'll try to summarize the statement as accurate as possible):

"There are N rooms and M roads, road i directly connect room u_i with room v_i. There are also K switches, switch i can control road a_i and road b_i. More specifically, if switch j is on, roads a_i is enabled and roads b_i is disabled, and vice-versa (disabled road can't be walked on). If there is no switch controlling road i, then that road is always enabled. It's guaranteed that one road will be controlled by at most one switch, and when all switches are off, the roads system will form a tree (connected acyclic graph). Is it true that for all 2^k states of the switches, the roads system will always form a tree?"

Our teams have discussed this problem for the entire morning but failed to come up with any algorithm that can solve this problem in polynomial time. It also doesn't help that the original statement didn't give constraint of N, M, and K, too. Can someone help us on this matter? Thanks in advance.