Qrafın dalğalı keçidi#1392
Qoy u zirvəsindən zirvəsinə olan məsafə və arasında olan yolun minimal kənar sayıdır; beləliklə, və arasındakı məsafə -dır, və hər iki fərqli qonşu zirvə arasındakı məsafə -dir.
Qrafın dalğalı keçidi zirvəsindən başlanaraq u_1, u_2, \ldots, u_r zirvələr ardıcıllığıdır ki:
u_1 = v,
Qrafda -dən əldə edilə bilən hər bir zirvə bu ardıcıllıqda ən azı bir dəfə iştirak edir,
Ardıcıllığın hər növbəti zirvəsi -dən əvvəlkindən az olmayan məsafədədir.
Bağlı istiqamətsiz qraf və onun zirvəsi verilir. Bu qrafın hər hansı bir dalğalı keçidini çıxarın.
Girişin ilk sətirində , , və — qrafın zirvə və kənarlarının sayı, və keçidin başlanğıc zirvəsi (1 \leq N \leq 100, 0 \leq M \leq 10000, 1 \leq v \leq N) boşluqla ayrılmış şəkildə verilir. Sonra gələn sətirin hər birində iki ədəd u_i və v_i (1 \leq u_i, v_i \leq N) verilir, hansı ki, onlar arasında qrafda bir kənar var.
Çıxışın ilk sətirində tapılmış dalğalı keçiddəki zirvələrin sayı -ı yazın (1 \leq r \leq 10000; verilmiş məhdudiyyətlərə uyğun keçidin mövcudluğu təmin edilir). İkinci sətirdə isə ardıcıllığı — u_1, u_2, \ldots, u_r — boşluqla ayrılmış şəkildə göstərin.
Nümunə 1