B. Уралдааны граф

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

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

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

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

Уг бодлого дээр та $n$ оройтой уралдааны граф байгуулах ёстой. Энэ нь аль ч эрэмбэтэй ($v, u$) ($v ≠ u$) хос оройн хувьд $v$-с $u$-руу $2$-c илүү ирмэг дамжихгүй очдог байх ёстой юм.

Өөрөөр хэлвэл чиглэлтэй, гогцоо агуулаагүй графын хувьд аль ч оройгоор аль ч оройруу дундаа яг $1$ орой дамжиж очиж болдог байвал энэ графыг уралдааны граф гэж нэрлэнэ.

Оролт

Оролтонд графын оройн тоо болох $n$ ($3 ≤ n ≤ 1000$) өгөгдөнө.

Гаралт

Хэрвээ дээрх нөхцлийг хангах граф байхгүй бол $-1$-г хэвлэ.

Эсрэг тохиолдолд мөр бүрт $n$ тоо байх $n$ мөрийг хэвлэнэ. Энэ бол графын холбоос хүснэгт $a$ байх юм. Графын оройнуудыг $1$-с $n$ хүртэл дугаарласан гэж үзвэл $a_{v,u} = 0$ байх юм бол $v$-с $u$-руу зам байхгүй, $a_{v,u} = 1$ байвал зам байдаг гэсэн үг.

Гаралтын граф нь дараах нөхцөлийг хангах уралдааны граф байх ёстой. Үүнд:

  • Бүх $v, u$ ($1 ≤ v, u≤ n$; $v ≠ u$)-н хувьд $a_{v,u} + a_{u,v} = 1$
  • Бүх $v$ ($1 ≤ v ≤ n$)-н хувьд $a_{v,v} = 0$

Орчуулсан: zoloogg

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

Оролт
3
Гаралт
0 1 0
0 0 1
1 0 0
Оролт
4
Гаралт
-1
Сэтгэгдлүүдийг ачааллаж байна...