문제
오늘도 세상을 위해 도둑일을 계획하고 있는 의적 임꺽정. 그러나 옛날과는 달리 궁궐에 CCTV가 너무 많이 설치되어 있어 임꺽정은 아무것도 못하고 있다.
세상이 너무나 변한걸 느낀 임꺽정은 철저한 궁궐 조사와 해킹 공부를 하기 시작했는데,
그 성과로 궁궐의 CCTV 연결구조를 알게 되었고, 조작할 수 있는 방법도 터득했다!!
궁궐의 CCTV는 총 N개가 있으며 특별한 구조로 이루어져 있는데,
모든 CCTV는 서로 직, 간접적으로 연결되어 있는 형태로, N-1개의 연결관계로 이루어져 있다는 것이다.
CCTV의 조작은 특정 CCTV를 토글 형태로, 끄고 켜는게 가능하지만, 직접적으로 연결된 CCTV들 역시 토글 형태로 동작을 하게된다는 점이다.
(토글은 꺼져있으면 켜지고 켜져있으면 꺼진다는 뜻이다.)
CCTV가 너무 자주 꺼졌다가 켜지면 병사들이 알아챌 수 있으니 최소한의 조작으로 모든 CCTV를 끄는것이 좋다.
따라서 의적 임꺽정에게 최소 몇번의 조작이 필요한지 알려주자.
입력
첫 번째 줄에 CCTV의 수 N이 주어집니다. ( 3 <= N <= 100000 )
다음 줄부터 N-1줄에 걸쳐 CCTV 연결 관계가 공백을 구분으로 CCTV의 번호가 두개 주어집니다. (CCTV의 번호는 1번부터 N번까지 입니다.)
마지막줄에는 초기 CCTV의 상태가 N개의 정수로 주어집니다. (0일 경우 꺼져있음. 1일 경우 켜져있음.)
출력
첫 줄에 모든 CCTV를 끄는데 필요한 최소 조작 횟수를 출력한다.
모든 CCTV를 끄는것이 불가능한 경우 impossible을 출력하면 된다.
예제1
5
12
13
24
25
01011
4
예제2
5
12
23
34
45
01111
impossible