Generate Tree

#include "testlib.h"
#include <vector>

std::vector<int> P;

int Root(int X) {
	return X == P[X] ? X : P[X] = Root(P[X]);
}

void GenTree(int N, std::vector<std::pair<int, int> > &M) {

	P.resize(N);
	for (int i = 0; i < N; i++) P[i] = i;

	M.resize(N - 1);
	for (int i = 0; i < N - 1; i++) {
		int u, v;
		do {
			u = rnd.next(N);
			v = rnd.next(N);
		} while (Root(u) == Root(v));
		P[Root(u)] = Root(v);
		M[i].first = u;
		M[i].second = v;
	}
}

int main(int argc, char *argv[]) {
	registerGen(argc, argv, 1);

	int N = 7;

	std::vector<std::pair<int, int> > E;
	GenTree(N, E);

	printf("%d\n", N);
	for (int i = 0; i < N - 1; i++) printf("%d %d\n", E[i].first, E[i].second);

	return 0;
}