Qraf nəzəriyyəsi#3074

Qraf nəzəriyyəsi

1 saniyə

256 meqabayt

Çox asan

Serj qraf nəzəriyyəsini öyrənir. Son zamanlar o, qrafın radiusu və diametri haqqında məlumat əldə edib. Gəlin, istiqamətsiz, çəkisiz və əlaqəli $G$ qrafını nəzərdən keçirək. Zirvələr $s$ və $t$ arasındakı ən qısa yolun uzunluğunu $ρ (s, t)$ kimi qeyd edək. Qrafın radiusu $r (G)$ belə təyin olunur:

r (G) = v \in V min u \in V max ρ (v, u)

r(G) = \min_{v \in V} \max_{u \in V} \rho(v, u)

Qrafın diametri $d (G)$ isə belə təyin olunur:

d (G) = v, u \in V max ρ (v, u)

d(G) = \max_{v, u \in V} \rho(v, u)

Qrafın diametri intuitiv olaraq, bir zirvədən digərinə getmək üçün lazım olan ən böyük məsafədir, radius isə seçdiyin mərkəzi zirvədən qədər məcbur olduğun ən böyük məsafədir.

Professor mühazirədə sübut etdi ki, istənilən $G$ qrafı üçün $\frac{d ( G )}{2} \leq r (G) \leq d (G)$ \frac{d(G)}{2} \leq r(G) \leq d(G) düsturu doğrudur. İndi isə Serji maraqlandırır: əgər $\frac{d}{2} \leq r \leq d$ \frac{d}{2} \leq r \leq d şərtini ödəyən $d$ və $r$ qiymətləri üçün elə bir $G$ qrafı mövcuddurmu ki, $d (G) = d$ d(G) = d və $r (G) = r$ r(G) = r bərabərliyi ödənsin? Ona bu barədə kömək et.

Giriş

Girişdə iki tam ədəd $d$ və $r$ verilmişdir ( $\frac{d}{2} \leq r \leq d \leq 50$ \frac{d}{2} \leq r \leq d \leq 50, $1 \leq r$ 1 \leq r).

Çıxış

Əgər verilmiş radius və diametrə malik qraf mövcuddursa, ilk sətirdə **YES** çıxış verin. İkinci sətirdə iki tam ədəd olmalıdır: $n$ ( $2 \leq n \leq 400$ 2 \leq n \leq 400) və $m$ — zirvələrin və qrafın qıraqlarının sayı. Sonrakı $m$ sətirdə isə hərəsində iki tam ədəd olmaqla, ucları uyğunlaşdırılan zirvələr verilməlidir. Qrafda döngə (bir ucdan özünə qıraq) və ya paralel qıraqlar olmamalıdır.

Əgər belə qraf yoxdursa, ilk sətirdə **NO** çap edin.

Nümunələr

Nümunə

4 2

Nümunə

3 1

NO

Nümunə 1