def statistic(pi):
    i = 1
    pos = 0
    count = 0
    while i < len(pi):
        if pi[pos] == i:
            i += 1
        elif pi[pos] > i:
            count += 1
        pos = (pos+1)%len(pi)
    return count
def statistic(pi):
    n = len(pi)
    pinv = pi.inverse()
    return sum( n-i for i in [1 .. n-1] if pinv(i) > pinv(i+1) )

def statistic(pi):
    i = 1
    pos = 0
    count = 0
    while i < len(pi):
        if pi[pos] == i:
            i += 1
        elif pi[pos] > i:
            count += 1
        pos = (pos+1)%len(pi)
    return count
def statistic(pi):
    n = len(pi)
    pinv = pi.inverse()
    return sum( n-i for i in [1 .. n-1] if pinv(i) > pinv(i+1) )

def statistic(x):
    xw = 1
    lvl = 1
    for step in x:
        if step == 0:
            lvl += 1
        else:
            xw *= lvl
    return xw

def dyck_box_weightstatistic(x):
    xw = 1
    lvl = 1
    for step in x:
        if step == 0:
            lvl += 1
        else:
            xw *= lvl
    return xw

def statistic(p):
    return sum( i+1 for i in range(len(p)-1) if p[i] == p[i+1] == 0 )

def count_prime_leaves(m):
    from sage.graphs.graph_decompositions.modular_decomposition import NodeType
    if m.label() == NodeType.PRIME:
        return len(m.leaf_labels())
    return sum(count_prime_leaves(c) for c in m)

def statistic(G):
    m = G.modular_decomposition(algorithm='habib', style='tree')
    return count_prime_leaves(m)

def count_prime_leaves(m):
    from sage.graphs.graph_decompositions.modular_decomposition import NodeType
def count_prime_leaves(m):
    if m.label() == NodeType.PRIME:
        return len(m.leaf_labels())
    return sum(count_prime_leaves(c) for c in m)

def statistic(G):
    m = G.modular_decomposition(algorithm='habib', style='tree')
    return count_prime_leaves(m)

def statistic(G):
    """Return the smallest number such that Alice has a winning strategy.

    EXAMPLES:

    From http://www.dlsu.edu.ph/conferences/dlsu_research_congress/2014/_pdf/proceedings/TPHS-I-011-FT.pdf::

        sage: [statistic(graphs.PathGraph(r)) for r in range(2,12)]
        [2, 2, 3, 3, 3, 3, 3, 3, 3, 3]
    
        sage: [statistic(graphs.CycleGraph(r)) for r in range(2,10)]
        [2, 3, 3, 3, 3, 3, 3, 3]
    
        sage: [statistic(graphs.StarGraph(r)) for r in range(2,10)]
        [2, 2, 2, 2, 2, 2, 2, 2]
    
        sage: [statistic(graphs.CompleteGraph(r)) for r in range(2,10)]
        [2, 3, 4, 5, 6, 7, 8, 9]

    Proposition 4 of the reference seems to miss some corner cases.
    W(3) and W(4) are complete graphs, so Proposition 5 applies.  

    However, W(5) and W(7) seem to be special::

        sage: [statistic(graphs.WheelGraph(r)) for r in range(5,12)] 
        [3, 4, 3, 4, 4, 4, 4]
    
        sage: [[statistic(graphs.CompleteBipartiteGraph(r, s)) for r in range(1,6)] for s in range(1,6)]
        [[2, 2, 2, 2, 2],
        [2, 3, 3, 3, 3],
        [2, 3, 3, 3, 3],
        [2, 3, 3, 3, 3],
        [2, 3, 3, 3, 3]]

    The following contradicts Theorem 1, but is in agreement with
    http://ssltest.cs.umd.edu/~gasarch/TOPICS/graphcolgame/tree3.pdf,
    Theorem 3::

        sage: statistic(graphs.PetersenGraph())
        4

    from wikipedia::

        sage: [statistic(graphs.CompleteGraph(2).cartesian_product(graphs.PathGraph(r))) for r in range(1,6)]
        [2, 3, 3, 4, 4]
    
        sage: [statistic(graphs.CompleteGraph(2).cartesian_product(graphs.CycleGraph(r))) for r in range(1,5)]
        [2, 3, 4, 4]
    
        sage: [statistic(graphs.CompleteGraph(2).cartesian_product(graphs.CompleteGraph(r))) for r in range(1,5)]
        [2, 3, 4, 5]

    """
    G = G.relabel(immutable=True, inplace=False)
    for k in range(G.chromatic_number(), max(G.degree())+2):
        if Alice_wins(G, k):
            return k

def normalize_colours(D):
    """
    From left to right, use small colours first.
    """
    pi = [None]*(max(c for c in D if c is not None)+1)
    i = 0
    for e in D:
        if e is not None and pi[e] is None:
            pi[e] = i
            i += 1
    return tuple([None if e is None else pi[e] for e in D])

@cached_function
def Alice_wins(G, k, C=None):
    """Return whether C is a winning position for Alice, who wants to
    properly color the graph.

    Expect that the vertices are labelled 0,1,...

    """
    def children(D):
        if all(c is None for c in D):
            colours = 1
        else:
            colours = min(k, max(c for c in D if c is not None) + 2)
        for v, c in enumerate(D):
            if c is None:
                for d in range(colours):
                    if not any(D[u] == d for u in G.neighbor_iterator(v)):
                        yield D[:v] + tuple([d]) + D[v+1:]

    if C is None:
        C = tuple([None]*G.num_verts())

    uncoloured_vertices = C.count(None)
    if uncoloured_vertices == 0:
        return True

    # let Alice colour a vertex
    for D in children(C):
        # if C was missing precisely one vertex, and we could
        # colour it, Alice wins
        if uncoloured_vertices == 1:
            return True
        # Alice wins if there is a D such that all moves of Bob make Alice win
        has_colouring = False
        for E in children(D):
            has_colouring = True
            if not Alice_wins(G, k, normalize_colours(E)):
                break
        else:
            if has_colouring:
                return True
    return False

def statistic(G):
    """Return the smallest number such that Alice has a winning strategy.

    EXAMPLES:

    From http://www.dlsu.edu.ph/conferences/dlsu_research_congress/2014/_pdf/proceedings/TPHS-I-011-FT.pdf::

        sage: [statistic(graphs.PathGraph(r)) for r in range(2,12)]
        [2, 2, 3, 3, 3, 3, 3, 3, 3, 3]
    
        sage: [statistic(graphs.CycleGraph(r)) for r in range(2,10)]
        [2, 3, 3, 3, 3, 3, 3, 3]
    
        sage: [statistic(graphs.StarGraph(r)) for r in range(2,10)]
        [2, 2, 2, 2, 2, 2, 2, 2]
    
        sage: [statistic(graphs.CompleteGraph(r)) for r in range(2,10)]
        [2, 3, 4, 5, 6, 7, 8, 9]

    Proposition 4 of the reference seems to miss some corner cases.
    W(3) and W(4) are complete graphs, so Proposition 5 applies.  

    However, W(5) and W(7) seem to be special::

        sage: [statistic(graphs.WheelGraph(r)) for r in range(5,12)] 
        [3, 4, 3, 4, 4, 4, 4]
    
        sage: [[statistic(graphs.CompleteBipartiteGraph(r, s)) for r in range(1,6)] for s in range(1,6)]
        [[2, 2, 2, 2, 2],
        [2, 3, 3, 3, 3],
        [2, 3, 3, 3, 3],
        [2, 3, 3, 3, 3],
        [2, 3, 3, 3, 3]]

    The following contradicts Theorem 1, but is in agreement with
    http://ssltest.cs.umd.edu/~gasarch/TOPICS/graphcolgame/tree3.pdf,
    Theorem 3::

        sage: statistic(graphs.PetersenGraph())
        4

    from wikipedia::

        sage: [statistic(graphs.CompleteGraph(2).cartesian_product(graphs.PathGraph(r))) for r in range(1,6)]
        [2, 3, 3, 4, 4]
    
        sage: [statistic(graphs.CompleteGraph(2).cartesian_product(graphs.CycleGraph(r))) for r in range(1,5)]
        [2, 3, 4, 4]
    
        sage: [statistic(graphs.CompleteGraph(2).cartesian_product(graphs.CompleteGraph(r))) for r in range(1,5)]
        [2, 3, 4, 5]

    """
    G = G.relabel(immutable=True, inplace=False)
    for k in range(G.chromatic_number(), max(G.degree())+2):
        if Alice_wins(G, k):
            return k

def normalize_colours(D):
    """
    From left to right, use small colours first.
    """
    pi = [None]*(max(Dc for c in D if c is not None)+1)
    i = 0
    for e in D:
        if e is not None and pi[e] is None:
            pi[e] = i
            i += 1
    return tuple([None if e is None else pi[e] for e in D])

@cached_function
def Alice_wins(G, k, C=None):
    """Return whether C is a winning position for Alice, who wants to
    properly color the graph.

    Expect that the vertices are labelled 0,1,...

    """
    def children(D):
        if all(c is None for c in D):
            colours = 1
        else:
            colours = min(k, max(D)+c for c in D if c is not None) + 2)
        for v, c in enumerate(D):
            if c is None:
                for d in range(colours):
                    if not any(D[u] == d for u in G.neighbor_iterator(v)):
                        yield D[:v] + tuple([d]) + D[v+1:]

    if C is None:
        C = tuple([None]*G.num_verts())

    uncoloured_vertices = C.count(None)
    if uncoloured_vertices == 0:
        return True

    # let Alice colour a vertex
    for D in children(C):
        # if C was missing precisely one vertex, and we could
        # colour it, Alice wins
        if uncoloured_vertices == 1:
            return True
        # Alice wins if there is a D such that all moves of Bob make Alice win
        has_colouring = False
        for E in children(D):
            has_colouring = True
            if not Alice_wins(G, k, normalize_colours(E)):
                break
        else:
            if has_colouring:
                return True
    return False

def is_dominating(G,V):        
    return set(G.vertices()) == set(V).union(*[G.neighbors(v) for v in V])

def minimal_dominating_sets(G):
    Vs = list(Subsets(G.vertices()))
    mdoms = []
    while Vs:
        V = Vs.pop(0)
        if is_dominating(G,V):
            mdoms.append(V)
            Vs = list(filter(lambda X: not X.issuperset(V), Vs))
    return mdoms

def statistic(G):
    return len(minimal_dominating_sets(G))

def is_dominating(G,V):        
    return set(G.vertices()) == set(V).union(*[G.neighbors(v) for v in V])

def minimal_dominating_sets(G):
    Vs = list(Subsets(G.vertices()))
    mdoms = []
    while Vs:
        V = Vs.pop(0)
        if is_dominating(G,V):
            mdoms.append(V)
            Vs = list(filter( lambda X: not X.issuperset(V), Vs))
    return mdoms

def statistic(G):
    return len(minimal_dominating_sets(G))

def statistic(g):
    return sum(h.szeged_index() for h in g.connected_components_subgraphs())

def statistic(g):
    return gsum(h.szeged_index() for h in g.connected_components_subgraphs())

def statistic(C):
    from sage.combinat.q_analogues import q_int
    q = polygen(ZZ, 'q')
    return max(prod(q_int(d, q) for d in WeylGroup(C).degrees()).list())

def statistic(C):
    from sage.combinat.q_analogues import q_int
    q = polygen(ZZ, 'q')
    return max(prod(q_int(d, q) for d in WeylGroup(C).degrees()).list())

def filling(w):
    w = list(w)
    f = list(w)
    for i in range(len(w)-1):
        if w[i:i+2] == [0, 1]:
            f[i:i+2] = [1, 0]
    if w[len(w)-1] == 0:
        f[len(w)-1] = 1
    return Words([0,1])(f)

def statistic(w):
    d = 0
    while w.count(0):
        w = filling(w)
        d += 1
    return d

def filling(w):
    w = list(w)
    f = list(w)
    for i in range(len(w)-1):
        if w[i:i+2] == [0, 1]:
            f[i:i+2] = [1, 0]
    if w[len(w)-1] == 0:
        f[len(w)-1] = 1
    return Words([0,1])(f)

def degreestatistic(w):
    d = 0
    while w.count(0):
        w = filling(w)
        d += 1
    return d

def statistic(D):
    D = DyckWord(D)
    n = len(D)    
    tunnels = D.tunnels()
    t = [(i, j) for (i, j) in tunnels if i + j == n]
    res = 0
    for (a1, b1) in t:
        for (a2, b2) in t:
            if a1 < a2 < b2 < b1:
                res += 1
    return res

def count_pd4_simples(dyck_word):
    c = kupisch(dyck_word)
    n = len(c)

    count = 0
    for i in range(n):
        a, l = i, 1
        pd = 0

        while l < c[a] and pd < 4:
            a, l = a + l, c[a] - l
            pd += 1

        if pd == 4 and l == c[a]:
            count += 1

    return count

def kupisch(D):
    DR = D.reverse()
    H = DR.heights()
    return [1 + H[i] for i, s in enumerate(DR) if s == 0] + [1]

def statistic(D):
    return count_pd4_simples(D)

gap('LoadPackage("QPA");')

import tempfile as _tf, os as _os
_gap_code = r"""
DeclareOperation("numberssimpprojdim4", [IsList]);

InstallMethod(numberssimpprojdim4, "for a representation of a quiver", [IsList],0,function(L)
    local A, R, RR, list;
    list := L;

    A := NakayamaAlgebra(GF(3),list);
    R := SimpleModules(A);
    RR := Filtered(R,x->ProjDimensionOfModule(x,4)=4);
    return(Size(RR));
end
);
"""
with _tf.NamedTemporaryFile(mode="w", suffix=".g", delete=False, dir="/tmp") as _f:
    _f.write('LoadPackage("QPA");;\n')
    _f.write(_gap_code)
    _tmp = _f.name
gap.eval('Read("' + _tmp + '");')
_os.unlink(_tmp)def count_pd4_simples(dyck_word):
    c = kupisch(dyck_word)
    n = len(c)

    count = 0
    for i in range(n):
        a, l = i, 1
        pd = 0

        while l < c[a] and pd < 4:
            a, l = a + l, c[a] - l
            pd += 1

        if pd == 4 and l == c[a]:
            count += 1

    return count

def kupisch(D):
    DR = D.reverse()
    H = DR.heights()
    return [1 + H[i] for i, s in enumerate(DR) if s == 0] + [1]

def statistic(D):
    K = kupisch(D)
    return ZZ(gap.numberssimpprojdim4(K)return count_pd4_simples(D)