魏（2-sat）（前缀建边优化）
【题目描述】 魏国有n个城镇被分成了k个郡，有m条连接城镇的无向边。 曹操要求给每个郡选择一个城镇作为首都，满足每条边至少有一个端点是首都。 【输入格式】 第一行有三个整数，城镇数n（1<=n<=10^6），边数m（0<=m<=10^6），郡数k（1<=k<=n）。 接下来m行，每行有两个整数ai和bi（ai≠bi），表示有一条无向边连接城镇ai和bi...
