Ot mütəxəssisi

İnəklərinin otlama marşrutlarına daha yaxşı nəzarət etmək istəyən fermer Con öz təsərrüfatı boyunca inəklər üçün bir tərəfli yollar çəkmişdir. Təsərrüfat $1$-dən $n$-ə qədər nömrələnmiş $n$ tarladan ibarətdir, hər bir bir tərəfli yol isə tarla cütlərindən birini birləşdirir. Məsələn, əgər yol $x$ tarlasından $y$ tarlasına gedirsə, inəklər $x$-dən $y$-ə hərəkət edə bilər, amma $y$-dən $x$-ə hərəkət edə bilməzlər.

Bessi, hamımızın bildiyi kimi, mümkün qədər çox tarlada ot yeməyi sevir. Günün əvvəlində o, həmişə $1$ tarlasında olur və günün sonunda onu yenidən $1$ tarlasına qaytaran müəyyən bir marşrut üzrə hərəkət edir. O, yolu boyunca ziyarət etdiyi müxtəlif tarlaların sayını maksimuma çatdırmaq istəyir, çünki onların hər birində ot yeyə bilər. Əgər o, eyni tarlanı bir neçə dəfə ziyarət edərsə, həmin tarladakı ot yalnız bir dəfə hesablanır.

Təxmin edilə biləcəyi kimi, Bessi fermer Conun yollardaki bir tərəfli hərəkət qadağasından çox razı deyil, çünki bu, onun gün ərzində ziyarət edə biləcəyi müxtəlif tarlaların sayını məhdudlaşdırır. O bilmək istəyir ki, əgər ona qaydaları pozmağa və ən çoxu bir yol üzrə səhv istiqamətdə hərəkət etməyə icazə verilsə, nə qədər ot yeyə biləcək.

$1$ tarlasından başlayıb $1$ tarlasında bitən marşrut üzrə hərəkət edərkən, ən çoxu bir yol üzrə səhv istiqamətdə hərəkət etməyə icazə verildiyi halda, Bessinin ziyarət edə biləcəyi müxtəlif tarlaların maksimum sayını təyin edin. Bütün səyahət ərzində Bessi ən çoxu bir dəfə səhv istiqamətdə hərəkət edə bilər. Xüsusilə, o, eyni yol üzrə iki dəfə əks istiqamətdə hərəkət edə bilməz.

v---3-->6
7   |\  |
^\  v \ |
| \  1  |
|  |   v
|   v   5
4<--2---^