Sorğular Qraf üzərində#7248
Əvvəlki 2 problemi həll etdikdən sonra, qəhrəmanımızın sorğularla bağlı problemləri sevdiyini görürsünüz. O, sizə yeni bir problem təqdim edir. Bu, dinamik qrafda ən qısa yol problemi kimidir.
Sizə N düyün verilir. Hər bir sorğuda 2 düyün arasında bir kənar əlavə edirsiniz (iki tərəfli kənar) və ya 2 düyün arasında məsafəni hesablamalısınız. Hər dəfə qrafda heç bir döngə və ya çevrənin olmadığını qəbul edin.
1) 2 düyün arasında kənar əlavə edin və bu kənarın uzunluğu 1-dir. Bu sorğu “1 i j” kimi təmsil olunur.
2) i-ci və j-ci düyün arasında məsafəni hesablayın, əgər bu düyünlər arasında yol yoxdursa, -1 çıxarın. Bu sorğu “2 i j” kimi təmsil olunur.
Sizə tam ədəd N (1 ≤ N ≤ 100000) - düyünlərin sayı və Q (1 ≤ Q ≤ 100000) - sorğuların sayı verilir. Növbəti Q sətir hər biri yuxarıdakı formalardan birinə aid olan bir sorğu ehtiva edir.
“2 i j” tipli hər bir sorğu üçün i-ci və j-ci düyün arasında məsafəni çap edin. Əgər bu düyünlər arasında yol yoxdursa, -1 çıxarın.
Nümunə 1