31996번 - 트리 불 끄기 스페셜 저지

문제

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

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

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

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

입력

첫 번째 줄에 정점의 개수 $N$과 밥이 처음에 위치한 정점의 번호 $a$가 공백으로 구분되어 주어진다. $(2 \le N \le 100,000円;$ 1ドル \le a \le N)$

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

세 번째 줄부터 $N-1$개의 줄에 걸쳐 각각의 간선이 연결하는 두 정점의 번호 $x_i,ドル $y_i$가 공백으로 구분되어 주어진다. $(1 \le x_i < y_i \le N)$

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

출력

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

두 번째 줄에 각 절차에서 선택한 정점을 나타내는 $k$개의 정수 $u_1,u_2,\cdots,u_k$를 공백으로 분리하여 출력한다. 이때 $u_1$번 정점은 $a$번 정점에 인접해야 하며, 2ドル \le i \le k$인 모든 $i$에 대해 $u_i$번 정점은 $u_{i-1}$번 정점에 인접해야 한다.

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

제한

노트

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

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

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