小红拿到了一棵树，每个节点上有一个字符，每个节点上的字符为'd'、'p'、'?'这三种。 现在请你将所有'?'字符变成'd'或者'p'字符，需要满足任意两个相邻节点的字符不同。你能帮帮她吗？

输入描述:

第一行输入一个正整数，代表节点的数量。第二行输入一个长度为的、仅包含'?'、'd'和'p'的字符串。第个字符代表号节点的初始字符。接下来的行，每行输入两个正整数，代表节点和节点有一条边连接。

输出描述:

如果无解，请输出 -1。否则输出一个由'd'和'p'组成的字符串，第个字符代表最终号节点上的字符。