经过深思熟虑之后，小贱君打算去M国闯一闯，那是一个古老的东方国度，传说有很多高阶魔法师，他想成为一名伟大的魔法师，将来征服星辰大海。 经过千辛万苦，小贱君终于来到了M国，不幸的是刚进城门小贱君就被M国的守城士兵困在了一种叫做“困兽之斗”的阵法之中。 士兵对小贱君说：“看到漂浮在你身边的宝石了吗？彩虹连接的两颗宝石可以任意交换位置，你需要通过一系列交换后使得宝石组成的字符串的字典序最小。若不能破阵，那还是请回吧！” 小贱君观察了一下周围的宝石，只见每颗宝石上标有一个小写字母，而且有一些宝石上通过彩虹与其他宝石相连。 琢磨了半天，他终于搞懂了这个阵法的意思： 若宝石系列为：dcba 其中有两道彩虹，分别是(0,1),(1,2),代表第一个位置上的宝石可以和第二个位置上的宝石互换，第二个位置上的宝石可以和第三个位置上的宝石互换，最终可以得到字典序最小的宝石系列：bcda。 作为小贱君的死党，你有什么方法帮助他破阵吗？ 输入描述: 输入包含多组测试数据。 对于每组测试数据： 字符串s --- 代表宝石序列 n --- 代表有n条彩虹 接下来n行，每行两个数ai,bi --- 表示ai和bi由一条彩虹相连。 保证： 1<=s的长度<=10000 1<=n<=10000 且输入数据均合法。 输出描述: 对于每组数据，输出一个字符串 示例1 输入 dcba 2 0 1 1 2 hellonowcoder 4 0 1 1 4 2 5 2 3 输出 bcda ehllonowcoder