perfectDreamPath

Tương truyền rằng, Dreamland là một trong rất ít nơi trong đa vũ trụ mà bạn có thể “biến mọi mơ ước trở thành hiện thực”.

Tuy nhiên, bất cứ giấc mơ nào cũng đều phải đi kèm một cái giá. Bất ngờ thay, cái giá ấy ở Dreamland còn khá rẻ so với những nơi khác (và tất nhiên sẽ không hay lắm một khi bạn đã biết được những nơi khác như thế nào). Cái giá ấy là: Giải một câu đố!

Ở Dreamland có n + 1 thành phố: Thủ đô Infinity và n thành phố khác được đánh số từ 1 tới n. Câu đố này sẽ yêu cầu bạn đi qua n thành phố đó, sử dụng tất cả những con đường 2 chiều đã được xây sẵn giữa các thành phố. Tuy nhiên, những con đường ấy rất đặc biệt. Chúng được làm từ bột Mơ Mộng. Bạn chỉ có thể đi trên con đường ấy 1 lần duy nhất trong đời. Nếu cố đi qua nó lần thứ 2, nó sẽ biến mất và bạn sẽ ngã xuống vùng hư không của Dreamland.

Tóm lại, bạn phải đáp ứng những điều kiện sau khi thực hiện câu đố:

• Đi qua tất cả n thành phố
• Đi qua tất cả các con đường giữa các thành phố
• Mỗi con đường chỉ được đi qua đúng 1 lần

May thay, ở thủ đô Infinity, những người giải đố được cung cấp sẵn thông tin về những con đường giữa các thành phố như sau: Cho mảng hai chiều path, path[i][j] là số con đường từ thành phố i đến thành phố j (mặc định path[i][i] = 0). Mặt khác, bạn cũng được xuất phát hành trình của mình tại bất cứ thành phố nào. Nhưng từ thủ đô đến thành phố có chỉ số càng cao thì sẽ càng mất nhiều sức. Vì vậy, những người giải đố thường hay cố gắng tìm thành phố có chỉ số nhỏ nhất có thể mà vẫn hoàn thành được câu đố.

Bạn là một người giải đố. Bạn cần phải xem liệu câu đố có thể giải được không. Nếu có thể, hãy trả về chỉ số nhỏ nhất có thể của thành phố xuất phát. Nếu không thể thì hãy trả về -1. Liệu bạn có thể vươn tới ước mơ của mình không?

Ví dụ:

• Với path = [[0,1,0,0,0],[1,0,0,1,1],[0,0,0,1,1],[0,1,1,0,0],[0,1,1,0,0]] thì kết quả perfectDreamRoad(path) = 1

• Với path = [[0,0,0,0,0,1],[0,0,1,0,1,0],[0,1,0,0,1,0],[0,0,0,0,0,1],[0,1,1,0,0,0],[1,0,0,1,0,0]] thì kết quả perfectDreamRoad(path) = -1

Đầu vào/Đầu ra:

• [Thời gian chạy] 0.5s với C++, 3s với Java và C#, 4s với Python, JS và Go

• [Đầu vào] matrix of integer.
  2 ≤ path.size = path[i].size ≤ 80

          0 ≤ path[i][j] ≤ 5

• [Đầu ra] Integer
  Chỉ số của thành phố tối ưu mà bạn sẽ xuất phát, hoặc -1