【codechef】 Historical Junctions（开放想方法，分类）

Input:
2
4 4
1 2
2 3
3 4
4 1
4 6
1 2
2 3
3 4
4 1
1 3
2 4Output:
4 4
1 5
2 6
3 7
4 8
0 0

http://www.codechef.com/SNCK151A/problems/HISTJUNK

当n<3||(n==3&&m==3)时：

虽然4的这种情况也是，不过简单起见我们也可以选择加边（1-3是因为“不能新建超过n*(n-1)的规定”特判）

其他情况：当n=3时要特别考虑。

其他（n>=4）：

#include <algorithm>
#include <bitset>
#include <cassert>
#include <cctype>
#include <cmath>
#include <complex>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <ctime>
#include <iostream>
#include <map>
#include <queue>
#include <set>
#include <string>
#include <utility>
#include <vector>
using namespace std;
int n, m;
int dg[105];
int main() {	int tc, i, j, k;	for (scanf("%d", &tc); tc--; ) {scanf("%d%d", &n, &m);fill_n(dg, n + 1, 0);for (k = 0; k < m; k++) {scanf("%d%d", &i, &j);dg[i]++, dg[j]++;}if (n <= 2 || n == 3 && m == 3) {puts("0 0");continue;}if (n == 3) {puts("2 3");for (i = 1; i <= 3; i++) {if (dg[i] == 2) printf("%d 5\n", i);else printf("%d 4\n", i);}continue;}printf("4 %d\n", 2 * n + 2);for (i = 1; i <= n; i++) {printf("%d %d\n", i, n + 1);printf("%d %d\n", i, n + 2);}printf("%d %d\n", n + 1, n + 3);printf("%d %d\n", n + 2, n + 4);}return 0;
}