Brilliant Stars

Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's training is to train your eyesight and concentration by observing many stars shining in the night sky. Rabbits can record the characteristics of stars with their own sense.

Rabbit decided to add the characteristics of the stars recorded as "Star Observation Diary" to his notebook. Here, we want to avoid recording two "similar" stars together. Whether or not the two stars are "similar" is all determined by the rabbit's judgment. The relationship of "similarity" is not so complicated and satisfies the following conditions.

Condition: There are four different stars A, B, C, D, and A and B, B and C, and C and D are "similar" respectively. At this time, A and C are "similar", B and D are "similar", or both.

Rabbits want to record as many stars as possible without recording two "similar" stars. I also want to know how many ways to do that.

Input

N M X1 Y1 ... XM YM

N is the number of stars and M is the number of pairs of two "similar" stars. A star is represented by an integer number greater than or equal to 1 and less than or equal to N, and Xi, Yi (1 ≤ i ≤ M) indicates that the star Xi and the star Yi are "similar".

Satisfy 1 ≤ N ≤ 100,000, 0 ≤ M ≤ 200,000, 1 ≤ Xi <Yi ≤ N. The same set as (Xi, Yi) does not appear multiple times. The relationship of "similarity" satisfies the condition specified in the problem statement.

Output

The first line shows the maximum number of stars that can be recorded so that two "similar" stars are not recorded, and the second line shows the number of star combinations that can achieve that maximum (only the order in which they are recorded). Divide the changed one by 1,000,000,009 and output the remainder.

Examples

Input

4 3 1 2 1 3 1 4

Output

3 1

Input

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

Output

6 32

Input

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

Output

4 6

inputFormat

Input

N M X1 Y1 ... XM YM

N is the number of stars and M is the number of pairs of two "similar" stars. A star is represented by an integer number greater than or equal to 1 and less than or equal to N, and Xi, Yi (1 ≤ i ≤ M) indicates that the star Xi and the star Yi are "similar".

Satisfy 1 ≤ N ≤ 100,000, 0 ≤ M ≤ 200,000, 1 ≤ Xi <Yi ≤ N. The same set as (Xi, Yi) does not appear multiple times. The relationship of "similarity" satisfies the condition specified in the problem statement.

outputFormat

Output

The first line shows the maximum number of stars that can be recorded so that two "similar" stars are not recorded, and the second line shows the number of star combinations that can achieve that maximum (only the order in which they are recorded). Divide the changed one by 1,000,000,009 and output the remainder.

Examples

Input

4 3 1 2 1 3 1 4

Output

3 1

Input

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

Output

6 32

Input

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

Output

4 6

样例

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

6
32

</p>