#include #include #include #include #include using namespace std; #define rep(i, a, b) for(int i = a; i < (b); ++i) #define all(x) begin(x), end(x) #define sz(x) (int)(x).size() typedef long long ll; typedef pair pii; typedef vector vi; template struct RMQ { vector> jmp; RMQ(const vector& V) : jmp(1, V) { for (int pw = 1, k = 1; pw * 2 <= sz(V); pw *= 2, ++k) { jmp.emplace_back(sz(V) - pw * 2 + 1); rep(j,0,sz(jmp[k])) jmp[k][j] = min(jmp[k - 1][j], jmp[k - 1][j + pw]); } } T query(int a, int b) { assert(a < b); // or return inf if a == b int dep = 31 - __builtin_clz(b - a); return min(jmp[dep][a], jmp[dep][b - (1 << dep)]); } }; struct LCA { int T = 0; vi time, path, ret; RMQ rmq; LCA(vector& C) : time(sz(C)), rmq((dfs(C,0,-1), ret)) {} void dfs(vector& C, int v, int par) { time[v] = T++; for (int y : C[v]) if (y != par) { path.push_back(v), ret.push_back(time[v]); dfs(C, y, v); } } int lca(int a, int b) { if (a == b) return a; tie(a, b) = minmax(time[a], time[b]); return path[rmq.query(a, b)]; } }; int main() { int n, m; std::cin >> n >> m; std::vector parent(n); parent[0] = -1; for(int i=0; i> a >> b; parent[b-1] = a-1; } std::vector > children(n); for(int i=1; i availableroad(n); int cur = 0; for(int i=0; i> d; int a = lca.lca(d-1, cur); if(a != cur) { int nc = children[a].size(); int j=0; for(j=availableroad[a]; j