A Path Problem

View as PDF

Submit solution

Points: 7
Time limit: 1.0s
Memory limit: 64M

Author:
Problem types

Given a forest of trees containing N nodes and bidirectional edges, output the number of paths in the forest of trees. A path is defined as a sequence of nodes which are connected by edges in the forest of trees, and the sequence contains at least one node. A path is different from another path if the starting or ending nodes differ. For example, a path from a to b is different from a path from b to a.

Input Specification

The first line will contain 2 integers, N, M (1 \le N \le 10^6, 0 \le M < N), the number of nodes and the number of edges respectively.

The next M lines will each contain 2 integers, a, b (1 \le a \le b \le N), indicating that node a and node b are connected by a single edge. It is guaranteed that there will be no cycles in the forest of trees.

Output Specification

Output one integer, the number of paths in the forest of trees.

Sample Input 1

Copy
5 2
1 3
2 3

Sample Output 1

Copy
11

Sample Input 2

Copy
9876 0

Sample Output 2

Copy
9876

Comments

There are no comments at the moment.