小男孩伊戈尔想成为一名旅行者。首先,他决定参观祖国乌日扬迪亚的所有城市。
众所周知,乌日扬迪亚有 n 个城市,有 m 条双向道路相连。此外,国内不存在连接同一对城市的两条道路,但可以存在起点和终点位于同一城市的道路。伊戈尔想提前计划他的旅程。 Boy 认为,如果一条路径经过 m - 2 条道路两次,并且恰好经过另外 2 条道路一次,则该路径是好的。这条好路可以在乌日扬迪亚的任何城市开始和结束。
现在他想知道 Uzhlyandia 有多少条不同的好路。如果两条路径恰好经过一次的道路组不同,则认为两条路径不同。帮助 Igor — 计算好路径的数量。
输入
第一行包含两个整数 n, m (1 ≤ n, m ≤ 106) — 分别是乌日扬迪亚的城市和道路数量。
接下来的 m 行每行包含两个整数 u 和 v (1 ≤ u, v ≤ n),这意味着城市 u 和 v 之间有道路。
保证输入中不会出现两次道路。这也意味着对于每个城市来说,只有一条道路将城市连接起来。
输出
打印出唯一的整数——Uzhlyandia 中良好路径的数量。
示例
输入 #1
5 4 1 2 1 3 1 4 1 5
输出 #1
6
输入 #2
5 3 1 2 2 3 4 5
输出 #2
0
输入 #3
2 2 1 1 1 2
输出 #3
1
注意
在第一个示例测试用例中,好的路径是:
- 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 → 4 → 1 → 5,
- 3 → 1 → 2 → 1 → 5 → 1 → 4,
- 4 → 1 → 2 → 1 → 3 → 1 → 5.
存在与上面显示的相同的好路径,因为它们经过的道路组是相同的:
- 2 → 1 → 4 → 1 → 3 → 1 → 5,
- 2 → 1 → 5 → 1 → 3 → 1 → 4,
- 2 → 1 → 5 → 1 → 4 → 1 → 3,
- 3 → 1 → 4 → 1 → 2 → 1 → 5,
- 3 → 1 → 5 → 1 → 2 → 1 → 4,
- 4 → 1 → 3 → 1 → 2 → 1 → 5,
- 以及其他方向的所有路径。
因此,答案是 6。
在第二个测试用例中,Igor 根本无法走完所有道路。
在第三种情况中,Igor 每条路都走过一次。