문제

개의 정점으로 구성된 트리가 있다. 트리는 간선에 방향이 없는 연결된 그래프로, 각 정점에서 다른 정점으로 가는 최단 경로가 유일하다. 각 정점에는 전구와 스위치가 있는데, 각 전구는 켜져 있거나 꺼져 있다. 정점에 있는 스위치를 누르면, 그 정점의 전구의 상태가 바뀐다. 즉, 켜진 전구는 꺼지고, 꺼진 전구는 켜진다.

밥은 이 트리 위에 살고 있는 나무늘보이다. 밥은 처음에 번 정점에 있는데, 다음의 절차를 번 이상 수행해 트리의 전구를 모두 꺼진 상태로 만들고자 한다.

• 현재 밥이 번 정점에 있다고 하자. 번 정점에 인접한 번 정점을 선택한 뒤, 번 정점에 있는 스위치를 누르고 번 정점으로 이동한다.

밥을 도와 위 절차를 번 이하로 수행해 트리의 전구를 모두 꺼진 상태로 만들 수 있는 방법을 찾아 주자. 문제의 조건 하에 그러한 방법이 언제나 존재함을 증명할 수 있다.

입력

첫 번째 줄에 정점의 개수 과 밥이 처음에 위치한 정점의 번호 가 공백으로 구분되어 주어진다.

두 번째 줄에 전구의 상태를 나타내는 길이 의 문자열 가 주어진다. 번 정점의 전구가 켜져 있는 상태라면 번째 문자는 1, 그렇지 않다면 번째 문자는 0이다.

세 번째 줄부터 개의 줄에 걸쳐 각각의 간선이 연결하는 두 정점의 번호 , 가 공백으로 구분되어 주어진다.

주어진 그래프는 올바른 트리임이 보장된다.

출력

첫 번째 줄에 밥이 트리의 전구를 모두 꺼진 상태로 만들기 위해 사용할 절차의 횟수 를 출력한다.

두 번째 줄에 각 절차에서 선택한 정점을 나타내는 개의 정수 를 공백으로 분리하여 출력한다. 이때 번 정점은 번 정점에 인접해야 하며, 인 모든 에 대해 번 정점은 번 정점에 인접해야 한다.

조건에 따라 트리의 전구을 모두 꺼진 상태로 만드는 방법이 여러 가지라면 그 중 하나만 출력한다. 또한, 수행하는 절차의 수가 최소가 될 필요는 없다.

Note

예제에서 밥이 따르는 절차와 그에 따른 전구의 상태는 아래와 같다.

1. 밥이 번 정점으로 이동하고, 번 정점의 전구가 꺼진다.
2. 밥이 번 정점으로 이동하고, 번 정점의 전구가 꺼진다.
3. 밥이 번 정점으로 이동하고, 번 정점의 전구가 켜진다.
4. 밥이 번 정점으로 이동하고, 번 정점의 전구가 꺼진다.
5. 밥이 번 정점으로 이동하고, 번 정점의 전구가 꺼진다.
6. 밥이 번 정점으로 이동하고, 번 정점의 전구가 켜진다.
7. 밥이 번 정점으로 이동하고, 번 정점의 전구가 켜진다.
8. 밥이 번 정점으로 이동하고, 번 정점의 전구가 꺼진다.
9. 밥이 번 정점으로 이동하고, 번 정점의 전구가 꺼진다.
10. 밥이 번 정점으로 이동하고, 번 정점의 전구가 켜진다.
11. 밥이 번 정점으로 이동하고, 번 정점의 전구가 꺼진다.
12. 밥이 번 정점으로 이동하고, 번 정점의 전구가 꺼진다.

총 번의 절차를 시행하였으며, 절차가 끝난 후 트리의 전구는 모두 꺼진 상태이다.