C. Систем администратор

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

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

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

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

Боб $X$ корпорацид систем администраторийн ажилд оржээ. Түүний эхний ажил нь $2$ талаасаа оролттой $m$ ширхэг кабел ашиглан $n$ серверийг холбох ба аль ч хоёр сэрвэрийн хооронд мэдээлэл дамжуулах боломжтой болох юм. Шууд холболт бүр $2$ өөр серверийг хооронд нь холбох ёстой ба аль ч хоёр сервер хамгийн ихдээ нэг шууд холболттой байх ёстой.

$X$ корпорацийн өрсөлдөгч болох $Y$ корпораци Боб-д татгалзаж боломгүй санал тавиад нэг нэмэлт нөхцөл оруулахыг хүсчээ. Хэрэв $v$ дугаартай сервер унавал, аль ч хоёр серверийн хооронд мэдээлэл дамжуулах боломжгүй болох ба өөрөөр хэлбэл системийн бүтэн байдал алдагдана. Боб-д серверүүдийг ингэж холбоход туслаарай.

Оролт

Оролтын эхний мөрөнд зайгаар тусгаарлагдсан $n$,$m$,$v$ ($3 ≤ n ≤ 105$, $0 ≤ m ≤ 105$, $1 ≤ v ≤ n$) 3 бүхэл тоо агуулагдана, $n$ - серверийн тоо, $m$ - шууд холболтын тоо, $v$ - системийг бүтэн байдлыг алдагдуулах серверийн дугаар.

Гаралт

$m$ мөрөнд мөр тус бүрд хоорондоо шууд холбогдох $2$ сэрвэрийн дугаар байна. Серверийг $1$-ээс эхэлж дугаарлана. Олон боломжит хариу байвал аль нэгийг нь л хэвлэхэд болно.

Шаардагдсан аргаар серверүүдийг холбох боломжгүй бол гаралт нь $-1$ байна.

Орчуулсан: kami-sama

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

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