A. Хувьсагч эсвэл Тэнд эсвэл Энд

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

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

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

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

Вася гэж нэрлэгдэх хувьсагчийн хувьд амьдрал тийм ч амар биш байлаа. Тэрээр хаашаа ч явсан нэг болго утга оноогдож байна нэг бол анигдаж байна эсвэл хэрэглэгдэж байх ажээ.

Вася-ын амьдрал программын нөхцөлийн дагуу үргэлжилж байв. Нөхцөл болгон дээр Вася хэрэглэгдэж байна (жишээлбэл өөр хувьсагчийн утгыг тооцоолж байна), утга оноогдож байна эсвэл анигдаж байх юм. Түүнчлэн зарим нөхцөлүүдийн хооронд чиглэлтэй шилжилтүүд оршин байх ажээ.

Зам гэдэг нь $v_{1}, v_{2}, ..., v_{x}$ гэсэн нөхцөлүүдийн дарааллыг хэлэх бөгөөд энд ямар ч $1 ≤ i < x$-ын хувьд $v_{i}$-аас $v_{i + 1}$ хүртэлх шилжилт оршин байх юм.

Хэрэв ямар нэгэн $i$ $(1 ≤ i ≤ k)$-ын хувьд $p_{i} = v$ ба $p_{1}$-р нөхцөл дээр Вася-д утга оноогдож, $p_{k}$-р нөхцөл дээр Вася хэрэглэгдэх бөгөөд өөр ямар ч $p_{i}$-р нөхцөлийн ($p_{1}$-аас бусад) хувьд Вася-д утга оноогоогүй байх $p_{1}, p_{2}, ..., p_{k}$ гэсэн зам оршин байвал $v$-р нөхцөл дээрх Вася-ын утгыг дэлхий ертөнц маш сонирхон хүлээн авах юм.

Тэгвэл Вася-д туслан Вася-ын утгыг дэлхий ертөнц маш сонирхон хүлээж авах нөхцөлүүдийг олж өгнө үү.

Оролт

Эхний мөрөнд зайгаар тусгаарлагдан 2 бүхэл тоо $n$ болон $m$ ($1 ≤ n, m ≤ 10^{5}$) өгөгдөх ба эдгээр нь харгалзан нөхцөлүүдийн тоо болон шилжилтүүдийн тоог илэрхийлнэ.

2-дахь мөрөнд зайгаар тусгаарлагдсан $n$ ширхэг бүхэл тоонууд $f_{1}, f_{2}, ..., f_{n}$ ($0 ≤ f_{i} ≤ 2$)-ууд өгөгдөх ба энд $f_{i}$ нь $i$-р нөхцөл дээрх Вася-д хийгдэх үйлдлийг илэрхийлнэ: $0$ гэдэг нь анигдаж буйг, $1$ гэдэг нь утга оноогдож байгааг, $2$ гэдэг нь хэрэглэгдэж байгааг илэрхийлнэ.

Дараагийн $m$ ширхэг мөрөнд зайгаар тусгаарлагдсан хос бүхэл тоонууд $a_{i}, b_{i}$ ($1 ≤ a_{i}, b_{i} ≤ n$, $a_{i} ≠ b_{i}$)-ууд өгөгдөх ба хос болгон нь $a_{i}$ дугаартай нөхцөлөөс $b_{i}$ дугаартай нөхцөл хүртэлх шилжилтийг илэрхийлэх юм. 2 нөхцөлийн хооронд хэдэн ч тооны шилжилт оршин байж болно.

Гаралт

$r_{1}, r_{2}, ..., r_{n}$ гэсэн $n$ ширхэг бүхэл тоонуудыг хооронд нь зайгаар эсвэл шинэ мөрүүдээр тусгаарлан хэвлэнэ үү. Хэрэв $i$-р нөхцөл дээрх Вася-ын утгыг дэлхий ертөнц маш сонирхон хүлээн авах бол $r_{i}$ нь $1$-тэй тэнцүү байх бөгөөд бусад тохиолдолд $0$-тэй тэнцүү байх юм. Түүнчлэн нөхцөлүүд нь оролтод өгөгдсөн дарааллаараа $1$-ээс $n$ хүртэл дугаарлагдсан байна.

Орчуулсан: Баатархүү

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

Оролт
4 3
1 0 0 2
1 2
2 3
3 4
Гаралт
1
1
1
1
Оролт
3 1
1 0 2
1 3
Гаралт
1
0
1
Оролт
3 1
2 0 1
1 3
Гаралт
0
0
0

Тэмдэглэл

Эхний жишээн дээр бодлогын нөхцөлүүдийг ашиглан Вася-ын утгыг дэлхий ертөнц маш сонирхон хүлээж авхаар цор ганц зам гарган авч чадах бөгөөд 1 2 3 4 энэ зам нь бүх нөхцөлийг агуулж байна. Түүнчлэн эдгээр бүх нөхцөлүүдийн хувьд Вася-ын утгыг дэлхий ертөнц маш сонирхон хүлээж авах юм.

2-дахь жишээнд бодлогын нөхцөлүүдийг ашиглан Вася-ын утгыг дэлхий ертөнц маш сонирхон хүлээж авхаар цор ганц зам гарган авч чадах бөгөөд 1 3 харамсалтай нь 2-р нөхцөл нь уг зам дотор агуулагдаагүй байна.

3-дахь жишээнд Вася-ын утгыг дэлхийн ертөнц маш сонирхон хүлээн авч байхаар эдгээр нөхцөлүүдийг ашиглан ямар ч зам гарган авч чадахгүй байна. Иймд Вася-ын утгыг хэзээ ч дэлхий ертөнц сонирхохгүй ажээ.

Сэтгэгдлүүдийг ачааллаж байна...