题目描述

Mis R 有 m 颗糖，编号为 1,2,⋯ ,m 。他打算发给 n 个小朋友。发完糖之后，为了促进小朋友之间的友谊，他会安排 r 次互换活动。每次互换活动，会让第 x 个小朋友和第 y 个小朋友交换手里的糖果。现在 Mis R 想知道最终每个小朋友手中有哪些糖果。

输入格式

第一行两个整数 n , m , r （2 ≤ n ≤ 1000，1 ≤ m , r ≤ ${10}^6$ ），表示 n 个小朋友， m 颗糖， r 次互换安排。

第二行:有 m 个整数，表示第 i 个糖果发给了第 $a_i$ 个小朋友。

接下来 r 行，每行两个整数 x,y，表示第 x 个小朋友和第 y 个小朋友互换手中的糖果。

数据保证 1 ≤ $a_i$ , x , y ≤ n，x ≠ y。

输出格式

n 行，每行以一个整数 $c_i$ 开头，表示第 i 个小朋友含有的糖果数，接下来是一个长度为 $c_i$ 的递增编号序列，整数之间用空格隔开，表示第 i 个小朋友手中糖果的编号。

样例

3 6 1
1 3 2 1 3 2
2 3

2 1 4
2 2 5
2 3 6

提示

一个小朋友可能有不止一颗糖，所以，两个小朋贾环糖的时候不是交换一粒，而是用一组糖去换另外一组糖。