package main

import (
	"bufio"
	"fmt"
	"os"
)

func main() {
	in := bufio.NewReader(os.Stdin)
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	var n, m int
	fmt.Fscan(in, &n, &m)

	parent := make([]int, n+1)
	for i := 1; i <= n; i++ {
		parent[i] = i
	}

	var find func(int) int
	find = func(i int) int {
		if parent[i] == i {
			return i
		}
		parent[i] = find(parent[i])
		return parent[i]
	}

	ans := 0
	for i := 0; i < m; i++ {
		var u, v int
		fmt.Fscan(in, &u, &v)

		rootU := find(u)
		rootV := find(v)

		if rootU != rootV {
			parent[rootU] = rootV
		} else {
			ans = (ans*2 + 1) % 1000000009
		}
		fmt.Fprintln(out, ans)
	}
}