Description

尽管不少人都吃过鲜美的草莓，却很少有人真正的看过野草莓的成长。它们从自己的枝上伸出一根根长长的触须，每当遇到合适的地方就会扎根发芽，生长出来一株新的草莓。所以，当你在森林中遇到一株草莓的时候，通常就意味着你会在它的周围找到一片草莓田。但这些草莓并非可以永远做无忧无虑的精灵，树林中穿梭的鸟儿和偶尔路过的鹿群都喜欢吃这种美味的浆果。不过，他们最大的威胁却是来自那些酷爱草莓的棕熊。他们不但可以吃掉整整一片草莓，而且还会粗鲁地把一片草莓田搞得乱七八糟。于是每当一块草莓田越长越大之后，森林中的精灵们就会把一块草莓田分开来种到空地中去，以免被粗鲁的棕熊搞乱。不过这些好心的精灵并不希望把草莓分得太散，因为草莓们会感到孤单。所以她们希望按照空地的数目来分割草莓田，使得每块空地上恰好可以放上一块用触须连接在一起的草莓田，且使得所有空地上含有草莓浆果的最小重量最大。可是天真的精灵并不知道怎么来做这件事情，你可以帮助他们吗？

【任务描述】

你的任务就是要把一片草莓田分割成k块从而转移到k块空地上，而你的这个分割方案需要满足如下的条件：

• 每一块中的草莓必然是直接或者间接通过触须和其他草莓相连接的；
• 这种分割方案所对应的每块空地上草莓重量之和的最小值在所有分割方案中最大；

最后输出你的分割方案和结果。

值得注意的是，虽然按道理来说草莓间互相连接的触须应该符合某些特定的关系，形成一些规则的图案。但在富饶的森林中，长势良好的草莓经常会把触须缠绕在一起。这个时候，精灵们会认为这其实是一根触须。所以精灵们给你的草莓田可能会形成复杂的图案。甚至由于鸟儿或者鹿群的捣乱，一块草莓田中的有些草莓甚至没有通过触须和其他的草莓连接在一起。不过这并不影响最后的结果，你只要把一块草莓田分割成为k块通过触须连接在一起的小草莓田就可以了。

Format

Input

第一行为三个整数 n 、m及 k ，n表示草莓的株数，m表示草莓间伸出的触须的数目，k为空地的数目。

接下来的n行每行两个整数i 及$b_i$，表示第i株草莓上面结了$b_i$克的草莓。顺序下来的m行每行两个整数p 和 q ，表示 p 、q 之间有触须相连接。

另外，在所有这些数据的最后还有单独的一行包括一个整数d 用作评分，有关d 的说明，可以参看下面的评分方法。

Output

你一共要输出k+1行。第一行为一个整数 x ，表示你分割的草莓田中最大的最小重量。然后下面的n 行中，每行第一个整数为$n_i$，表示按照这个重量分割出来的第i块草莓田中含有多少株草莓。然后该行中接下来的$n_i$个整数为这些草莓的编号。请注意一行中草莓必然是通过触须相连接的。

Samples

7 9 3
1 4
2 4
3 3
5 5
6 7
7 2
1 2
1 6
2 3
2 5
2 6
4 5
4 6
6 7
2000000000

7
2 1 6
2 2 3
3 4 5 7

Limitation

输入样例

【评分方法】

你的需要针对berry1.in-berry10.in这10个给定的输入文件给出你的输出berry1.out-berry10.out并放在你的选手目录下。我们将根据你给出的输出文件给出分数。对于某一确定的测试点来说，如果你的输出文件中第一行的x和下面的分割方案不符合，或者是输出文件本身就有错误，那么你将得不到该测试点的分数。这里输出文件的错误可以使用我们提供的berry_check检查工具进行检查。只有当这个程序输出Yes的时候，你的输出才可以确认是可接受的。 可接受的输出将被我们进一步的计算来获得你最后的分数。如果我们记你输出文件中的最大的最小重量为 x ，而我们的最优结果为 best ，则我们根据如下的公式计算你的分数： 这里的d为上面输入数据中最后一行输入的整数。

【你如何测试自己的输出】

我们提供berry_check这个工具作为测试你的输出文件的办法。使用这个工具的方法是： berry_check <输入文件名> <输出文件名> 在你调用这个文件后，berry_check将根据你给出的输入和输出文件给出测试的结果，其中包括：

• 非法退出：该点得0分；
• not connect：你程序输出的行中含有不连通的分量；
• duplicate：同一点输出了两次；
• extra：输出文件中包括多余数据；
• lack：输出的总点数不对；
• answer not match：输出中第一行的结果和实际结果不符；
• Yes：输出正确，将进行下一步的评分。