[Solution] Remove Directed Edges solution codeforces

Remove Directed Edges solution codeforces – You are given a directed acyclic graph, consisting of 𝑛n vertices and 𝑚m edges. The vertices are numbered from 11 to 𝑛n. There are no multiple edges and self-loops.

[Solution] Remove Directed Edges solution codeforces

Let in𝑣inv be the number of incoming edges (indegree) and out𝑣outv 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 in𝑣in′v and out𝑣out′v.

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

  • in𝑣<in𝑣in′v<inv or in𝑣=in𝑣=0in′v=inv=0;
  • out𝑣<out𝑣out′v<outv or out𝑣=out𝑣=0out′v=outv=0.

Let’s call a set of vertices 𝑆S cute if for each pair of vertices 𝑣v and 𝑢u (𝑣𝑢v≠u) such that 𝑣𝑆v∈S and 𝑢𝑆u∈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 00?

Input

The first line contains two integers 𝑛n and 𝑚m (1𝑛21051≤n≤2⋅1050𝑚21050≤m≤2⋅105) — 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𝑣,𝑢𝑛1≤v,u≤n𝑣𝑢v≠u) — the description of an edge.

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

[Solution] Remove Directed Edges solution codeforces

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 00.

Examples
input

Copy
3 3
1 2
2 3
1 3
output

Copy
2

[Solution] Remove Directed Edges solution codeforces

input

Copy
5 0
output

Copy
1
input

Copy
7 8
7 1
1 3
6 2
2 3
7 2
2 4
7 3
6 3
output

Copy
3

Remove Directed Edges solution codeforces

In the first example, you can remove edges (1,2)(1,2) and (2,3)(2,3)in=[0,1,2]in=[0,1,2]out=[2,1,0]out=[2,1,0]in=[0,0,1]in′=[0,0,1]out=[1,0,0]out′=[1,0,0]. You can see that for all 𝑣v the conditions hold. The maximum cute set 𝑆S is formed by vertices 11 and 33. They are still connected directly by an edge, so there is a path between them.

In the second example, there are no edges. Since all in𝑣inv and out𝑣outv are equal to 00, leaving a graph with zero edges is allowed. There are 55 cute sets, each contains a single vertex. Thus, the maximum size is 11.

In the third example, you can remove edges (7,1)(7,1)(2,4)(2,4)(1,3)(1,3) and (6,2)(6,2). The maximum cute set will be 𝑆={7,3,2}S={7,3,2}. You can remove edge (7,3)(7,3) as well, and the answer won’t change.

Here is the picture of the graph from the third example:

Remove Directed Edges solution codeforces

For Solution

Click here

Leave a Comment