#include using namespace std; // 列が小さすぎて WA の確率が足りない int main(int argc, char* argv[]) { // 3の列 × 1500 // 5の列 × 1500 int N = 6000; int L = 1500; // 列の個数 vector> G(N + 1); for (int i = 1; i < L; i++) { G[i].push_back(i + 1); G[i + 1].push_back(i); } int id = L + 1; for (int u = 1; u <= L; u++) { int now = u; // 縦に 3 つ if (u <= 750) { G[now].push_back(id); G[id].push_back(now); id++; G[now].push_back(id); G[id].push_back(now); id++; } else { // 縦に 5 つ G[now].push_back(id); G[id].push_back(now); now = id; id++; G[now].push_back(id); G[id].push_back(now); id++; now = u; G[now].push_back(id); G[id].push_back(now); now = id; id++; G[now].push_back(id); G[id].push_back(now); id++; } } stack S; S.push(1); vector visited(N + 1, 0); cout << N << endl; while (!S.empty()) { int now = S.top(); S.pop(); visited[now] = 1; for (int nx : G[now]) { if (visited[nx]) continue; cout << now << " " << nx << "\n"; S.push(nx); } } return 0; }