문제

부터 까지 번호가 붙은 개의 정점으로 이루어진 트리가 있다. 각 정점에는 알파벳 C, T, P 중 하나가 쓰여 있다. 다음 조건을 만족하는 단순 경로를 CTP 경로라고 하자.

• 경로에 포함된 정점들의 문자를 순서대로 나열했을 때, 그 문자열이 "CTP"를 무한히 이어 붙인 "CTPCTPCT..." 문자열의 접두사이면 이 경로를 CTP 경로라고 한다.

예를 들어 위 그림의 트리에서 서로 다른 CTP 경로는 [2], [2, 1], [2, 1, 3], [2, 1, 3, 6], [2, 4], [6]이 있다.

당신은 CTP 경로가 최대한 많은 트리를 좋아한다. 트리에서 정점 하나를 골라서 적혀 있던 문자를 지우고 원하는 문자를 적어 넣어서 서로 다른 CTP 경로의 개수를 최대화해 보자. 지우기 전에 적혀 있던 문자와 같은 문자를 다시 적어 넣을 수도 있다.

입력

첫 번째 줄에 정수 이 주어진다. ()

두 번째 줄에 번 정점부터 번 정점까지 각 정점에 적혀 있는 문자들이 공백 없이 순서대로 주어진다. 각 문자는 C, T, P 중 하나이다.

세 번째 줄부터 개의 줄에 걸쳐서 간선의 정보가 주어진다. 간선은 , 의 형태로 주어진다. 이는 트리의 번 정점과 번 정점이 간선으로 연결되어 있음을 의미한다. ()

출력

첫 번째 줄에 수정할 정점 번호를 출력한다.

두 번째 줄에 적어 넣을 문자를 출력한다. 적어 넣을 문자는 C, T, P 중 하나다.

서로 다른 CTP 경로의 개수를 최대화하는 방법이 여러 가지라면, 그중 아무것이나 하나를 출력한다.