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 pii = pair<int, int>;
using vi = vector<int>;
using spii = set<pii>;
const int NMAX = 1e5 + 11;
pii EMPTY = make_pair(INT_MAX, -2);
int n, cur_time = 0;
int sz[NMAX], depth[NMAX], visit_time[NMAX];
bool black[NMAX];
vi tree[NMAX];
spii seg[4 * NMAX];
void add_edge(int u, int v)
{
    tree[u].push_back(v);
    tree[v].push_back(u);
}
void visit(int u, int d)
{
    depth[u] = d;
    visit_time[u] = cur_time;
}
void traverse(int u, int d)
{
    int local_time = cur_time;
    visit(u, d);
    for (int v : tree[u])
    {
        if (visit_time[v] == -1)
            traverse(v, d + 1);
    }
    sz[u] = cur_time - local_time;
}
void build(int v, int tl, int tr)
{
    if (tl == tr)
        seg[v] = {EMPTY};
    else
    {
        int tm = (tl + tr) / 2;
        build(v * 2, tl, tm);
        build(v * 2 + 1, tm + 1, tr);
        seg[v] = {EMPTY};
    }
}
pii query(int v, int tl, int tr, int x)
{
    int pos = visit_time[x];
    if (tl == tr and pos == tl)
        return *seg[v].begin();
    else if (tl <= pos and pos <= tr)
    {
        int tm = (tl + tr) / 2;
        spii acc_ans;
        acc_ans.insert(*seg[v].begin());
        acc_ans.insert(query(v * 2, tl, tm, x));
        acc_ans.insert(query(v * 2 + 1, tm + 1, tr, x));
        return *acc_ans.begin();
    }
    else
        return EMPTY;
}
void update(int v, int tl, int tr, int ql, int qr, int x)
{
    if (ql > qr)
        return;
    if (tl == ql and tr == qr)
    {
        if (not black[x])
            seg[v].insert({depth[x], x});
        else
            seg[v].erase({depth[x], x});
    }
    else
    {
        int tm = (tl + tr) / 2;
        update(v * 2, tl, tm, ql, min(qr, tm), x);
        update(v * 2 + 1, tm + 1, tr, max(ql, tm + 1), qr, x);
    }
}
int main(void)
{
    int q, u, v, type;
    cin >> n >> q;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> u >> v;
        add_edge(u - 1, v - 1);
    }
    memset(visit_time, -1, NMAX);
    traverse(0, 0);
    build(1, 0, n - 1);
    while (q--)
    {
        cin >> type >> v;
        v -= 1;
        if (type == 1)
            cout << query(1, 0, n - 1, v).second + 1 << endl;
        else
        {
            update(1, 0, n - 1, visit_time[v], visit_time[v] + sz[v] - 1, v);
            black[v] = !black[v];
        }
    }
    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 ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
const int ALPH = 26;
const int TRIEMAX = 20;
struct Node
{
    bool finish, visited;
    array<Node *, ALPH> children;
    Node(void)
    {
        visited = finish = false;
        fill(children.begin(), children.end(), nullptr);
    }
    ~Node()
    {
        finish = visited = false;
        for (auto child : children)
            delete child;
    }
};
struct Trie
{
    Node *root;
    Trie() { root = new Node(); }
    ~Trie()
    {
        delete root;
        root = nullptr;
    }
    bool insert(string s)
    {
        auto cur = root;
        for (int i = 0, n = (int)s.size(); i < n; ++i)
        {
            int j = s[i] - '0';
            if (not cur->children[j])
                cur->children[j] = new Node();
            if (cur->finish)
                return false;
            cur->visited = true;
            cur = cur->children[j];
        }
        if (cur->visited)
            return false;
        return cur->visited = cur->finish = true;
    }
};
int main(void)
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        Trie tree;
        int n;
        bool flag = true;
        cin >> n;
        while (n--)
        {
            string num;
            cin >> num;
            if (flag and not tree.insert(num))
                flag = false;
        }
        cout << (flag ? "YES" : "NO") << endl;
    }
}

using namespace std;
using ll = long long;
using ii = pair<int, int>;
using vi = vector<int>;
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void read_n(InputIterator it, int n)
{
    copy_n(istream_iterator<T>(cin), n, it);
}
template <typename InputIterator,
          typename T = typename iterator_traits<InputIterator>::value_type>
void write(InputIterator first, InputIterator last, const char *delim = "\n")
{
    copy(first, last, ostream_iterator<T>(cout, delim));
}
vi prefix_function(string s)
{
    int n = (int)s.size();
    vi pi(n, 0);
    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;
    }
    return pi;
}
int main(void)
{
    ios::sync_with_stdio(false), cin.tie(NULL);
    int t;
    cin >> t;
    while (t--)
    {
        string str, pat;
        cin >> str >> pat;
        int pat_sz = (int)pat.size();
        auto pi = prefix_function(pat + "#" + str);
        vi ans;
        for (int i = pat_sz + 1, len = (int)pi.size(); i < len; ++i)
            if (pi[i] == pat_sz)
                ans.push_back(i + 1 - 2 * pat_sz);
        if ((int)ans.size() == 0)
            cout << "Not Found" << endl;
        else
            cout << (int)ans.size() << endl, write(ans.begin(), ans.end(), " "), cout << 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;
}