《程序设计基础二》类的设计部分练习题目:1432--1446,运算符重载部分练习题目:1447--1461

Problem 1976. -- 网络寻路

1976: 网络寻路

Time Limit: 1 Sec  Memory Limit: 128 MB   64bit IO Format: %lld
Submitted: 52  Accepted: 13
[Submit][Status][Web Board]

Description

X 国的一个网络使用若干条线路连接若干个节点。节点间的通信是双向的。某重要数据包,为了安全起见,必须恰好被转发两次到达目的地。该包可能在任意一个节点产生,我们需要知道该网络中一共有多少种不同的转发路径。

源地址和目标地址可以相同,但中间节点必须不同。

例如对于有4个结点的网络,其中结点1和2,结点1和3,结点2和3,结点2和4,结点2和5,结点3和5均有线路连接。则路径1 -> 2 -> 3 -> 1 是允许的,而路径1 -> 2 -> 1 -> 2 或者 1 -> 2 -> 3 -> 2 都是非法的。

Input

多组测试数据。每组测试数据输入格式如下。

第一行为两个整数N M,分别表示节点个数和连接线路的条数(1<=N<=10000; 0<=M<=100000)

接下去有M行,每行为两个整数 u v,表示节点u v 联通(1<=u,v<=N , u!=v)

输入数据保证任意两点最多只有一条边连接,并且没有自己连自己的边,即不存在重边和自环。

Output

每组测试数据占一行,输出一个整数,表示满足要求的路径条数。

Sample Input

3 3
1 2
2 3
1 3
4 4
1 2
2 3
3 1
1 4

Sample Output

6
10

[Submit][Status][Web Board]