Simple Problem#12288
Sign in

Simple Problem

2 seconds
256 megabytes
Very hard

The author got tired of describing stories about Rudolandyia, so the problem will be without a legend.

You are given a directed acyclic graph with vertices and edges. You can remove any edges. You need to leave the minimum number of edges such that, after the removal of edges, the set of all possible topological sorts does not change.

By topological sorting of a directed acyclic graph, we understand any linear order of its vertices such that for every edge (u \to v), vertex appears before vertex in this order.

Input

The first line contains two integers and (1 \le n, m \le 10^5) — the number of vertices and edges in the graph, respectively.

In the next lines, there are two integers and (1 \le v, u \le n) — a directed edge from vertex to vertex .

Output

You need to output the minimum number of edges and the edges that need to be kept.

Examples

Example 1

Loading
Loading

Note

We have the following graph:

Then the set of topological sorts will not change when removing the following edges:

1 \to 3 and edge 4 \to 3.

Scoring

  1. Subtask ( points): (n,m \le 15)

  2. Subtask ( points): (n \le 100)

  3. Subtask ( points): (n \le 500)

  4. Subtask ( points): (n,m \le 5000)

  5. Subtask ( points): (The graph is generated in the form of a bamboo with additional edges)

  6. Subtask ( points): (\deg_v \le 2)

  7. Subtask ( points): No additional constraints