暂无测试数据。

Background

Description

遥远的星系中共有n颗行星，由m个双向虫洞所连接。两颗不同行星间最多有1个虫洞直接相连，但一个虫洞的两端可能连接同一颗行星。一条星际旅行的航线需要满足以下要求：从任意一颗行星出发，在任意一颗行星上结束，总共经过m−2个虫洞恰好2次，经过2个虫洞恰好1次。现在我们想要知道，有多少种本质不同的旅行航线。两条航线被认为本质不同，当且仅当至少存在一个虫洞，在两条航线中经过的次数不同。

Format

Input

第一行两个整数n,m，表示行星和虫洞的数量。 接下来m行，每行两个整数u,v，表示存在一个双向虫洞直接连接u和v。每一个虫洞最多会被描述一次。

Output

一行一个整数，代表本质不同的航线的数量。

Sample

Input

5 4
1 2
1 3
1 4
1 5

Output

6

Explanation

本质不同的航线有6条：
• 2 - 1 - 3 - 1 - 4 - 1 - 5
• 2 - 1 - 3 - 1 - 5 - 1 - 4
• 2 - 1 - 4 - 1 - 5 - 1 - 3
• 3 - 1 - 2 - 1 - 5 - 1 - 4
• 3 - 1 - 2 - 1 - 4 - 1 - 5
• 4 - 1 - 2 - 1 - 3 - 1 - 5
注意 2 - 1 - 4 - 1 - 3 - 1 - 5 不是另一个本质不同的航线，它与第一条航线是本质相同的。

Limitation

对于10%的数据，n,m ≤ 5。
对于20%的数据，n,m ≤ 10。
对于40%的数据，n,m ≤ 100。
对于60%的数据，n,m ≤ 1000。
对于所有数据，1 ≤ n,m ≤ 105，1 ≤ u,v ≤ n。
1s, 256000KiB for each test case.

Hint

Source

CDQZ TEST