Cow Gathering with One Reversal Path

Farmer John has installed one-way cow paths on his farm consisting of N fields labeled 1 through N. Each one-way path allows cows to travel only in the designated direction. Bessie, the cow, starts at field 1 at the beginning of the day and must return to field 1 at the end. She wishes to maximize the number of distinct fields she visits. Normally she can only follow the directed paths; however, she is allowed to choose one path to travel in the reverse direction (i.e. against the arrow) during her journey. Note that she may only travel backwards on at most one path and cannot use the same path in reverse more than once.

More formally, suppose there is a directed edge from field X to field Y (written as \(X \to Y\)). Bessie may, along her route starting and ending at field 1, pick at most one edge \(X \to Y\> and traverse it backwards as if it were \(Y \to X\). In all other cases she must follow the paths in the given direction. Bessie only benefits from visiting a field once (i.e. a field is only counted once even if she visits it multiple times).

Your task is to compute the maximum number of distinct fields Bessie can visit when she is allowed to take at most one reverse traversal.

Hint: Let \(A\) be the set of fields reachable from field 1 via forward paths and \(B\) be the set of fields that can reach field 1 (i.e. there is a forward path from the field to 1). Without any reversal, Bessie is limited to \(A \cap B\). With one reversal available, if there exists any edge \(v \to u\) such that \(u\) is in \(A\) and \(v\) is in \(B\), then she can combine the routes to visit up to \(A \cup B\) fields.

inputFormat

The first line contains two integers \(N\) and \(M\) (\(1 \leq N \leq 10^5\), \(1 \leq M \leq 10^5\)), representing the number of fields and the number of one-way paths, respectively.

Each of the following \(M\) lines contains two integers \(X\) and \(Y\) (\(1 \leq X,Y \leq N\)), indicating a directed edge from field \(X\) to field \(Y\).

It is guaranteed that there is at most one directed edge between any pair of fields.

outputFormat

Output a single integer which is the maximum number of distinct fields that Bessie can visit on a route starting and ending at field 1, while using at most one reverse path.

sample

4 4
1 2
2 3
3 1
2 4

4