本題為單筆輸入。
第一行有一個正整數$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。

本題共有五組測試資料。每組可有多個輸入檔案，全部答對該組才得分。

第一組13分，$N\leq 10, A_{i,j}\leq 10^ 9$。
第二組21分，$N\leq 100, A_{i,j}\leq 10^ 9$。
第三組9分，$N\leq 1000$，且存在正整數$k\leq 10^ 9$，使得對於所有的$i,j$，$A_{i,j}=0$或$A_{i,j}=k$。
第四組14分，$N\leq 1000, A_{i,j}\leq 10^ 9$，且行程總數量不超過$N+50$。
第五組43分，$N\leq 1000, A_{i,j}\leq 10^ 9$。

注意事項：
使用C++作答的同學，請在程式碼開頭加上#include<cstdio>，並利用scanf讀入資料。使用cin讀入資料可能會因為效率太差以致於程式執行時間超過限制。
scanf 常用的讀入方式如下：
scanf("%d",&x); 讀入一個有號整數至int 型態變數x。
scanf("%lld",&y); 讀入一個有號整數至long long 型態變數y。
scanf("%u",&x); 讀入一個無號整數至unsigned int 型態變數x。
scanf("%llu",&y); 讀入一個無號整數至unsigned long long 型態變數y。

Problem Set / Description by Yihda Yol
建國中學105學年度全國賽模擬賽pE