每次按一个开关就会改变两盏灯的状态，考虑把这种关系在一张图上表示出来。在图上把所有可能同时改变状态的灯连边，让亮灯的点的值为 \(1\)，不亮的为 \(0\)，那么每次按灯就是把连接一条边的两点的值都异或上 \(1\)，最终要让所有点的值都为 \(0\)。
由于每个点的度都大于 \(1\) 且图上共有 \(n\) 个点和 \(n\) 条边，发现这是一个基环树森林。对每棵基环树单独考虑，对于不在环上的边组成的若干条链，先贪心地尝试消除链上值为 \(1\) 的点，如果还有剩余，就转移到环上消除。如下图：
其中 \(1,2,3,5\) 的值为 \(1\)。
这里有两种方案：
- \(1-2,3-5\)
- \(1-5,2-3\)
两种方案的路径在环上交替出现，选择一种更优的即可。
实现方面，由于每次只能同时消两个点，如果值为 \(1\) 的点有奇数个，那么无解。对于有解的情况，先用拓扑排序找链，由于点在链上，所以只会遇到一个还未更新的点。如果当前点值为 \(1\)，就向下一个点转移。然后对于每个环，把两种方案所对应的边和代价都记录下来，选取更优的即可。
时间复杂度 \(O(n)\)，有些常数。