E. Антигинж

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

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

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

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

$0$-с $(n-1) $ хүртэл дугаарлагдсан $n$ ширхэг оройтой циклгүй чиглэлт граф өгөгджээ. Энэ граф нь $0$-с $(n-1)$ хүртэл дугаарлагдсан $n$ ширхэг ирмэгтэй ба $i$ дугаартай ирмэг нь $i, (i+1)modn$ оройнуудыг холбогдог ба аль ч тал руугаа чиглэсэн байж болно. ($i$-с $(i+1)$ рүү эсвэл $(i+1)$-с $i$-рүү)

$x$ тоог $y$ тоонд хуваахад гарах үлдэгдлийг $x mod y$ гэж тэмдэглэдэг.

Граф дахь $u,v$ хос оройнуудын хувьд эдгээрийн аль нэгнээс нөгөө рүү нь хүрэх зам олддог бол энэ 2 оройг харьцуулагдахуйц оройнууд гэе. Антигинж гэдэг нь аль ч 2 нь харьцуулагдахуйц биш оройнуудын олонлог юм. Антигинжийн чадал гэдэг нь энэ олонлог дахь оройнуудын тоо юм. Өөрөөс нь илүү чадалтай антигинж үл олдох антигинжийг максимум гэе.

Таны даалгавар өгөгдсөн граф дахь максимум антигинжийн чадлыг олох юм.

Оролт

Эхний мөрөнд тэг нэгээс тогтох $s_0s_1... s_{n-1} (2\le n\le 10^6)$ тэмдэгтүүдийн дараалал өгөгдөнө үүний урт $(n)$ нь өгөгдсөн граф дахь орой ба ирмэгийн тоотой давхацна. Хэрэв $s_i (i\ge 0)$ нь 0 байвал $i$ , $(i+1) mod n$ оройнуудыг холбосон ирмэг $i$-р оройгоос $(i + 1) mod n$-р орой рүү чиглэлтэй байна. Нөгөө тохиолдолд ирмэг нь эсрэг чиглэлтэй байна.

Өгөгдсөн граф нь циклгүй байна.

Гаралт

Өгөгдсөн граф дахь максимум антигинжийн чадлыг илтгэх тоог хэвлэ.

Орчуулсан: Төрбат

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

Оролт
001
Гаралт
1
Оролт
110010
Гаралт
3

Тэмдэглэл

Consider the first test sample. The graph's $G$ edges are: $0 -> 1$, $1 -> 2$, $0 -> 2$. We can choose the set of vertexes $[0]$ as the maximum antichain. We cannot choose an antichain of larger size.

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