크산두 쿠데타

미술 평론가로서 매일같이 미술관을 찾아다녀야 하는데 전시품을 만질 수도 없다니, 도저히 견딜 수 없게 되었다. 그래서 미술 도둑으로서의 경력을 다시 한번 시도해 보기로 했다.* 하지만 데뷔전이 완전히 망한 뒤였기에, 이번에는 감시 카메라 문제를 반드시 해결하기로 마음먹었다.

그래서 IT 기술을 동원해 카메라 제어 시스템에 침입했다. 안타깝게도 카메라 자체가 최근 설치된 작품 Xanadu의 일부이다. 이 때문에 다소 이상한 동작이 나타난다. 미술관 곳곳에 $N$대의 카메라(1, …, $N$번)가 있는데, 예술적 이유로 이미 꺼져 있는 카메라도 있을 수 있다. $N$대의 카메라는 $N - 1$개의 전선으로 연결되어 있어, 어떤 두 카메라든 직접 또는 간접적으로 연결되어 있다. 카메라 제어 시스템에는 카메라마다 버튼이 하나씩 있다. 그런데 이 버튼을 누르면 그 카메라 하나만 전환되는 것이 아니라, 그 카메라에 직접 연결된 모든 카메라도 함께 전환된다.†

카메라 제어 시스템을 너무 많이 조작하면 해킹 사실이 들킬까 걱정된다. 모든 카메라를 끄는 데 필요한 최소 버튼 누름 횟수를 계산하는 프로그램을 작성하라.

* 게다가 낮에는 미술 평론가, 밤에는 미술 도둑이라는 두 활동 사이의 놀라운 시너지도 눈치챘다. 의심을 사지 않고 답사할 수 있다든가, 미리 극찬 리뷰를 써서 훔칠 작품의 가격을 올린다든가 하는 식이다.

† 이것은 우리 자신의 안녕과 기분이 가장 가까운 사람들의 안녕에 영향을 준다는 것에 대한 은유이다. 정말로.

첫째 줄에는 미술관의 카메라 수 $N$이 정수로 주어진다.

다음 $N - 1$개 줄에는 각각 두 정수 $a$와 $b$가 주어진다($1 \le a, b ≤ N$, $a \ne b$). 이는 카메라 $a$와 $b$가 전선으로 직접 연결되어 있음을 뜻한다.

마지막 줄에는 $N$개의 정수가 주어진다. $i$번째 정수는 카메라 $i$가 처음에 켜져 있으면 1, 꺼져 있으면 0이다.

프로그램은 한 줄을 출력해야 한다. 이 줄에는 모든 카메라를 끄는 데 필요한 최소 버튼 누름 횟수를 정수로 출력하거나, 모든 카메라를 끄는 것이 불가능하면 문자열 impossible을 출력한다.

• $3 \le N \le 100 000$

다음 그림은 첫 번째 샘플을 보여준다.

모든 카메라를 끄는 최적의 버튼 누름 순서는 카메라 4, 5, 3, 1의 버튼을 이 순서대로 누르는 것이다.