B: Brilliant Stars

ICPC で良い成績を収めるには修行が欠かせない．うさぎは ICPC で勝ちたいので，今日も修行をすることにした．

今日の修行は，夜空に輝くたくさんの星たちを観測して，視力と集中力を鍛えようというものである．うさぎは独自のセンスで星の特徴を記録していくことができる．

うさぎは「星の観測日記」として記録した星の特徴をノートにつけていくことにした．ここで，「似ている」 2 つの星をともに記録することは避けたい．2 つの星が「似ている」かどうかは，すべてうさぎの判断で決まっている．「似ている」かどうかの関係はあまり複雑ではなく，以下の条件を満たす．

条件： 異なる 4 つの星 A, B, C, D があり，A と B，B と C，C と D がそれぞれ「似ている」とする．このとき，A と C が「似ている」か，B と D が「似ている」か，あるいはその両方が成り立つ．

うさぎは「似ている」 2 つの星を記録しないようになるべくたくさんの星を記録したい．また，そのようにする方法が何通りあるかも知りたい．

Input

N M
X1 Y1
 ...
XM YM

N は星の個数，M は「似ている」 2 つの星の組の個数である．星は 1 以上 N 以下の整数の番号により表され，X_i, Y_i (1 ≤ i ≤ M) は星 X_i と星 Y_i が「似ている」ことを表す．

1 ≤ N ≤ 100,000，0 ≤ M ≤ 200,000，1 ≤ X_i < Y_i ≤ N を満たす．(X_i, Y_i) として同一の組は複数回現れない．「似ている」かどうかの関係は，問題文で指定された条件を満たす．

Output

1 行目に，「似ている」 2 つの星を記録しないように記録できる星の個数の最大値を，2 行目に，その最大値を実現できる星の組み合わせの個数 (記録する順番のみを変えたものは同じと考える) を 1,000,000,009 で割った余りを出力せよ．

Sample Input 1

4 3
1 2
1 3
1 4

Sample Output 1

3
1

Sample Input 2

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

Sample Output 2

6
32

Sample Input 3

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

Sample Output 3

4
6