C. Анивчиж буй мод

хугацааны хязгаарлалт 1 секунд

санах ойн хязгаарлалт 256 мегабайт

оролт стандарт оролт

гаралт стандарт гаралт

Иахуб өөрийн нээж олсон моднуудаар их бахархдаг. Тэрээр "анивчиж буй мод" хэмээх шинэ мод зохион бүтээжээ. Энэхүү шинэ нээлтийнхээ дараа тэрээр хүүхдүүдэд зориулан энэ модоор тоглодог тоглоом зохиож гэнэ.

Тоглоом оройнууд нь $1$-ээс $n$ хүртэл дугаарлагдсан $n$ оройтой модон дээр явагдана. Модны орой бүр дээр анхны утга гэгдэх $init_{i}$ тоо байх ба энэ нь $0$ эсвэл $1$ гэсэн тоо байна. Модны үндсээр $1$-р оройг тэмдэглэе.

Тоглогч тоглолтын явцад модон дээр хэдэн ч үйлдэл хийж болно (огт хийхгүй байсан ч болно). Үйлдэл хийхдээ ямар нэгэн $x$ дугаартай орой сонгоно. Дараа нь $x$ орой дээрх утгыг эсрэгээр нь өөрчлөн ($0$ бол $1$, $1$ бол $0$), $x$-ийн хүүхдүүд дээрх утгыг хэвэнд нь үлдээн, $x$-ийн хүүхдийнх нь хүүхэд мөчрүүд дээрх утгыг өөрчлөн, тэдгээрийн хүүхдийн утгыг хэвээр нь үлдээх гэх мэт навч хүртэл нь үргэлжлүүлнэ.

Тоглоомын зорилго нь $i$ дэх орой бүрийн утгыг $goal_{i}$ ($0$ эсвэл $1$ гэсэн тоо) болгох юм. Чи аль болох цөөн үйлдлээр зорилгодоо хүрэх ёстой.

Оролт

Эхний мөрөнд нэг бүхэл тоо $n$ ($1 ≤ n ≤ 10^{5}$) байна. Дараагийн $n-1$ мөр бүрт $u_{i}$ болон $v_{i}$ оройнууд ирмэгээр холбогдсонг илэрхийлэх $u_{i}$ ба $v_{i}$ ($1 ≤ u_{i}, v_{i} ≤ n$; $u_{i} ≠ v_{i}$) бүхэл тоонууд байна.

Дараах мөрөнд $n$ ширхэг бүхэл тоо байх ба $i$ дэх нь $init_{i}$ ($init_{i}$ нь $0$ эсвэл $1$) тоо байна. Дараагийн мөрөнд мөн $n$ ширхэг бүхэл тоо байх ба $i$ дэх нь $goal_{i}$ ($goal_{i}$ нь $0$ эсвэл $1$) байна.

Гаралт

Эхний мөрөнд хамгийн бага үйлдлийн тоо $cnt$-г хэвлэ. Дараагийн $cnt$ мөр бүрт үйлдэл хийхдээ сонгосон оройн дугаар $x_{i}$-г хэвлэ.

Орчуулсан: Бат-Од

Жишээ тэстүүд

Оролт
10
2 1
3 1
4 2
5 1
6 2
7 5
8 6
9 8
10 5
1 0 1 1 0 1 0 1 0 1
1 0 1 0 0 1 1 1 0 1
Гаралт
2
4
7
Сэтгэгдлүүдийг ачааллаж байна...