Mr. Malnar is globally recognized as an authority on many things. For example, he is an authority on the quality of cured meat products, the organic cultivation of hot peppers on balconies, the tasting of grape-based juices, and many other things. In this problem, we will deal with a problem that is currently bothering him, and we will explore how Mr. Malnar will solve his problem using his unquestionable authority in the aviation industry.

Mr. Malnar had flights to Singapore and Moscow scheduled this year. He had already booked plane tickets, chosen spacious accommodation, and studied the best wellness & spa destinations. Unfortunately, due to the epidemiological crisis, the trips were canceled. Devastated and worried, he immediately started studying flight schedules and the general state of the aviation industry and noticed that the world is no longer connected. "This cannot be, I must save the world immediately!", thought Mr. Malnar and got to work.

There are $N$ airports and $M$ flight routes in the world. Airports are labeled with natural numbers from $1$ to $N$, and each flight route connects two different airports, which means that planes can travel in both directions between those two airports. Under normal circumstances, it was possible to travel from any airport to any other airport using one or more flight routes, meaning the world was connected. Mr. Malnar will reconnect the world with just a few phone calls. Each call will be made to an airport, some calls might be made to the same airport multiple times, and they will go something like this:

Airport representative: Good day! You have reached an airport, how can I help you?

Mr. Malnar: Good day, Mr. Malnar on the phone. I noticed that your flight routes make no sense and that you need to do the exact opposite. That is, let set $A$ contain the airports you are directly connected to by a flight route, and let set $B$ contain all other airports. I want you to cancel all flight routes that connect your airport and airports from set $A$, and introduce flight routes that will connect your airport and airports from set $B$. I have some work to do now so I must go, you do as I said.

Airport representative: We apologize for the oversight, we will proceed as you said.

Your task is to determine the minimum number of phone calls Mr. Malnar must make to reconnect the world. Also, determine how many different ways he could make the calls such that the number of calls made is still minimal. The number of ways should be printed modulo $10^9 + 7$. It is possible to prove that, using enough phone calls, Mr. Malnar can always save the world.

Input

The first line contains natural numbers $N$ and $M$ from the problem description.

In the $i$-th of the next $M$ lines, there are two natural numbers $a_i$ and $b_i$ ($1 \le a_i, b_i \le N, a_i \neq b_i$) which indicate that there is a flight route between airports labeled $a_i$ and $b_i$. There will not be two flight routes connecting the same pair of airports.

Output

In the first line, print the required minimum number of phone calls from the problem description.

In the second line, print the required number of ways from the problem description modulo $10^9 + 7$.

Subtasks

Solutions that print the correct first line and an incorrect second line (or do not print it at all) on a test case will receive 15% of the points assigned to that test case.

The number of points for a subtask is equal to the minimum number of points your solution achieves on any of the test cases of that subtask.

Examples

Input 1

6 6
3 4
1 2
2 3
5 4
4 1
4 6

Output 1

0
1

Note 1

The world is already connected, so Mr. Malnar does not need to make any calls.

Input 2

4 2
1 4
2 3

Output 2

2
4

Note 2

The following sequences of calls are the shortest among those that make the world connected: $(1, 4), (4, 1), (2, 3), (3, 2)$.

Input 3

8 9
1 4
2 3
6 7
8 5
2 4
7 8
5 6
6 8
4 3

Output 3

1
5