Authority

Mr. Malnar is recognized worldwide as an authority on many things. For example, he is an authority on the quality of cured meats, growing hot peppers organically on a balcony, tasting grape juice, and many other things. In this problem he faces a difficulty, and we will look at how he solves it using his authority in the aviation industry.

This year Mr. Malnar had flights booked to Singapore and Moscow. He had already bought the plane tickets, chosen a spacious hotel, and researched the best wellness and spa destinations. Unfortunately, the epidemic crisis cancelled the trips. Shaken and worried, he immediately began studying the flight routes and the general state of the aviation industry, and noticed that the world is no longer connected. "This cannot go on, I have to save the world right away!" thought Mr. Malnar, and threw himself into the work.

There are $N$ airports and $M$ air routes in the world. Airports are numbered with natural numbers from $1$ to $N$, and each air route connects two different airports, which means planes can travel in both directions between those two airports. Under normal circumstances it was possible to travel from every airport to every other airport using one or more air routes, that is, the world was connected. Mr. Malnar will reconnect the world with just a few phone calls. Each call is made to some airport, some airports may receive several calls, and the conversation goes roughly like this:

Airport representative: Hello! You have reached the airport, how can I help you?

Mr. Malnar: Hello, this is Mr. Malnar speaking. I have noticed that your air routes make no sense, and you need to do the exact opposite. Let set $A$ contain the airports you are directly connected to by an air route, and let set $B$ contain all the other airports. I want you to remove all air routes connecting your airport and the airports in set $A$, and add air routes connecting your airport and the airports in set $B$. I have some business now, so I have to go. Please do what I said.

Airport representative: We apologize for the mistake, we will do as you said.

Your task is to find the minimum number of phone calls Mr. Malnar must make to reconnect the world. Also find how many different ways he can make calls while keeping the number of calls minimal. Print the number of ways modulo $10^9 + 7$. It is possible to prove that with enough phone calls, Mr. Malnar can always save the world.

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

Each of the next $M$ lines contains two natural numbers $a\_i$ and $b\_i$ ($1 ≤ a\_i , b\_i ≤ N$, $a\_i ≠ b\_i$), meaning there is an air route between airports $a\_i$ and $b\_i$. No two air routes connect the same pair of airports.

On the first line, print the minimum number of phone calls from the statement.

On the second line, print the number of ways from the statement modulo $10^9 + 7$.

First sample: the world is already connected, so Mr. Malnar does not need to make any call.

Second sample: the following call sequences are the shortest ones that make the world connected: $(1, 4)$, $(4, 1)$, $(2, 3)$, $(3, 2)$.