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

// Here you should verify both the syntax and validity of your input.
// Use the Validator class in the validation.h header for checking.

struct UnionFind {
	vector<int> par, rank;
	int c;
	UnionFind(int n) : par(n), rank(n, 0), c(n) {
		for(int i = 0; i < n; ++i) par[i] = i;
	}
	int find(int i) { return (par[i] == i ? i : (par[i] = find(par[i]))); }
	int count() { return c; }
	void merge(int i, int j) {
		if((i = find(i)) == (j = find(j))) return;
		c--;
		if(rank[i] > rank[j]) swap(i, j);
		par[i] = j;
		if(rank[i] == rank[j]) rank[j]++;
	}
};

int main(int argc, char **argv) {
	InputValidator v;
	int n = v.read_long_long(2, 100000);
	v.space();
	int p = v.read_long_long(0, n - 1);
	v.newline();

	UnionFind uf(n);
	for(int i = 0; i < n - 1; ++i) {
		int a = v.read_long_long(0, n-1);
		v.space();
		int b = v.read_long_long(0, n-1);
		v.newline();
		if(a == b) v.WA("Edge must not be a loop!");
		uf.merge(a, b);
	}
	if(uf.count() != 1) v.WA("The graph is not connected!");
}