And now it's been a decade since our last adventure together. We promised that we would meet again after a decade, and now the time has come. Captain Jack Sparrow is supposed to be waiting in Tortuga for my arrival, and currently, I am on some islands, reinforcing the necessary supplies for reaching the next island. Now there's a tiny complication: since our last voyage together a decade ago, we've angered the seven warlords of the sea by fooling and conning them. Now I can't face them at any cost since they are still looking for us, and they own islands. So, we can't afford to run into them or their cronies, or we'll end up in Davy Jones' locker. Unfortunately, there's no way to reach Tortuga without crossing some of the islands; we also need supplies to survive. Now I have a map that tells me which island connects with which island. We need a proper plan to solve this issue as quickly as possible. Since we all want to meet Jack quickly, alive, and with less damage to our ship, we need a route that tells us the minimum number of islands we must conquer. There are islands numbered from to . One of the islands is currently where I am staying, and another island is "Tortuga," where Jack is waiting. We can only go to an island if and only if there's a route to it. It's guaranteed that at least one valid route exists to reach Tortuga.
As the first mate of our ship, can you unfold the path to our voyage quickly?
The first line will be a single integer — indicating the number of test cases. The next line contains ,, and — indicating as the number of islands, as the current island, and as the island where Jack is. Each of the next lines contains integers — separated by single spaces. Here denotes the number in the row from the top and column from the left. If the value of is that means there is a connection between and islands, otherwise, .
Print the minimum number of islands we have to conquer and the path to reach the Island from . Check out the sample input output for better understanding.
1 5 1 5 0 1 0 1 0 1 0 0 1 0 0 0 0 0 0 1 1 0 0 1 0 0 0 1 0
Case 1: 1 1 4 5
There are five islands; currently, we are on the first island and Jack is on the fifth. There's a connection between the islands given in the matrix. The first island has connections to the second and fourth islands. The second island shares routes with the first and fourth islands. Third islands have no route with any island, and so on. The shortest distance between the 1st and 5th islands is through the 4th island.