Team Change

문제

Mr. Smith, the physical education teacher at Rocky Mountain High School, likes to take a hands-off approach to teaching gym class. What does that mean? A lot of dodgeball!

For the last few months, the students have been split into the same two teams. But now some students are asking for a change.

Some students want to be assigned to a specific team. Also, certain pairs of students that are currently on opposite teams have become rivals and are unwilling to be on each other's team.

Since Mr. Smith does not want to be complacent he has decided to shuffle the teams. He realizes it is not necessarily possible to form new teams satisfying both of the above constraints. To solve this, he will make some students sit the next game out.

Your job is to help Mr. Smith form the new teams that satisfy the above constraints such that the number of students who must sit out is minimum. Note that the teams do not need to have the same number of players nor does a team have to have any players at all.

입력

The first line of input contains two integers $NN$ ($1\le N\le 10001\; \backslash leq\; N\; \backslash leq\; 1\backslash ,000$), which is the number of students, and $RR$ ($0\le R\le 100000\; \backslash leq\; R\; \backslash leq\; 10\backslash ,000$), which is the number of rivalries.

The next line contains a string which describes the current teams. The string has length $NN$ consisting of characters A and B. The $ii$th character on this line is the team that the $ii$th student is currently playing for.

The next line contains a string which describes the students' requested teams. The string has length $NN$ consisting of characters A, B, and ?. The $ii$th character on this line is the desired team of the $ii$th student or ? if the student has no preference.

The next $RR$ lines describe the rivalries. Each line contains two distinct integers $ii$ ($1\le i\le N1\; \backslash leq\; i\; \backslash leq\; N$) and $jj$ ($1\le j\le N1\; \backslash leq\; j\; \backslash leq\; N$), which indicates that student $ii$ and student $jj$ are rivals. Rival students are on different teams. No rival pair of students will be reported more than once.

출력

Display a valid team formation with the minimum number of students sitting out. If the $ii$th student is to sit out of the game, the $ii$th character should be X. Otherwise, the $ii$th character of this line should either be A or B, indicating which team this player is assigned to.

If there are multiple possible solutions, display any of them.

5 4
AAABB
??AAA
1 4
2 4
3 4
3 5

BBXAA

2 1
AB
AA
1 2

XA

8 8
ABBABAAA
?B?ABBAB
1 2
4 3
6 5
4 5
1 5
2 8
3 7
2 4

BXBAXBAB