"""
cg.py -- counting connected induced vertex sets of a finite simple graph.

c(G) = number of nonempty sets F of vertices such that the induced subgraph
G[F] is connected.

Graphs are given as adjacency bitmasks: adj[v] is an int whose bit u is set
iff u ~ v.  Vertices are 0..n-1.

Two independent counting methods are provided:

  c_brute(adj)  -- method 1: test every nonempty subset for connectivity.
  c_esu(adj)    -- method 2: output-sensitive enumeration of connected sets
                   (Wernicke's ESU extension scheme; each connected set is
                   generated exactly once, from its minimum vertex).

For trees there is a third method:

  c_tree_dp(adj) -- subtrees counted by the rooted product formula
                    f(v) = prod_{children w} (1 + f(w)),  c(T) = sum_v f(v).

The functions share no code beyond the adjacency representation.
"""

from itertools import combinations


# ---------------------------------------------------------------- utilities

def adj_from_edges(n, edges):
    adj = [0] * n
    for u, v in edges:
        if u == v:
            raise ValueError("loop")
        adj[u] |= 1 << v
        adj[v] |= 1 << u
    return adj


def edges_from_adj(adj):
    n = len(adj)
    return [(u, v) for u in range(n) for v in range(u + 1, n) if adj[u] >> v & 1]


def is_connected_mask(adj, S):
    """Is the induced subgraph on the vertex set S (bitmask, nonempty) connected?"""
    start = S & -S
    seen = start
    frontier = start
    while frontier:
        v = (frontier & -frontier).bit_length() - 1
        frontier &= frontier - 1
        new = adj[v] & S & ~seen
        seen |= new
        frontier |= new
    return seen == S


def is_connected(adj):
    n = len(adj)
    return n > 0 and is_connected_mask(adj, (1 << n) - 1)


# ------------------------------------------------------- method 1: brute force

def c_brute(adj):
    n = len(adj)
    return sum(1 for S in range(1, 1 << n) if is_connected_mask(adj, S))


# ------------------------------------------------------- method 2: ESU scheme

def c_esu(adj, limit=None):
    """Count connected vertex sets by explicit enumeration.

    For each vertex v, enumerate the connected sets whose minimum vertex is v:
    a set S is extended only by vertices of the current extension set, and a
    newly added vertex w contributes to the extension set only its exclusive
    neighbours (neighbours of w that are larger than v, not in S, and not
    adjacent to S).  This is the ESU scheme of Wernicke (2006), which
    generates every connected set exactly once.

    If `limit` is given, stop and return limit+1 as soon as the count exceeds it.
    """
    n = len(adj)
    total = 0
    for v in range(n):
        higher = ~((1 << (v + 1)) - 1)          # vertices > v
        # stack items: (S, N(S) as mask, extension mask)
        stack = [(1 << v, adj[v], adj[v] & higher)]
        while stack:
            S, NS, ext = stack.pop()
            total += 1
            if limit is not None and total > limit:
                return limit + 1
            while ext:
                w = (ext & -ext).bit_length() - 1
                ext &= ext - 1
                excl = adj[w] & higher & ~S & ~NS     # exclusive neighbours of w
                stack.append((S | (1 << w), NS | adj[w], ext | excl))
    return total


# ------------------------------------------------------- method 3: trees only

def c_tree_dp(adj, root=0):
    n = len(adj)
    if n == 1:
        return 1
    parent = [-1] * n
    order = [root]
    parent[root] = root
    for v in order:
        m = adj[v]
        while m:
            w = (m & -m).bit_length() - 1
            m &= m - 1
            if parent[w] == -1:
                parent[w] = v
                order.append(w)
    if len(order) != n:
        raise ValueError("not connected")
    f = [1] * n
    for v in reversed(order):
        if v != root:
            f[parent[v]] *= 1 + f[v]
    return sum(f)


def is_tree(adj):
    n = len(adj)
    m = sum(bin(a).count("1") for a in adj) // 2
    return is_connected(adj) and m == n - 1


# ------------------------------------------------------------- graph6 format

def to_graph6(adj):
    n = len(adj)
    if n > 62:
        raise ValueError("n > 62 not supported")
    bits = []
    for v in range(1, n):
        for u in range(v):
            bits.append(adj[u] >> v & 1)
    while len(bits) % 6:
        bits.append(0)
    out = [chr(n + 63)]
    for i in range(0, len(bits), 6):
        val = 0
        for b in bits[i:i + 6]:
            val = (val << 1) | b
        out.append(chr(val + 63))
    return "".join(out)


def from_graph6(s):
    s = s.strip()
    n = ord(s[0]) - 63
    if n > 62:
        raise ValueError("n > 62 not supported")
    bits = []
    for ch in s[1:]:
        val = ord(ch) - 63
        for k in range(5, -1, -1):
            bits.append(val >> k & 1)
    adj = [0] * n
    i = 0
    for v in range(1, n):
        for u in range(v):
            if bits[i]:
                adj[u] |= 1 << v
                adj[v] |= 1 << u
            i += 1
    return adj


# ------------------------------------------------------ canonical graph6

def canonical_graph6(adj):
    """The lexicographically least graph6 string among all labelings of the
    graph with vertex set {0,...,n-1}.

    graph6 lists the adjacency bits column by column: (0,1), (0,2), (1,2),
    (0,3), (1,3), (2,3), ...  For a fixed n all strings have the same length
    and lexicographic order on strings is lexicographic order on this bit
    sequence.  We assign new labels 0, 1, 2, ... in turn; when the labels
    0..v-1 are fixed, the choice of the vertex receiving label v determines
    column v.  At each node only the vertices giving the least column can
    lead to the least string, so we branch on those only and prune against
    the best complete sequence found so far.  The result is exact (it is
    compared with brute force over all n! labelings in the self-test).
    """
    n = len(adj)
    best = [None]

    def rec(perm, used, seq):
        v = len(perm)
        if v == n:
            if best[0] is None or seq < best[0]:
                best[0] = seq
            return
        cand = []
        for x in range(n):
            if not used >> x & 1:
                cand.append((tuple(adj[p] >> x & 1 for p in perm), x))
        mincol = min(c for c, _ in cand)
        newseq = seq + mincol
        if best[0] is not None and newseq > best[0][:len(newseq)]:
            return
        for col, x in cand:
            if col == mincol:
                rec(perm + [x], used | (1 << x), newseq)

    rec([], 0, ())
    bits = list(best[0])
    # build the canonical labeled graph from the least bit sequence and encode it
    m = [0] * n
    i = 0
    for v in range(1, n):
        for u in range(v):
            if bits[i]:
                m[u] |= 1 << v
                m[v] |= 1 << u
            i += 1
    return to_graph6(m)


def _canonical_brute(adj):
    from itertools import permutations
    n = len(adj)
    best = None
    for p in permutations(range(n)):       # p[new] = old
        m = [0] * n
        for a in range(n):
            for b in range(a + 1, n):
                if adj[p[a]] >> p[b] & 1:
                    m[a] |= 1 << b
                    m[b] |= 1 << a
        s = to_graph6(m)
        if best is None or s < best:
            best = s
    return best


# ------------------------------------------------------------ self-test

def _selftest():
    # paths: T(n); cycles: n(n-1)+1; complete: 2^n-1; stars: 2^(n-1)+n-1
    for n in range(1, 11):
        P = adj_from_edges(n, [(i, i + 1) for i in range(n - 1)])
        K = adj_from_edges(n, list(combinations(range(n), 2)))
        S = adj_from_edges(n, [(0, i) for i in range(1, n)])
        for adj, want in ((P, n * (n + 1) // 2), (K, 2 ** n - 1),
                          (S, 2 ** (n - 1) + n - 1 if n > 1 else 1)):
            assert c_brute(adj) == want == c_esu(adj), (n, want)
        if n >= 3:
            C = adj_from_edges(n, [(i, (i + 1) % n) for i in range(n)])
            assert c_brute(C) == n * (n - 1) + 1 == c_esu(C)
        assert c_tree_dp(P) == n * (n + 1) // 2
        assert from_graph6(to_graph6(K)) == K
    # canonical graph6 against brute force over all labelings
    import random
    rng = random.Random(1)
    for t in range(400):
        n = rng.randint(1, 7 if t < 350 else 8)
        p = rng.random()
        adj = adj_from_edges(n, [(a, b) for a in range(n) for b in range(a + 1, n) if rng.random() < p])
        assert canonical_graph6(adj) == _canonical_brute(adj), to_graph6(adj)
    print("cg.py self-test passed")


if __name__ == "__main__":
    _selftest()