Planar Perimeter

题意翻译

## 题目描述 Ujan终于把他的房子打扫干净了，现在想装饰一下室内。他决定放置一块漂亮的地毯，将客房真正地连接起来。 他对多边形图块组成的地毯感兴趣，这样的图块的每一边要么是另一个（不同）图块的一边，要么是整个地毯外侧的一边。换句话说，地毯可以被表示为一个平面图，每个图块都对应于图的一面，每一面都是一个简单的多边形。地毯的周长就是图的外侧边的数量。 如果一个地毯由 $f$ 个图块组成，其中第 $i$ 个图块正好有 $a_{i}$ 条边，并且周长是最小的，那么Ujan认为它是美丽的。找到一个这样的地毯，这样Ujan就可以订购它了! ## 输入格式 输入的第一行包含一个整数 $f$ ( $1 \le f \le 10^5$ )，表示地毯中图块的数量。 下一行包含 $f$ 个整数 $a_{1},...,a_{f}$ ( $3 \le a_{i} \le 3 \cdot 10^5 $，表示每个图块的边数。图块的边数 $a_{1} +...+ a_{f}$ 不会超过 $3 \cdot 10^5 $。 ## 输出格式 以图的形式输出地毯的描述 首先，输出一个整数 $n$ ( $3\le n\le 3\cdot 10^5$ ),表示图的节点数（节点必须从 $1$ 到 $n$ 编号）。 然后输出 $f$ 行，包含图的每一面的描述。第 $i$ 行应该描述第 $i$ 面，并且包含 $a_{i}$ 个不同的整数 $v_{i,1},...,v_{i,a_{i}}$ ( $1\le v_{i,j}\le n$ )，表示节点 $v_{i,j}$ 和节点 $v_{i,(j\mod a_{i})+1}$ 被任意一边连接。 该图应是平面的，并且满足问题描述中的限制，它的周长应该尽可能小。 **图中不应有重边或自环。** 图应是连通的。请注意，答案始终有解；如果有多个解，输出其中任何一个。

题目描述

Ujan has finally cleaned up his house and now wants to decorate the interior. He decided to place a beautiful carpet that would really tie the guest room together. He is interested in carpets that are made up of polygonal patches such that each side of a patch is either a side of another (different) patch, or is an exterior side of the whole carpet. In other words, the carpet can be represented as a planar graph, where each patch corresponds to a face of the graph, each face is a simple polygon. The perimeter of the carpet is the number of the exterior sides. Ujan considers a carpet beautiful if it consists of $ f $ patches, where the $ i $ -th patch has exactly $ a_i $ sides, and the perimeter is the smallest possible. Find an example of such a carpet, so that Ujan can order it!

输入输出格式

输入格式

The first line of input contains a single integer $ f $ ( $ 1 \leq f \leq 10^5 $ ), the number of patches in the carpet. The next line contains $ f $ integers $ a_1, \ldots, a_f $ ( $ 3 \leq a_i \leq 3\cdot 10^5 $ ), the number of sides of the patches. The total number of the sides of the patches $ a_1 + \ldots + a_f $ does not exceed $ 3\cdot10^5 $ .

输出格式

Output the description of the carpet as a graph. First, output a single integer $ n $ ( $ 3 \leq n \leq 3 \cdot 10^5 $ ), the total number of vertices in your graph (the vertices must be numbered from $ 1 $ to $ n $ ). Then output $ f $ lines containing the description of the faces. The $ i $ -th line should describe the $ i $ -th face and contain $ a_i $ distinct integers $ v_{i,1}, \ldots, v_{i,a_i} $ ( $ 1 \leq v_{i,j} \leq n $ ), which means that the vertices $ v_{i,j} $ and $ v_{i,(j \bmod{a_i})+1} $ are connected by an edge for any $ 1 \leq j \leq a_i $ . The graph should be planar and satisfy the restrictions described in the problem statement. Its perimeter should be the smallest possible. There should be no double edges or self-loops in the graph. The graph should be connected. Note that a solution always exists; if there are multiple solutions, output any of them.

输入输出样例

输入样例 #1

2
3 3

输出样例 #1

4
2 1 4 
1 2 3 

输入样例 #2

3
5 3 5

输出样例 #2

6
1 2 3 4 5
4 5 6
1 3 4 6 5

说明

In the first sample, the two triangular faces are connected by a single edge, which results in the minimum perimeter $ 4 $ . The figure shows one possible configuration for the second sample. The minimum perimeter in this case is $ 3 $ .