Brilliant Stars

Time Limit : 2 sec, Memory Limit : 65536 KB

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 以下の整数の番号により表され,Xi, Yi (1 ≤ iM) は星 Xi と星 Yi が「似ている」ことを表す.

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

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

Source: ACM-ICPC Japan Alumni Group Summer Camp 2011 , Day 2, Tokyo, Japan, 2011-09-18
http://acm-icpc.aitea.net/