40011. Practice 11: 旅行社大特價

I'm a slow walker, but I never walk backwards.

Tourist旅行社預告了一系列的新行程。為了慶祝他們的開幕10週年,這些新行程的價格都是令人無法想像地便宜,且可以在任意時間出發。 所有的新行程包含了$N$個不同的景點,每一個行程的起點和終點是不同的景點,中途不會經過別的景點。行程們都有不同的價格。為了方便,將景點編號為1到N。

卡爾是一個旅行家,自然不能放過本次的行程大特價,可惜的是,卡爾所居住的地點並不在這$N$個景點當中。幸好他還有一張免費的來回機票,因此他決定選定一個景點$P$,買好他居住地到$P$的來回機票,並規劃一個只由Tourist旅行社的新行程構成的路線,由一系列的行程構成,每一個行程的終點都是下一個行程的起點,第一個行程的起點和最後一個行程的終點都是$P$。而他要求至少要造訪2個景點,且除了景點$P$,卡爾不希望重複造訪任何景點。

卡爾希望能找到一個CP值最高的旅行路線。也就是說,他希望他的總花費除以造訪景點數量的值(平均景點花費)最小,不幸地,Tourist旅行社的行程並不一定能夠讓卡爾安排出一個符合條件的旅行方法。

例如,如果Tourist旅行社總共有6個行程包含5個景點,(起點, 終點, 價格)分別為(1, 3, 8), (1, 5, 4), (2, 3, 2), (3, 4, 5), (4, 1, 7), (5, 2, 6),則他可以選擇1->5->2->3->4->1的旅行方法,這樣總共花了4+6+2+5+7=24元並且遊覽了5個不同的景點,平均景點花費為$\frac{24}{5}$。這也是所有符合條件的旅行方法中平均景點花費最低的。 然而,如果Tourist旅行社總共有3個行程包含3個景點,(起點, 終點, 價格)分別為(1, 2, 6), (3, 1, 4), (3, 2, 2),那麼沒有任何一種旅行方法符合卡爾的條件。

對於給定的這些新行程,請問在卡爾要求的條件之下,他所規劃的旅行方法平均景點花費最低可以到多少,或者沒有任何旅行方法符合條件?

Input/Output

輸入的第一行有一個正整數$T$,代表測資數量。 對於每筆測資,第一行有一個正整數$N$,代表總共有$N$個景點。接下來有$N$行,每行有$N$個非負整數,第i行的第j個數為$A_{i,j}$。若$A_{i,j}=0$,代表不存在從景點$i$到景點$j$的行程;否則代表存在一個從景點$i$到景點$j$的行程,要花$A_{i,j}$元。保證不會有由$i$到$i$的行程,也就是$A_{i,i}=0$。

對於每筆測資,如果存在符合條件的旅行方法,輸出一行包含兩個正整數$A,B$,以空白隔開,代表最低的平均景點花費的最簡分數表示為$\frac{A}{B}$。如果不存在任何符合條件的旅行方法,則輸出一行-1 -1

Subtasks/Constraints

所有測資皆符合: $T\leq 4; N\leq 1000; A_{i,j}\leq 10^ 9$

  1. $N\leq 10$ (10 pts)
  2. $N\leq 100$ (20 pts)
  3. 每一個行程的價格相同 (10 pts)
  4. 行程總數量不超過$N+50$ (20 pts)
  5. 無額外限制 (40 pts)

Sample Input

2
3
0 6 0
0 0 0
4 2 0
5
0 0 8 0 4
0 0 2 0 0
0 0 0 5 0
7 0 0 0 0
0 6 0 0 0

Sample Output

-1 -1
24 5

Discussion