Minimum Project Clusters

You are given n projects and m dependencies between them. Each dependency is a directed edge from one project to another. A cluster is defined as a set of projects such that starting from any project in the cluster, you can reach all other projects in the cluster by following the given directed dependencies.

Your task is to compute the minimum number of clusters you can form so that every project belongs to exactly one cluster. In other words, you need to determine the number of groups that are connected via dependencies (by following the dependency directionally). Note that if a project does not depend on or is not depended on by any other, it forms a cluster of its own.

The problem can be mathematically interpreted as follows: Given a directed graph with n nodes and m edges, find the number of connected components when connectivity is determined by traversing only in the direction of the edges. If there is a cycle and every node has an incoming edge, consider the entire cycle as one cluster.

Note: The dependencies are provided in the form of directed edges and the clustering is computed by performing a traversal (e.g. BFS) along the directed edges starting from each unvisited project.

inputFormat

The first line contains two space-separated integers \(n\) and \(m\), where \(n\) is the number of projects and \(m\) is the number of dependencies.

The following \(m\) lines each contain two space-separated integers \(u\) and \(v\) representing a dependency from project \(u\) to project \(v\).

You should read the input from stdin.

outputFormat

Output a single integer to stdout representing the minimum number of clusters required.

5 4
1 2
2 3
3 4
5 4

2