using namespace std;
using vi = vector<int>;
using ll = long long;
int main(void)
{
    int n, m, u, v;
    vector<vi> edge_exists;
    vi node_seq;
    cin >> n >> m;
    edge_exists.resize(n + 1, vi(n + 1, false));
    for (int i = 1; i <= n; ++i)
        node_seq.push_back(i);
    for (int i = 0; i < m; ++i)
    {
        cin >> u >> v;
        edge_exists[u][v] = edge_exists[v][u] = true;
    }
    ll ans = 0;
    do
    {
        bool is_hamiltonian = true;
        for (int i = 1; is_hamiltonian and i < n; ++i)
        {
            u = node_seq[i - 1], v = node_seq[i];
            if (not edge_exists[u][v])
                is_hamiltonian = false;
        }
        ans += is_hamiltonian;
    } while (next_permutation(next(node_seq.begin()), node_seq.end()));
    cout << ans << endl;
    return 0;
}

using namespace std;
using ll = long long;
int main(void)
{
    ll a, b, x, ap, bp;
    cin >> a >> b >> x;
    ap = (a + x - 1) / x;
    bp = b / x;
    cout << bp - ap + 1 << endl;
    return 0;
}

using namespace std;
const int NMAX = 1e6 + 11;
string s;
int n, pi[NMAX];
void prefix_function(void)
{
    memset(pi, 0, sizeof(pi));
    for (int i = 1; i < n; ++i)
    {
        int j = pi[i - 1];
        while (j > 0 and s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            ++j;
        pi[i] = j;
    }
}
int main(void)
{
    int t, ans, j;
    cin >> t;
    for (int tc = 1; tc <= t; ++tc)
    {
        cin >> s;
        n = s.size();
        prefix_function();
        ans = 0;
        j = pi[n - 1];
        while (j != 0)
        {
            j = pi[j - 1];
            ans += 1;
        }
        cout << "Case " << tc << ": " << ans << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
const int ALPH = 2;
const int TRIEMAX = 20;
struct node
{
    ll cnt;
    node *children[ALPH];
    node(void)
    {
        children[0] = children[1] = nullptr;
        cnt = 0;
    }
    ~node()
    {
        for (int i = 0; i < ALPH; ++i)
        {
            delete children[i];
            children[i] = nullptr;
            cnt = 0;
        }
    }
};
struct trie
{
    node *root;
    trie() { root = new node(); }
    ~trie()
    {
        delete root;
        root = nullptr;
    }
    inline ll get_cnt(node *cur) { return cur == nullptr ? 0 : cur->cnt; }
    void insert(int x)
    {
        node *cur = root;
        for (int i = TRIEMAX; i >= 0; --i)
        {
            int j = (x >> i) & 1;
            if (cur->children[j] == nullptr)
                cur->children[j] = new node();
            cur = cur->children[j];
            cur->cnt += 1;
        }
    }
    ll query(int x, int k)
    {
        int xi, ki, j;
        ll ans = 0;
        node *cur = root;
        for (int i = TRIEMAX; i >= 0; --i)
        {
            if (cur == nullptr)
                break;
            xi = (x >> i) & 1;
            ki = (k >> i) & 1;
            if (xi == 0 and ki == 1)
            {
                ans += get_cnt(cur->children[0]);
                j = 1;
            }
            else if (xi == 1 and ki == 0)
            {
                j = 1;
            }
            else if (xi == 0 and ki == 0)
            {
                j = 0;
            }
            else
            {
                ans += get_cnt(cur->children[1]);
                j = 0;
            }
            cur = cur->children[j];
        }
        return ans;
    }
};
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int tc, n, k, x, acc;
    ll ans;
    cin >> tc;
    while (tc--)
    {
        cin >> n >> k;
        trie t;
        acc = ans = 0;
        t.insert(acc);
        while (n--)
        {
            cin >> x;
            acc ^= x;
            ans += t.query(acc, k);
            t.insert(acc);
        }
        cout << ans << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
const int NMAX = 1e5 + 11;
vi g[NMAX];
int dp[NMAX];
void compdp(int u, int p)
{
    dp[u] = 0;
    for (auto v : g[u])
    {
        if (v == p)
            continue;
        compdp(v, u);
        if (dp[v] == 0)
            dp[u] = 1;
    }
}
int main(void)
{
    int n, u, v;
    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }
    compdp(1, 0);
    cout << accumulate(dp + 1, dp + n + 1, 0) << endl;
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using vii = vector<ii>;
using vi = vector<int>;
using si = set<int>;
using mii = map<int, int>;
const int NMAX = 4e4 + 11;
int seg[4 * NMAX], lazy[4 * NMAX];
void lazy_propagate(int v, int tl, int tr, int new_val)
{
    seg[v] = new_val;
    if (tl != tr)
    {
        lazy[2 * v] = new_val;
        lazy[2 * v + 1] = new_val;
    }
    lazy[v] = 0;
}
void update(int v, int tl, int tr, int ql, int qr, int new_val)
{
    if (lazy[v] != 0)
        lazy_propagate(v, tl, tr, lazy[v]);
    if (ql > qr)
        return;
    else if (ql == tl and qr == tr)
        lazy_propagate(v, tl, tr, new_val);
    else
    {
        int tm = (tl + tr) / 2;
        update(v * 2, tl, tm, ql, min(qr, tm), new_val);
        update(v * 2 + 1, tm + 1, tr, max(ql, tm + 1), qr, new_val);
    }
}
int query(int v, int tl, int tr, int ql, int qr)
{
    if (lazy[v] != 0)
        lazy_propagate(v, tl, tr, lazy[v]);
    if (ql > qr)
        return 0;
    if (ql == tl and qr == tr)
        return seg[v];
    else
    {
        int tm = (tl + tr) / 2;
        return query(2 * v, tl, tm, ql, min(qr, tm)) +
               query(2 * v + 1, tm + 1, tr, max(ql, tm + 1), qr);
    }
}
pair<int, vii> compress(vii qranges)
{
    vi values;
    mii compressed;
    for (auto [l, r] : qranges)
        values.push_back(l), values.push_back(r);
    sort(values.begin(), values.end());
    values.erase(unique(values.begin(), values.end()), values.end());
    for (int i = 0, maxv = values.size(); i < maxv; i++)
        compressed[values[i]] = i + 1;
    for (auto &[l, r] : qranges)
        l = compressed[l], r = compressed[r];
    return {(int)values.size(), qranges};
}
int main(void)
{
    int t, n;
    cin >> t;
    while (t--)
    {
        memset(seg, 0, sizeof(seg));
        memset(lazy, 0, sizeof(lazy));
        cin >> n;
        vii qranges(n);
        for (auto &[l, r] : qranges)
            cin >> l >> r;
        auto [max_val, cranges] = compress(qranges);
        for (int i = 0; i < n; ++i)
        {
            auto [l, r] = cranges[i];
            update(1, 1, max_val, l, r, i + 1);
        }
        si ans;
        for (int i = 1; i <= max_val; ++i)
            ans.insert(query(1, 1, max_val, i, i));
        ans.erase(0);
        cout << ans.size() << endl;
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
const int CRMAX = 1e3 + 11;
const vi dr({0, 0, 1, -1});
const vi dc({1, -1, 0, 0});
int cols, rows, diameter, row_, col_;
char lab[CRMAX][CRMAX];
bool vis[CRMAX][CRMAX];
void clear_vis(void)
{
    for (int row = 0; row < rows; ++row)
        memset(vis[row], false, sizeof(vis[row][0]) * cols);
}
inline bool in_range(int row, int col)
{
    return row >= 0 and row < rows and col >= 0 and col < cols;
}
inline bool is_free_block(int row, int col) { return lab[row][col] == '.'; }
void dfs(int row, int col, int depth)
{
    if (depth > diameter)
    {
        diameter = depth;
        row_ = row;
        col_ = col;
    }
    vis[row][col] = true;
    for (int i = 0; i < 4; ++i)
    {
        if (in_range(row + dr[i], col + dc[i]) and
            not vis[row + dr[i]][col + dc[i]] and
            is_free_block(row + dr[i], col + dc[i]))
            dfs(row + dr[i], col + dc[i], depth + 1);
    }
}
int solve(void)
{
    diameter = INT_MIN;
    for (int row = 0; row < rows; ++row)
    {
        for (int col = 0; col < cols; ++col)
        {
            if (lab[row][col] == '.')
            {
                clear_vis();
                dfs(row, col, 0);
                clear_vis();
                dfs(row_, col_, 0);
                return diameter;
            }
        }
    }
    return 0;
}
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        cin >> cols >> rows;
        for (int row = 0; row < rows; ++row)
            cin >> lab[row];
        cout << "Maximum rope length is " << solve() << '.' << endl;
    }
    return 0;
}

using namespace std;
using ii = pair<int, int>;
using vi = vector<int>;
using vii = vector<ii>;
inline int sum_pair(ii a) { return a.first + a.second; }
struct segtree
{
    int n;
    vii t;
    segtree(int n)
    {
        this->n = n;
        t.resize(4 * n);
    }
    segtree(const vi &a) : segtree(a.size()) { build(a, 1, 0, n - 1); }
    ii merge(ii a, ii b) const
    {
        if (a.first < b.first)
            swap(a, b);
        return {a.first, max({a.second, b.second, b.first})};
    }
    void build(const vi &a, int v, int tl, int tr)
    {
        if (tl == tr)
            t[v] = {a[tl], -1};
        else
        {
            int tm = (tl + tr) / 2;
            build(a, 2 * v, tl, tm);
            build(a, 2 * v + 1, tm + 1, tr);
            t[v] = merge(t[2 * v], t[2 * v + 1]);
        }
    }
    void update(int pos, int new_val)
    {
        update_util(1, 0, n - 1, pos, new_val);
    }
    void update_util(int v, int tl, int tr, int pos, int new_val)
    {
        if (pos < tl or tr < pos)
            return;
        else if (tl == tr and tl == pos)
            t[v] = {new_val, -1};
        else
        {
            int tm = (tl + tr) / 2;
            update_util(2 * v, tl, tm, pos, new_val);
            update_util(2 * v + 1, tm + 1, tr, pos, new_val);
            t[v] = merge(t[v * 2], t[v * 2 + 1]);
        }
    }
    int query(int ql, int qr) const
    {
        return sum_pair(query_util(1, 0, n - 1, ql, qr));
    }
    ii query_util(int v, int tl, int tr, int ql, int qr) const
    {
        if (qr < ql)
            return {-1, -1};
        else if (ql == tl and qr == tr)
            return t[v];
        int tm = (tl + tr) / 2;
        return merge(query_util(2 * v, tl, tm, ql, min(tm, qr)),
                     query_util(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr));
    }
};
int main(void)
{
    int n, qn, ql, qr, pos, x;
    char qtype;
    vi a;
    cin >> n;
    a.resize(n);
    for (auto &x : a)
        cin >> x;
    segtree t(a);
    cin >> qn;
    while (qn--)
    {
        cin >> qtype;
        if (qtype == 'Q')
        {
            cin >> ql >> qr;
            cout << t.query(ql - 1, qr - 1) << endl;
        }
        else
        {
            cin >> pos >> x;
            t.update(pos - 1, x);
        }
    }
    return 0;
}

using namespace std;
using vi = vector<int>;
using ll = long long;
const int amax = 1e7 + 11;
struct fenwick
{
    int n;
    vi bit;
    fenwick(int _n) : n(_n + 1) { bit.assign(_n + 1, 0); }
    void point_update(int i, int delta)
    {
        ++i;
        while (i < n)
        {
            bit[i] += delta;
            i += (i & -i);
        }
    }
    ll prefix_sum(int r)
    {
        ll ans = 0;
        ++r;
        while (r > 0)
        {
            ans += bit[r];
            r -= (r & -r);
        }
        return ans;
    }
    ll sum(int l, int r)
    {
        ll ans = prefix_sum(r);
        ans -= prefix_sum(l - 1);
        return ans;
    }
};
int main(void)
{
    int t, n, x;
    ll ans;
    cin >> t;
    while (t--)
    {
        cin >> n;
        fenwick tree(amax + 1);
        ans = 0;
        for (int i = 0; i < n; ++i)
        {
            cin >> x;
            tree.point_update(x, 1);
            ans += tree.sum(x + 1, amax);
        }
        cout << ans << endl;
    }
    return 0;
}

using namespace std;
using ll = long long;
const int NMAX = 1e5 + 11;
ll n, a[NMAX], seg[4 * NMAX];
void update(ll v, ll tl, ll tr, ll ql, ll qr);
void build(ll a[], ll v, ll tl, ll tr)
{
    if (tl == tr)
        seg[v] = a[tl];
    else
    {
        ll tm = (tl + tr) / 2;
        build(a, 2 * v, tl, tm);
        build(a, 2 * v + 1, tm + 1, tr);
        seg[v] = seg[2 * v] + seg[2 * v + 1];
    }
}
void lazy_propagate(ll v, ll tl, ll tr)
{
    if (tr - tl + 1 < seg[v])
    {
        if (tl == tr)
        {
            seg[v] = (ll)sqrt(seg[v]);
        }
        else
        {
            ll tm = (tl + tr) / 2;
            update(2 * v, tl, tm, tl, tm);
            update(2 * v + 1, tm + 1, tr, tm + 1, tr);
            seg[v] = seg[2 * v] + seg[2 * v + 1];
        }
    }
}
void update(ll v, ll tl, ll tr, ll ql, ll qr)
{
    if (ql > qr)
        return;
    if (tl == ql and tr == qr)
        lazy_propagate(v, tl, tr);
    else
    {
        ll tm = (tl + tr) / 2;
        update(2 * v, tl, tm, ql, min(tm, qr));
        update(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr);
        seg[v] = seg[2 * v] + seg[2 * v + 1];
    }
}
ll query(ll v, ll tl, ll tr, ll ql, ll qr)
{
    if (ql > qr)
        return 0;
    else if (tl == ql and tr == qr)
        return seg[v];
    else
    {
        ll tm = (tl + tr) / 2;
        return query(2 * v, tl, tm, ql, min(tm, qr)) +
               query(2 * v + 1, tm + 1, tr, max(tm + 1, ql), qr);
    }
}
int main(void)
{
    ll q, ql, qr, type, tc = 1;
    while (scanf("%lld", &n) != EOF)
    {
        memset(seg, 0, sizeof(seg));
        for (ll i = 0; i < n; ++i)
            scanf("%lld", &a[i]);
        build(a, 1, 0, n - 1);
        scanf("%lld", &q);
        printf("Case #%lld:\n", tc++);
        while (q--)
        {
            scanf("%lld%lld%lld", &type, &ql, &qr);
            if (ql > qr)
                swap(ql, qr);
            if (type == 0)
            {
                update(1, 0, n - 1, ql - 1, qr - 1);
            }
            else
            {
                printf("%lld\n", query(1, 0, n - 1, ql - 1, qr - 1));
            }
        }
        printf("\n");
    }
    return 0;
}