Програмчлалын олимпиадын бодлогын архив

Нохойтой дөрвөн танкчин Германы дөрвөн хотод тус тусдаа байгаа ба нэг хотод уулзах хэрэгтэй байгаа. Аюулгүй байдлын үүднээс нэг хотод хоёр өдөр дараалан байж болохгүй. Дөрвөн танкчин нэг хотод цуглахаас өмнө ямар ч хоёр танкчин нэг хотод зэрэг байж бас болохгүй. Дөрвөн танкчин нэг хотод дөрвүүлээ, нэг өдөр уулзах боломжтой эсэхийг тодорхойлох програм бич.

Input

Эхний мөрөнд хотуудын тоо болон тэдгээрийг  холбосон нэг чиглэлтэй замуудын тоог илэрхийлэх n, m тоонууд зайгаар тусгаарлагдан өгөгдөнө (4<=n<=40, 1<=m<=n*(n-1)).

Дараагийн m ширхэг мөрөнд x, y тоонууд байх ба энэ нь x хотоос y хот хүрэх нэг чиглэлт зам байгаа гэсэн үг юм (1<=x, y<=n). Ямар нэг хотоос өөр рүү нь орсон зам байхгүй ба мөн аль нэг хоёр хотыг нэг чиглэлд холбосон хоёр зам байхгүй.

Сүүлийн мөрөнд 4 ялгаатай тоо байх ба энэ нь танкчдын анх байсан хотуудын дугаар юм.

Output

Дөрвөн танкчны уулзах хүртэл хамгийн багадаа хэдэн хоног өнгөрөхийг ол. Хэрэв тэр дөрөв уулзах боломжгүй бол 0-ийг гарга.

Example

Input:
5 4
1 5
2 5
3 5
4 5
1 2 3 4

Output:
1
Input:
5 4
1 5
2 5
3 5
4 1
1 2 3 4
Output:
0