#include #include #include using namespace atcoder; using mint = modint1000000007; using namespace std; #define rep(i,n) for (int i = 0; i < (n); ++i) #define Inf 1000000001 int main(){ int N; cin>>N; priority_queue> Q; Q.emplace(1,0); Q.emplace(1,1); vector a(1,0),b(1,1); vector d(N,0); d[0] = 1; d[1] = 1; for(int i=2;i inds; while(true){ pair p = Q.top(); Q.pop(); if(Q.size()==0 || d[i]+1>Q.top().first+1){ Q.push(p); break; } inds.push_back(p.second); d[i]++; } rep(j,inds.size()){ a.push_back(i); b.push_back(inds[j]); d[inds[j]]++; Q.emplace(d[inds[j]],inds[j]); } Q.emplace(d[i],i); } cout<