题目

给定一个 \(n\times n\) 的 01 矩阵（的上三角部分）\(A_{n\times n}\)。

构造一棵有 \(n\) 个结点的树，满足：

对于任意的 \(1\le l\le r\le n\)，编号在 \([l,r]\) 内的结点在树上构成一个连通块当且仅当 \(A_{l,r}=1\)。

数据保证有解。

单个数据点内有多组测试数据。所有数据点满足 \(1\le n\le 2000, \sum n\le 2000\)。

分析

没什么用的想法：如果图 \(G\) 是森林，那么 \(|V|\ge|E|+1\)，且当且仅当 \(|V|=|E|+1\) 时 \(G\) 是树。

这个性质最后并没能帮助我们构造，但是它却很好地帮助我们解决了“生成数据”和“检查输出”的问题。