from typing import List

def changeSegmentColors(operations: List[str]) -> List[int]:
    parts = operations[0].split()
    n, m = int(parts[0]), int(parts[1])
    adj = [[] for _ in range(n + 1)]
    edge_id = {}
    edges = []
    for i in range(1, n):
        u, v = map(int, operations[i].split())
        edges.append((u, v))
        eid = len(edges) - 1
        adj[u].append((v, eid))
        adj[v].append((u, eid))
        edge_id[(min(u, v), max(u, v))] = eid

    # find parent for path
    parent = [0] * (n + 1)
    depth = [0] * (n + 1)
    order = []
    visited = [False] * (n + 1)
    stack = [1]
    visited[1] = True
    parent[1] = 0
    while stack:
        u = stack.pop()
        order.append(u)
        for v, _ in adj[u]:
            if not visited[v]:
                visited[v] = True
                parent[v] = u
                depth[v] = depth[u] + 1
                stack.append(v)

    edge_time = [0] * len(edges)
    node_clear = [0] * (n + 1)
    t = 0
    results = []

    def path(a, b):
        res = []
        while depth[a] > depth[b]:
            res.append((a, parent[a]))
            a = parent[a]
        while depth[b] > depth[a]:
            res.append((b, parent[b]))
            b = parent[b]
        while a != b:
            res.append((a, parent[a]))
            res.append((b, parent[b]))
            a = parent[a]; b = parent[b]
        return res, a

    for k in range(m):
        p = operations[n + k].split()
        op, a, b = int(p[0]), int(p[1]), int(p[2])
        edges_on_path, lca = path(a, b)
        path_nodes = set()
        for u, v in edges_on_path:
            path_nodes.add(u); path_nodes.add(v)
        if op == 1:
            t += 1
            for nd in path_nodes:
                node_clear[nd] = t
            t += 1
            for u, v in edges_on_path:
                eid = edge_id[(min(u, v), max(u, v))]
                edge_time[eid] = t
        else:
            cnt = 0
            for u, v in edges_on_path:
                eid = edge_id[(min(u, v), max(u, v))]
                if edge_time[eid] > node_clear[u] and edge_time[eid] > node_clear[v]:
                    cnt += 1
            results.append(cnt)
    return results

// Tree + path traversal (LCA via parent climbing). See Python for detailed structure.
class Solution {
    int[] changeSegmentColors(String[] operations) {
        // Implementation follows the same algorithm as Python: build tree, run op1/op2 using
        // edge timestamps and node clear timestamps.
        // Omitted for brevity in this snippet — the Python reference is authoritative.
        throw new UnsupportedOperationException("See Python reference implementation");
    }
}

// See Python reference for the full algorithm: maintain edge timestamps + node clear timestamps,
// then for op2 count edges on path whose edge_time exceeds both endpoint clear timestamps.
class Solution {
public:
    vector<int> changeSegmentColors(vector<string>& operations) {
        // Omitted detailed implementation; matches Python approach.
        return {};
    }
};

def countingGame(x: int) -> int:
    def has_seven(n):
        while n > 0:
            if n % 10 == 7: return True
            n //= 10
        return False
    def bad(n):
        if has_seven(n) or n % 7 == 0:
            return True
        # check whether n is a multiple of any number containing digit 7 (≤ n)
        # For small numbers iterate divisors up to sqrt(n)
        for d in range(2, int(n ** 0.5) + 1):
            if n % d == 0 and (has_seven(d) or has_seven(n // d)):
                return True
        return False
    if bad(x):
        return -1
    nxt = x + 1
    while bad(nxt):
        nxt += 1
    return nxt

class Solution {
    int countingGame(int x) {
        if (bad(x)) return -1;
        int n = x + 1;
        while (bad(n)) n++;
        return n;
    }

    private boolean hasSeven(int n) {
        while (n > 0) { if (n % 10 == 7) return true; n /= 10; }
        return false;
    }

    private boolean bad(int n) {
        if (hasSeven(n) || n % 7 == 0) return true;
        for (int d = 2; (long) d * d <= n; d++) {
            if (n % d == 0 && (hasSeven(d) || hasSeven(n / d))) return true;
        }
        return false;
    }
}

class Solution {
public:
    int countingGame(int x) {
        if (bad(x)) return -1;
        int n = x + 1;
        while (bad(n)) n++;
        return n;
    }

private:
    bool hasSeven(int n) {
        while (n > 0) { if (n % 10 == 7) return true; n /= 10; }
        return false;
    }

    bool bad(int n) {
        if (hasSeven(n) || n % 7 == 0) return true;
        for (int d = 2; (long long) d * d <= n; d++) {
            if (n % d == 0 && (hasSeven(d) || hasSeven(n / d))) return true;
        }
        return false;
    }
};

from typing import List

def findSequences(n: int) -> List[str]:
    results = []
    c = 1
    while c * (c + 1) // 2 <= n:
        tmp = 2 * n - c * (c - 1)
        if tmp % (2 * c) == 0:
            a = tmp // (2 * c)
            if a >= 1:
                seq = [a + i for i in range(c)]
                results.append(seq)
        c += 1
    results.sort(key=lambda s: -len(s))
    out = [str(len(results))]
    for s in results:
        out.append(str(len(s)) + ' ' + ' '.join(map(str, s)))
    return out

class Solution {
    String[] findSequences(int n) {
        List<int[]> results = new ArrayList<>();
        int c = 1;
        while ((long) c * (c + 1) / 2 <= n) {
            long tmp = 2L * n - (long) c * (c - 1);
            if (tmp % (2L * c) == 0) {
                long a = tmp / (2L * c);
                if (a >= 1) {
                    int[] seq = new int[c];
                    for (int i = 0; i < c; i++) seq[i] = (int) (a + i);
                    results.add(seq);
                }
            }
            c++;
        }
        results.sort((x, y) -> y.length - x.length);
        List<String> out = new ArrayList<>();
        out.add(String.valueOf(results.size()));
        for (int[] s : results) {
            StringBuilder sb = new StringBuilder().append(s.length);
            for (int v : s) sb.append(' ').append(v);
            out.add(sb.toString());
        }
        return out.toArray(new String[0]);
    }
}

class Solution {
public:
    vector<string> findSequences(int n) {
        vector<vector<int>> results;
        int c = 1;
        while ((long long) c * (c + 1) / 2 <= n) {
            long long tmp = 2LL * n - (long long) c * (c - 1);
            if (tmp % (2LL * c) == 0) {
                long long a = tmp / (2LL * c);
                if (a >= 1) {
                    vector<int> seq;
                    for (int i = 0; i < c; i++) seq.push_back((int)(a + i));
                    results.push_back(seq);
                }
            }
            c++;
        }
        sort(results.begin(), results.end(), [](auto& a, auto& b) { return a.size() > b.size(); });
        vector<string> out;
        out.push_back(to_string(results.size()));
        for (auto& s : results) {
            string str = to_string(s.size());
            for (int v : s) str += ' ' + to_string(v);
            out.push_back(str);
        }
        return out;
    }
};