#include <vector>

#include "testlib.h"

using namespace std;

const int MAXN = 100000;
const int MAXD = 40;

bool was[MAXN];
vector<int> gr[MAXN];

void go(int cur)
{
	if (was[cur]) return;
	was[cur] = true;
	for (auto v : gr[cur]) go(v);
}

pair<int, int> find(int v) {
	int ans = v;
	int len = 0;
	was[v] = 1;
	for (int u: gr[v]) {
		if (was[u])
			continue;
		pair<int, int> x = find(u);
		if (x.second + 1 > len)
			len = x.second + 1, ans = x.first;
	}
	return make_pair(ans, len);
}

int main(int argc, char **argv)
{
	registerValidation();
	int group = atoi(argv[1]);
	
	int n = inf.readInt(1, MAXN, "n");
	inf.readEoln();
	
	for (int i = 0; i < n; i++) gr[i].clear();
	for (int i = 0; i < n - 1; i++)
	{
		int a = inf.readInt(1, n, format("a[%d]", i + 1));
		inf.readSpace();
		int b = inf.readInt(1, n, format("b[%d]", i + 1));
		inf.readEoln();
		a--, b--;
		gr[a].push_back(b);
		gr[b].push_back(a);
	}
	inf.readEof();
	
	for (int i = 0; i < n; i++) was[i] = false;
	go(0);
	for (int i = 0; i < n; i++) if (!was[i]) inf.quits(_fail, format("graph is not tree: vertex %d is not visited", i + 1));
	int flb = 1;
	int fld = 1;
	for (int i = 0; i < n; ++i)
		if ((int)gr[i].size() > 3)
			flb = 0;
	memset(was, 0, sizeof(was[0]) * n);
	int x = find(0).first;
	memset(was, 0, sizeof(was[0]) * n);
	x = find(x).second;
	if (x > MAXD)
		fld = 0;
	ensure(group != 1 || n <= 20);
	ensure(group != 2 || n <= 1000);
	ensure(group != 3 || (flb && fld));
	ensure(group != 4 || flb);
	ensure(group != 5 || fld);
	return 0;
}
