// inputに入力データ全体が入る
function Main(input) {
	input = input.split("\n");
	const input1 = input[0].split(" ");
	const N = parseInt(input1[0]);
	const K = parseInt(input1[1]);
	const Es = input.slice(1).map(x => x.split(" ").map(y => parseInt(y)));
	const ns = new Array(N);
	const nns = {};
	Es.forEach(edge => {
		if (ns[edge[0]]) {
			ns[edge[0]]++;
		} else {
			ns[edge[0]] = 1;
		}
		if (nns[edge[0]]) {
			nns[edge[0]].push(edge[1]);
		} else {
			nns[edge[0]] = [edge[1]];
		}

		if (ns[edge[1]]) {
			ns[edge[1]]++;
		} else {
			ns[edge[1]] = 1;
		}
		if (nns[edge[1]]) {
			nns[edge[1]].push(edge[0]);
		} else {
			nns[edge[1]] = [edge[0]];
		}

	})
	console.log(nns);
	var isCant = false;
	ns.forEach(n => isCant = n + 1 > K || isCant);
	if (isCant) {
		console.log(0);
	} else {
		var count = K;
		var roots = [0];
		var next = [];
		var a = [];
		while (true) {
			roots.forEach(x => {
				var n = 0;
				nns[x].forEach(y => {
					if (!a.includes(y)) {
						n++;
						if (ns[y] != 1) next.push(y);
					}
				});
				if (n != 0) {
					for (s = 0; s < n; n++) {
						count *= K - s;
					}
					a.push(x);
				}
			})
			if (next.length == 0) {
				break;
			} else {
				roots = next;
				next = [];
			}
		}
		console.log(count);
	}
}
//*この行以降は編集しないでください（標準入出力から一度に読み込み、Mainを呼び出します）
Main(require("fs").readFileSync("/dev/stdin", "utf8"));