트리 불 끄기

$N$개의 정점으로 이루어진 트리가 있다. 트리는 간선에 방향이 없는 연결 그래프이며, 임의의 두 정점을 잇는 최단 경로가 하나뿐이다. 각 정점에는 전구와 스위치가 있다. 전구는 켜져 있거나 꺼져 있으며, 정점의 스위치를 누르면 그 정점의 전구 상태가 바뀐다. 켜진 전구는 꺼지고, 꺼진 전구는 켜진다.

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

• 밥이 $v$번 정점에 있다고 하자. $v$번 정점과 인접한 $u$번 정점을 고른 뒤, $v$번 정점의 스위치를 누르고 $u$번 정점으로 이동한다.

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

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

두 번째 줄에 전구의 상태를 나타내는 길이 $n$의 문자열 $S$가 주어진다. $i$번 정점의 전구가 켜져 있으면 $i$번째 문자는 \tt{'1'}이고, 꺼져 있으면 \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번의 절차를 수행했으며, 절차가 끝난 뒤 트리의 전구는 모두 꺼진 상태이다.