#include using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int L, R; cin >> L >> R; struct Edge { int to, w; }; vector> adj; int n = 0; auto addNode = [&]() { adj.emplace_back(); return n++; }; int END_NODE = addNode(); int START = addNode(); // Free chain vector F(21, -1); F[0] = END_NODE; for (int k = 1; k <= 20; k++) { F[k] = addNode(); adj[F[k]].push_back({F[k-1], 0}); adj[F[k]].push_back({F[k-1], 1}); } // Decompose [lo, hi] into aligned blocks at bit length k auto getAlignedBlocks = [](int lo, int hi, int k) -> vector> { vector> blocks; int x = lo; while (x <= hi) { int p = 0; while (p < k && (x % (1 << (p+1)) == 0) && (x + (1 << (p+1)) - 1 <= hi)) p++; blocks.push_back({x, p}); x += (1 << p); } return blocks; }; // For a range [lo, hi] at k bits, create a node that uses multi-edges // to maximize sharing with the free chain. // // Key idea: decompose into aligned blocks. For each block with prefix P // and free length f, instead of building a chain of forced-bit nodes for P, // have the parent node emit MULTIPLE edges with the same bit value to // different children, each handling a different aligned sub-block. map, int> memo; function buildRange = [&](int k, int lo, int hi) -> int { if (lo > hi || k < 0) return -1; if (k == 0) return (lo == 0 && hi == 0) ? END_NODE : -1; if (lo == 0 && hi == (1 << k) - 1) return F[k]; auto key = make_tuple(k, lo, hi); if (memo.count(key)) return memo[key]; // Standard binary split int mid = 1 << (k-1); // 0-branch: [lo, min(hi, mid-1)] at k-1 bits int left = -1; if (lo <= min(hi, mid-1)) { left = buildRange(k-1, lo, min(hi, mid-1)); } // 1-branch: [max(lo,mid)-mid, hi-mid] at k-1 bits int right = -1; if (max(lo, mid) <= hi) { right = buildRange(k-1, max(lo, mid) - mid, hi - mid); } if (left == -1 && right == -1) return memo[key] = -1; // Now try multi-edge optimization: // If left has only one edge (forced bit), and that edge goes to a node // that we could reach by splitting differently... // Actually, let's try a different approach: decompose each branch into // aligned blocks and add multiple edges // Standard approach (for now) int u = addNode(); if (left != -1) adj[u].push_back({left, 0}); if (right != -1) adj[u].push_back({right, 1}); return memo[key] = u; }; // Now the key optimization: for forced-bit chains, replace them with // multi-edge parents. // // Example: if node A has edge (1)->B, and B has edge (0)->C, // and A's parent P has edge (0)->A, // then P has path P->(0)->A->(1)->B->(0)->C // Instead, we could have P directly emit edges to skip A and B: // P->(0)->C with... but that changes the bit sequence. // // This doesn't work for linear chains. // Alternative: build the range using multi-edge per bit. // For range [lo, hi] at k bits, decompose into aligned blocks. // Group blocks by their FIRST BIT: // bit 0 blocks: those with start < mid (first bit 0) // bit 1 blocks: those with start >= mid (first bit 1) // For each group, further decompose by second bit, etc. // At each level, if a block has a free suffix, connect directly to F[free_len]. // // This is essentially the trie approach, which gives 55 nodes. // Let me try: multi-edge from each range node to DIRECTLY connect // to aligned blocks, potentially skipping multiple forced-bit levels. // We can have multiple edges with the same weight! // E.g., node U can have edge (0)->A AND edge (0)->B, as long as // A and B's languages are disjoint. // // This means: instead of U->(0)->chain->(0)->...->(0)->F[k], // we can have U->(0)->F[k] directly? NO - that changes the number of bits. // // Each edge consumes one bit. The chain of forced 0s consumes multiple bits. // We can't replace multiple edges with one. int lenL = 32 - __builtin_clz(L); int lenR = 32 - __builtin_clz(R); for (int len = lenL; len <= lenR; len++) { int rs = 1 << (len-1), re = (1 << len) - 1; int cL = max(L, rs), cR = min(R, re); if (cL > cR) continue; int suffLen = len - 1; int loSuf = cL - rs, hiSuf = cR - rs; int target; if (suffLen == 0) target = END_NODE; else target = buildRange(suffLen, loSuf, hiSuf); if (target >= 0) adj[START].push_back({target, 1}); } // Remove unreachable vector reach(n, false); queue q; q.push(START); reach[START] = true; while (!q.empty()) { int u = q.front(); q.pop(); for (auto& e : adj[u]) { if (!reach[e.to]) { reach[e.to] = true; q.push(e.to); } } } map newId; int cnt = 0; newId[START] = ++cnt; for (int i = 0; i < n; i++) if (i != START && reach[i]) newId[i] = ++cnt; cout << cnt << "\n"; vector inv(cnt + 1); for (auto& [old, nw] : newId) inv[nw] = old; for (int i = 1; i <= cnt; i++) { int u = inv[i]; cout << adj[u].size(); for (auto& e : adj[u]) cout << " " << newId[e.to] << " " << e.w; cout << "\n"; } return 0; }