Уг бодлого дээр та $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$