C. Цикл

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

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

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

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

Чиглэлтэй, гогцоогүй, хос орой бүр яг нэг чиглэлт ирмэгээр холбогдсон графыг (тойргийн) "тэмцээн" гэе. Өөрөөр хэлбэл дурын хоёр $u$, $v$ ($u ≠ v$) оройг холбосон $u$-с $v$-руу юм уу эсвэл $v$-с $u$-руу чиглэлтэй ирмэг үргэлж байна.

Танд $n$ оройтой "тэмцээн" өгөгдсөн бол $3$ урттай цикл хайж олно уу.

Оролт

Эхний мөрөнд $n$ тоо ($1 ≤ n ≤ 5000$). Дараагийн $n$ мөрөнд графын ирмэг бүрийн холболтыг хүснэгтээр илэрхийлэх $A$ матриц байна. Хэрвээ $i$ оройноос $j$ орой руу чиглэлтэй ирмэг байгаа бол $A_{i,j} = 1$ ($i$-р мөрийн $j$-р тэмдэгт) үгүй бол $A_{i,j} = 0$ байна.

Өгөгдсөн граф "тэмцээн" байх нь гарцаагүй буюу $A_{i,i} = 0$; $A_{i,j} ≠ A_{j,i}$ ($1 ≤ i, j ≤ n$; $i ≠ j$) байна.

Гаралт

Гурван оройн дугаар $a_1$, $a_2$, $a_3$ ($1 ≤ a_i ≤ n$) байна. Энэ оройнууд $A_{a_1,a_2} = A_{a_2,a_3} = A_{a_3,a_1} = 1$ нөхцлийг хангах ёстой. Олон хариу байвал аль нэгийг нь хэвлэхэд болно.

Хэрвээ ийм гурван орой олдохгүй бол "-1" гэж хэвлэнэ үү.

Орчуулсан: gmunkhbaatarmn

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

Оролт
5
00100
10000
01001
11101
11000
Гаралт
1 3 2 
Оролт
5
01111
00000
01000
01100
01110
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...