A Path Problem

View as PDF

Points: 7
Time limit: 1.0s
Java 2.5s
Memory limit: 64M
Java 256M

Author:
Problem types

Given a forest of trees containing $$N$$ nodes and $$M$$ 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

5 2
1 3
2 3

Sample Output 1

11

Sample Input 2

9876 0

Sample Output 2

9876