Background

JYY has recently become obsessed with the strong connectivity of graphs. For any directed graph, JYY wants to add some edges to make the graph strongly connected.

JYY has a directed graph with $N$ vertices and $M$ edges, where all vertices are numbered from $1$ to $n$.

JYY wants to know:

1. In the given graph, what is the maximum number of vertices that can be chosen such that every pair of these vertices is mutually reachable in the original graph?
2. What is the minimum number of edges that need to be added to the given graph to make it strongly connected?

A directed graph $G(V, E)$ is strongly connected if and only if for any two vertices $a, b \in V$ ($a \neq b$), there exists a path from $a$ to $b$ and a path from $b$ to $a$. Since adding edges is troublesome, JYY guarantees that in the optimal solution, at most 1000 edges need to be added to make the original graph strongly connected.

Input

The first line contains two integers $N$ and $M$.

The next $M$ lines each contain two integers $x$ and $y$, representing a directed edge from $x$ to $y$ in the graph.

Output

The first line of the output file contains an integer $C$, representing the answer to JYY's first question.

The second line of the output file contains an integer $K$, representing the answer to JYY's second question.

The next $K$ lines each contain two integers representing a directed edge, describing an optimal edge-addition scheme for the second question. If there are multiple optimal solutions, output any one of them.

Subtasks

For each test case:

If only the first line is correct, you get 2 points.

If the first and second lines are correct but the scheme is incorrect, you get 4 points.

If the entire output is correct, you get 10 points.

Otherwise, you get 0 points.

Examples

Input 1

4 4
1 3
1 4
2 3
2 4

Output 1

1
2
3 1
4 2

Input 2

10 12
3 7
1 2
4 5
7 10
10 8
6 8
2 1
3 8
10 3
6 8
7 3
4 1

Output 2

3
4
8 4
5 9
1 10
9 6

Note

Both example outputs receive 10 points.

Constraints

For $10\%$ of the data, $N = 6$.

For $30\%$ of the data, $N \leq 100$, $M \leq 2\,000$.

For $80\%$ of the data, $N \leq 1\,000$, $M \leq 20\,000$.

For $100\%$ of the data, $1 \leq N \leq 10^4$, $0 \leq M \leq 2 \cdot 10^5$, and the number of edges to be added in the optimal solution does not exceed 1000.