There aren cities andm flight connections between them. Your task is to add new flights so that it will be possible to travel from any city to any other city. What is the minimum number of new flights required?

Input

The first input line has two integersn andm: the number of cities and flights. The cities are numbered1,2,\dots,n.

After this, there arem lines describing the flights. Each line has two integersa andb: there is a flight from citya to cityb. All flights are one-way flights.

Output

First print an integerk: the required number of new flights. After this, printk lines describing the new flights. You can print any valid solution.

Constraints

• 1 \le n \le 10^5
• 1 \le m \le 2 \cdot 10^5
• 1 \le a,b \le n

Example

Input:

4 51 22 33 11 43 4

Output:

14 2