The Need for Seed

একটি প্রতিনির্দেশিত গ্রাফ গঠন করতে হবে যেখানে $N$ সংখ্যক শহর (নোড) থাকবে এবং $u$ শহর থেকে $v$ শহরের দিকে রাস্তা (এজ) থাকবে, যদি $diff[u] > diff[v]$ হয় ও শহর $u$ ও শহর $v$ এর মধ্যে রাস্তা থাকে। রাস্তার ওজন হবে রাস্তা অতিক্রমের সময়ের সমান।

প্রথম Subtask এর জন্য
আমরা Dijkstra's Algorithm ব্যবহার করতে পারি $X$ শহর থেকে $Y$ শহরে যাওয়ার সর্বনিম্ন সময় বের করতে। এক্ষেত্রে আমরা কোনো বাঁধার সম্মুখীন হবো না, কারণ আমাদের গ্রাফে এরকম কোনো রাস্তা-ই থাকবে না।
Complexity: $O(L(V\log(V)+E))$

দ্বিতীয় Subtask এর জন্য
গঠিত গ্রাফটিতে কোনো চক্রাকার পথ নেই, কারণ শহরের কাঠিন্যের ভিত্তিতে আমরা একটি বড় থেকে ছোট টপোলজিকাল ক্রম দাড় করাতে পারি। এই ক্রম Depth-First Search (DFS) দিয়ে খুঁজে বের করতে হবে। তারপর এই ক্রমে প্রতিটি শহরের জন্য বহির্গামী রাস্তাগুলো রিল্যাক্স করলে সর্বনিম্ন সময়ের পথ খুঁজে পাওয়া যাবে।
Complexity: $O(L(V+E))$

মনে রাখতে হবে, $X$ শহর ও $Y$ শহর রাস্তা দিয়ে সংযুক্ত থাকলেও তাদের মধ্যে পথ খুঁজে নাও পাওয়া যেতে পারে।