小红的树形 dp

题号：NC268995
时间限制：C/C++/Rust/Pascal 1秒，其他语言2秒
空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld

题目描述

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

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

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

示例1

复制

4
?dd?
1 2
1 3
1 4

复制

pddd

示例2

复制

4
dd??
1 2
1 3
1 4

复制

-1