package main

import (
	"bufio"
	"os"
	"strconv"
)

func main() {
	scanner := bufio.NewScanner(os.Stdin)
	scanner.Split(bufio.ScanWords)
	
	out := bufio.NewWriter(os.Stdout)
	defer out.Flush()

	nextInt := func() int {
		scanner.Scan()
		res, _ := strconv.Atoi(scanner.Text())
		return res
	}

	if !scanner.Scan() {
		return
	}
	n, _ := strconv.Atoi(scanner.Text())
	m := nextInt()

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

	var find func(int) int
	find = func(i int) int {
		root := i
		for root != parent[root] {
			root = parent[root]
		}
		curr := i
		for curr != root {
			nxt := parent[curr]
			parent[curr] = root
			curr = nxt
		}
		return root
	}

	power := 1
	mod := 1000000009

	for i := 0; i < m; i++ {
		u := nextInt()
		v := nextInt()

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

		if rootU != rootV {
			parent[rootU] = rootV
		} else {
			power = (power * 2) % mod
		}

		ans := power - 1
		if ans < 0 {
			ans += mod
		}
		
		out.WriteString(strconv.Itoa(ans) + "\n")
	}
}