## GUPTA MECHANICAL

IN THIS WEBSITE I CAN TELL ALL ABOUT TECH. TIPS AND TRICKS APP REVIEWS AND UNBOXINGS ALSO TECH. NEWS .............

## Remove Directed Edges Codeforces Solution | Codeforces Problem Solution 2022

G. Remove Directed Edges
time limit per test
2 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

You are given a directed acyclic graph, consisting of $n$ vertices and $m$ edges. The vertices are numbered from $1$ to $n$. There are no multiple edges and self-loops.

Let ${\mathit{i}\mathit{n}}_{v}$ be the number of incoming edges (indegree) and ${\mathit{o}\mathit{u}\mathit{t}}_{v}$ be the number of outgoing edges (outdegree) of vertex $v$.

You are asked to remove some edges from the graph. Let the new degrees be ${\mathit{i}{\mathit{n}}^{\prime }}_{v}$ and ${\mathit{o}\mathit{u}{\mathit{t}}^{\prime }}_{v}$.

You are only allowed to remove the edges if the following conditions hold for every vertex $v$:

• ${\mathit{i}{\mathit{n}}^{\prime }}_{v}<{\mathit{i}\mathit{n}}_{v}$ or ${\mathit{i}{\mathit{n}}^{\prime }}_{v}={\mathit{i}\mathit{n}}_{v}=0$;
• ${\mathit{o}\mathit{u}{\mathit{t}}^{\prime }}_{v}<{\mathit{o}\mathit{u}\mathit{t}}_{v}$ or ${\mathit{o}\mathit{u}{\mathit{t}}^{\prime }}_{v}={\mathit{o}\mathit{u}\mathit{t}}_{v}=0$.

Let's call a set of vertices $S$ cute if for each pair of vertices $v$ and $u$ ($v\ne u$) such that $v\in S$ and $u\in S$, there exists a path either from $v$ to $u$ or from $u$ to $v$ over the non-removed edges.

What is the maximum possible size of a cute set $S$ after you remove some edges from the graph and both indegrees and outdegrees of all vertices either decrease or remain equal to $0$?

Input

The first line contains two integers $n$ and $m$ ($1\le n\le 2\cdot {10}^{5}$$0\le m\le 2\cdot {10}^{5}$) — the number of vertices and the number of edges of the graph.

Each of the next $m$ lines contains two integers $v$ and $u$ ($1\le v,u\le n$$v\ne u$) — the description of an edge.

The given edges form a valid directed acyclic graph. There are no multiple edges.

Output

Print a single integer — the maximum possible size of a cute set $S$ after you remove some edges from the graph and both indegrees and outdegrees of all vertices either decrease or remain equal to $0$.