Tree Craftsman

Time limit1sMemory limit1024 MB

Summary

Given a simple graph, count the ways to add edges so it becomes a tree, or report -1 if that count exceeds K.

Level: Medium6 of 10
Topics: Graph, Union-find, Math
Solved: No attempts yet

Problem

Sejong is a famous tree craftsman in Hanyang. Bring him any graph and he turns it into a fine tree!

You are given a simple graph with $N$ vertices and $M$ edges. A simple graph is one where every edge connects two distinct vertices, and no two vertices $u$ and $v$ are connected by more than one edge.

Sejong adds zero or more new edges between the vertices $1, 2, \ldots, N$ so that the graph becomes a tree.

Before he starts, Sejong wants to estimate how many ways there are to turn the graph into a tree. Help him check whether that number is greater than $K$ , and if it is not, find the exact count. Two ways are different only if the sets of added edges differ. All edges are undirected.

Input

The first line contains three integers $N$ , $M$ , and $K$ separated by spaces. ( $2 \le N \le 100\,000$ , $1 \le M \le 200\,000$ , $1 \le K \le 3\,000$ )

Each of the next $M$ lines contains two vertices $u_i$ and $v_i$ separated by a space, the endpoints of the $i$ -th edge. ( $1 \le u_i < v_i \le N$ , $(u_i, v_i) \ne (u_j, v_j)$ )

Output

If the number of ways to turn the graph into a tree is greater than $K$ , print -1. Otherwise, print the exact number of ways.

Examples2

Example 1
Input
```
2 1 1
1 2
```
Expected output
```
1
```
Example 2
Input
```
4 2 2
1 2
2 3
```
Expected output
```
-1
```