Global Connectivity via Flight Operations

There are \(N\) countries and \(M\) bidirectional flights connecting different countries. Note that there may be multiple flights connecting the same two countries. In the current pandemic, uniting the world to fight the disease is crucial. We say that the world is connected if and only if any two countries can reach each other (directly or indirectly) via the flights.

Let \(V=\{1,2,\dots,N\}\). In one operation, you may choose an arbitrary country \(u\in V\) and modify the flight network as follows:

• Define \(S\) as the set of countries that are connected to \(u\) by exactly one flight (i.e. if there is exactly one flight between \(u\) and \(v\), then \(v\in S\)).
• Let \(T=V\setminus\{u\}\setminus S\).
• For every \(v\in S\), delete the flight between \(u\) and \(v\). For every \(w\in T\), add a flight connecting \(u\) and \(w\) (if a flight already exists, add an extra one; recall that multiple flights are allowed).

Note that the effect of an operation on \(u\) is:

[ \text{new count}(u,v)= \begin{cases}0,&\text{if }\text{old count}(u,v)=1,\ \text{old count}(u,v)+1,&\text{if }\text{old count}(u,v)=0 \text{ or } \ge 2.\end{cases} ]

The final network is considered connected if every pair of countries is connected (directly or indirectly).

It can be proved that by adding sufficiently many flights (via operations) the world will eventually become connected. Your task is to achieve connectivity with the minimum number of operations. Moreover, under this minimum number of operations, find the number of different operation sequences modulo \(10^9+7\). Two operation sequences are considered different if there exists an index \(i\) such that the chosen country \(u\) in the \(i\)th operation is different.

---

Operation Validity

Observe that when an operation is performed on country \(u\), for each country \(v\) (\(v\neq u\)):

• If the flight count \(\text{old count}(u,v)=0\) or \(\ge 2\), then after the operation an edge is (added and remains) between \(u\) and \(v\).
• If \(\text{old count}(u,v)=1\), then the flight is removed.

This means that if \(u\) is originally connected to every other country by a unique flight, then after the operation all these direct connections are lost. However, note that countries in other connected components (with respect to the original network) are always not adjacent to \(u\) (i.e. count 0) so they will acquire a direct connection from \(u\) after the operation.

Minimum Operations Strategy

We call a vertex \(u\) safe if performing an operation on \(u\) will not disconnect the connectivity within its own connected component. In other words, if country \(u\) is in a component \(C\) of size \(s\), let \(\text{Adj}(u)\) be the set of countries directly connected to \(u\) in the initial network. Then \(u\) is safe if either:

• \(s=1\) (an isolated country), or
• \( |\text{Adj}(u)| < s-1 \) (i.e. there exists at least one country in \(C\) not directly connected to \(u\), so an edge will be added), or
• \( |\text{Adj}(u)| = s-1 \) but for at least one neighbor \(v\), there are multiple flights (i.e. the flight count is \(\ge 2\)) so that edge remains after the operation.

It turns out that:

• If the initial network is already connected, then \(k=0\) with exactly 1 valid (empty) operation sequence.
• If the network is disconnected and there is at least one safe vertex (in any component), then a single operation on any safe vertex will merge all components. In this case, \(k=1\) and the answer is the total number of safe vertices across all components.
• If the network is disconnected and every component is "unsafe" (which can happen when every connected component has exactly 2 countries connected by a unique flight), then an operation on any vertex in such a component breaks that component. In order to fix it, you must perform an additional operation on the partner in that component. In this scenario, \(k=2\) and the number of valid sequences equals \(2\) for each component (that is, \(2r\) if there are \(r\) components).

Your task is to compute and output the minimal number of operations \(k\) and the number of different valid operation sequences modulo \(10^9+7\).

inputFormat

The first line contains two integers \(N\) and \(M\) (\(1 \leq N \leq 10^5\), \(0 \leq M \leq 10^5\)). Each of the next \(M\) lines contains two integers \(u\) and \(v\) (\(1 \le u,v \le N, u \neq v\)) representing a bidirectional flight between countries \(u\) and \(v\). Note that there may be multiple flights between the same two countries.

outputFormat

Output two space‐separated integers: the minimum number of operations \(k\) and the number of valid operation sequences modulo \(10^9+7\).

sample

3 3
1 2
2 3
1 3

0 1