A ski base is planned to be built in Walrusland. Recently, however, the project is still in the constructing phase. A large land lot was chosen for the construction. It contains *n* ski junctions, numbered from 1 to *n*. Initially the junctions aren't connected in any way.

In the constructing process *m* bidirectional ski roads will be built. The roads are built one after another: first the road number 1 will be built, then the road number 2, and so on. The *i*-th road connects the junctions with numbers *a*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub>.

Track is the route with the following properties: 
-  The route is closed, that is, it begins and ends in one and the same junction.-  The route contains at least one road. -  The route doesn't go on one road more than once, however it can visit any junction any number of times. 
Let's consider the ski base as a non-empty set of roads that can be divided into one or more tracks so that exactly one track went along each road of the chosen set. Besides, each track can consist only of roads from the chosen set. Ski base doesn't have to be connected.

Two ski bases are considered different if they consist of different road sets.

After building each new road the Walrusland government wants to know the number of variants of choosing a ski base based on some subset of the already built roads. The government asks you to help them solve the given problem.
The first line contains two integers *n* and *m* (2 ≤ *n* ≤ 10<sup class="upper-index">5</sup>, 1 ≤ *m* ≤ 10<sup class="upper-index">5</sup>). They represent the number of junctions and the number of roads correspondingly. Then on *m* lines follows the description of the roads in the order in which they were built. Each road is described by a pair of integers *a*<sub class="lower-index">*i*</sub> and *b*<sub class="lower-index">*i*</sub> (1 ≤ *a*<sub class="lower-index">*i*</sub>, *b*<sub class="lower-index">*i*</sub> ≤ *n*, *a*<sub class="lower-index">*i*</sub> ≠ *b*<sub class="lower-index">*i*</sub>) — the numbers of the connected junctions. There could be more than one road between a pair of junctions.
Let us have 3 junctions and 4 roads between the junctions have already been built (as after building all the roads in the sample): 1 and 3, 2 and 3, 2 roads between junctions 1 and 2. The land lot for the construction will look like this:

The land lot for the construction will look in the following way:

We can choose a subset of roads in three ways:

In the first and the second ways you can choose one path, for example, 1 - 2 - 3 - 1. In the first case you can choose one path 1 - 2 - 1.
3 4
1 3
2 3
1 2
1 2
0
0
1
3
15 29
6 11
14 3
10 4
14 7
6 14
7 15
13 8
10 13
4 14
15 8
12 7
3 5
6 7
8 1
4 5
11 5
10 6
11 3
13 14
7 10
3 12
7 14
8 11
7 15
15 8
12 7
4 3
9 4
8 10
0
0
0
0
0
0
0
0
0
1
1
1
3
3
7
15
31
63
127
255
511
1023
2047
4095
8191
16383
32767
32767
65535
34 27
19 10
8 31
26 22
2 30
32 26
30 4
34 1
2 31
4 18
33 11
10 13
20 23
4 32
23 27
30 7
10 17
29 9
18 10
2 28
3 12
31 8
3 25
5 22
3 16
21 1
10 30
5 3
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
1
1
3
3
29 27
22 8
6 2
3 5
23 29
27 23
18 23
28 23
23 12
24 15
13 6
1 13
9 7
17 6
4 16
20 28
23 3
3 19
16 23
10 21
15 2
21 28
3 9
8 18
10 28
19 18
17 18
13 7
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
3
3
7
27 28
20 14
21 5
11 17
14 9
17 13
7 19
24 27
16 9
5 1
2 12
9 2
15 7
13 6
15 17
25 17
2 3
1 15
12 25
10 6
1 8
1 6
5 24
3 15
12 7
2 12
16 15
8 22
8 18
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
3
7
15
31
31
31
20 29
8 13
19 18
5 20
5 10
14 11
20 8
12 11
13 20
18 10
3 9
7 18
19 13
2 6
20 19
9 3
6 10
14 18
16 12
17 20
1 15
14 12
13 5
11 4
2 16
3 1
11 4
17 5
5 8
18 12
0
0
0
0
0
0
0
1
1
1
1
3
3
7
15
15
15
15
15
15
31
63
63
127
127
255
511
1023
2047
28 25
17 28
21 3
4 7
17 18
13 12
26 20
1 17
10 18
10 16
1 4
15 3
27 26
11 14
7 9
1 13
14 27
14 23
21 27
8 7
16 2
5 25
26 18
21 2
4 3
4 10
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
3
7
27 29
12 11
21 20
19 26
16 24
22 4
1 3
23 5
9 1
4 3
21 23
22 8
14 6
25 13
7 20
9 16
3 20
23 19
17 10
13 18
8 14
23 25
25 27
19 15
19 15
17 24
12 27
18 11
25 5
22 17
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
0
1
1
1
3
7
15
2 40
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
1 2
0
1
3
7
15
31
63
127
255
511
1023
2047
4095
8191
16383
32767
65535
131071
262143
524287
1048575
2097151
4194303
8388607
16777215
33554431
67108863
134217727
268435455
536870911
73741814
147483629
294967259
589934519
179869030
359738061
719476123
438952238
877904477
755808946
import sys
from array import array  # noqa: F401


def input():
    return sys.stdin.buffer.readline().decode('utf-8')


class UnionFind(object):
    __slots__ = ['nodes']

    def __init__(self, n: int):
        self.nodes = [-1] * n

    def find(self, x: int) -> int:
        if self.nodes[x] < 0:
            return x
        else:
            self.nodes[x] = self.find(self.nodes[x])
            return self.nodes[x]

    def unite(self, x: int, y: int) -> bool:
        root_x, root_y, nodes = self.find(x), self.find(y), self.nodes

        if root_x != root_y:
            if nodes[root_x] > nodes[root_y]:
                root_x, root_y = root_y, root_x
            nodes[root_x] += nodes[root_y]
            nodes[root_y] = root_x

        return root_x != root_y


if __name__ == '__main__':
    n, m = map(int, input().split())
    uf = UnionFind(n + 10)
    ans = [0] * m
    x = 1

    for i, (u, v) in enumerate(map(int, input().split()) for _ in range(m)):
        if not uf.unite(u, v):
            x *= 2
        ans[i] = x - 1

    sys.stdout.buffer.write('\n'.join(map(str, ans)).encode('utf-8'))
