User ainta has a stack of *n* red and blue balls. He can apply a certain operation which changes the colors of the balls inside the stack.
 -  While the top ball inside the stack is red, pop the ball from the top of the stack. -  Then replace the blue ball on the top with a red ball. -  And finally push some blue balls to the stack until the stack has total of *n* balls inside. 
If there are no blue balls inside the stack, ainta can't apply this operation. Given the initial state of the stack, ainta wants to know the maximum number of operations he can repeatedly apply.
The first line contains an integer *n* (1 ≤ *n* ≤ 50) — the number of balls inside the stack.

The second line contains a string *s* (|*s*| = *n*) describing the initial state of the stack. The *i*-th character of the string *s* denotes the color of the *i*-th ball (we'll number the balls from top to bottom of the stack). If the character is "R", the color is red. If the character is "B", the color is blue.

# SPOJ Problem Set (classical)
# 300. Cable TV Network
# Problem code: CABLETV

def is_connected(g):
    """
    detect whether an undirected graph is connected. dfs is used to traverse a sub-graph of g: if the sub-graph has the same number of vertex as g, g is connected.

    argument:
    g: 2d array for adjacency list representation.
    return:
    true if g is connected; otherwise, false.
    """
    color = []
    for v in g:
        color.append('white')
    c = 0;
    for i, v in enumerate(g):
        if color[i] == 'white':
            c += is_connected_visit(color, i, g)
            break
    return c == len(g)

def is_connected_visit(color, u, g):
    """
    sub-function used by is_connected(g).

    argument:
    color: the array that maps vertex and its state (white: unvisited; gray: depth-first visiting; black: visited.)
    u: the vertex is going to be visited.
    g: the graph.

    return:
    true if the graph g is connected; otherwise, false.
    """
    color[u] = 'gray'
    c = 1
    for v in g[u]:
        if color[v] == 'white':
            c += is_connected_visit(color, v, g)
    color[u] = 'black'
    return c

def matrix_g(g):
    """
    complete the edge information for graph g. Input graph information is not always complete. For example, (u, v) is input while (v, u) not. this function will supplement vertex adjacency information. 

    argument:
    g: the 2d array representing a graph.

    return:
    the 2d array containing complete vertex adjacency information.
    """
    for i, v in enumerate(g):
        for w in v:
            if i not in g[w]:
                g[w].append(i)
    return g

def next(bs):
    """
    sub-function used by select(g). use binary-string method to generate the next element when calculating power set. the function is destructive.

    argument:
    bs: a binary string representing the current subset. this argument may be modified.

    return:
    true if the next subset is constructed; false if no such item left.
    """
    c = len(bs)
    for b in bs[::-1]:
        c -= 1
        if b == 0:
            break
    if c > 0 or (c == 0 and bs[0] == 0):
        bs[c] = 1
        for i in range(c + 1, len(bs)):
            bs[i] = 0
        return True
    else:
        return False

def select(g):
    """
    generate the power set over the vertex set of g.

    argument:
    g: the 2d array representing a graph.

    return:
    the power set over the vertex set of g.
    """
    r =[]
    bs = [0] * len(g)
    while next(bs):
        z = []
        for i, b in enumerate(bs):
            if b == 1:
                z.append(i)
        r.append(z)
    return r

def remove(s, g):
    """
    generate a new graph that removes vertex set s from g.

    argument:
    s: the vertex set element of which will be removed from g.
    g: the 2d array representing a graph.
    return:
    a 2d array representing graph that does not contain vertexes in s.
    """
    a = len(g)
    b = len(s)
    r = [[] for i in range(a - b)]
    m = {}
    c = 0
    for i in range(a):
        if i not in s:
            m[i] = c
            c += 1
    for v, vn in enumerate(g):
        if v not in s:
            for w in vn:
                if w not in s and m[w] not in r[m[v]]:
                    r[m[v]].append(m[w])
    return r

def fac(g):
    """
    calculate the network's safty factor.

    argument:
    g: a 2d array representing a graph.

    return:
    the network g's sfaty factor.
    """
    if not is_connected(g) or len(g) == 0:
        return 0
    else:
        q = select(g)
        for s in q:
            g2 = remove(s, g)
            if not is_connected(g2) or len(g2) == 0:
                return len(s)

def calc():
    """
    entry function of the solution.
    """
    n = int(raw_input('input network numbers: '))
    r = []
    for i in range(n):
        test = raw_input('input a network: ').split()
        gvn = int(test[0])
        gen = int(test[1])
        g = [[] for v in range(gvn)]
        for e in range(2, 2 + gen):
            edge = test[e].split(',')
            edge[0] = int(edge[0].replace('(', ''))
            edge[1] = int(edge[1].replace(')', ''))
            g[edge[0]].append(edge[1])
            g[edge[1]].append(edge[0])
        matrix_g(g)
        r.append(fac(g))
    for f in r:
        print f

# g = [[1, 2], [0, 2, 4], [], [], [], [4], [1, 3, 5]]
# matrix_g(g)
# print g
# print is_connected(g)

# bs = [0, 0, 1, 0, 1, 1, 1]
# next(bs)
# print bs

# print '-' * 16
# g2 = [0, 1, 2, 3]
# print select(g2)

# print g
# g3 = remove([2], g)
# print g3

# print fac(g)

# e1 = [[1, 2], [0, 2], [0, 1]]
# e2 = [[], []]
# e3 = [[1, 2], [0, 2, 3, 4], [0, 1, 3], [1, 2, 4], [1, 3]]
# print fac(e1)
# print fac(e2)
# print fac(e3)

calc()
