index.md

網路連線 (connection)

AGC (Advanced Gaming Community) 是踢歐埃國數一數二盛大的電競平台，今年的全國初賽即將舉行，不過主辦方遇到了伺服器的設置問題。

AGC 總共建置了 $N$ 台伺服器，編號為 $1$ 至 $N$，在這 $N$ 台伺服器間共有 $M$ 個遠端通道，第 $i$ 條連接 $(u_i, v_i)$ 兩台伺服器（$u_i < v_i$），主辦方建立的遠端通道滿足下列兩個條件：

• 沒有連接兩個相同伺服器的遠端通道，也就是對所有的通道，$u_i \neq v_i$。
• 沒有兩個連接相同伺服器對的遠端通道，也就是對所有 $i \neq j$ 則 $(u_i, v_i) \neq (u_j, v_j)$。

我們說兩個伺服器 $a, b$ 可以傳輸訊息如果存在一系列的伺服器 $p_0, p_1, \ldots, p_t$ 滿足 $p_0 = a, p_t = b$ 且所有 $p_i, p_{i+1}$ 都有遠端通道連接，換句話說，由伺服器作為點而遠端通道作為邊的圖上，兩個點是連通的。

顯而易見的，僅僅遵守主辦方的條件只能保證沒有建立重複無效的邊，而沒有保證任意兩個伺服器皆可以傳輸訊息，現在你身為 AGC 的工程顧問，你想要知道有多少種新增剛好 $k$ 個遠端通道的方法能夠使得任意兩個伺服器皆可以傳輸訊息。

所有方法都必須滿足原本主辦方的兩個條件，而兩個方法不同如果它們新增遠端通道的集合不同，例如方案 ${(a, b), (c, d)}$ 與方案 ${(c, d), (b, a)}$ 被視為相同。

\clearpage

輸入

輸入的第一行有三個整數 $N, M, k$，接著有 $M$ 行，第 $i$ 行有兩個整數 $u_i, v_i$。

輸出

輸出有多少種新增剛好 $k$ 個遠端通道的方法滿足主辦方的兩個條件，而且任意兩個伺服器都能傳輸訊息。

輸入限制

• $1 \leq N \leq 80000$
• $0 \leq M \leq \min\left(\frac{N(N-1)}{2}, 10^6\right)$
• $1 \leq k \leq 2$
• $1 \leq u_i &lt; v_i \leq N$
• $(u_i, v_i) \neq (u_j, v_j) \quad (i \neq j)$

子任務

\subtasks

\clearpage

範例輸入 1

\testfile{0-01.in}

範例輸出 1

\testfile{0-01.out}

範例輸入 2

\testfile{0-02.in}

範例輸出 2

\testfile{0-02.out}

範例輸入 3

\testfile{0-03.in}

範例輸出 3

\testfile{0-03.out}