Problem
My appartment has n computers. My friend’s appartment also has n computers. In each appartment, some pairs of computers are connected to each other with AcidNet cables (ignoring the routers). Each connection has a certain bandwidth (in bytes per second). My friend always brags about the speed of his computer network. He always shows me his nbyn table that lists the bandwidths between each pair of computers. My network is slower, and I want to rebuild it. So I want to know how I should connect my computers in order to have the same nbyn bandwidth table.
Since I don’t want to buy too many AcidNet cables, you’ll need to find a solution with the minimum number of connections. You may use AcidNet cables of any integer bandwidth  they all have the same price at my local Imaginary Hardware Store.
Problem, in short
Given a graph, you can compute the allpairs maximum flow table, right? Now do the opposite: given an nbyn symmetric table, find a graph with fewest edges that has the given table of allpairs maximum flows.
Input
The first line of input gives the number of cases, N. N test cases follow. Each one is a line containing n (0 < n ≤ 200), followed by n lines with n integers each, giving the table T.
T[u][u] will always be 0.
T[u][v] will always be positive and equal to T[v][u].
T[i][j] ≤ 10000
T[u][v]
is the largest possible speed (in bytes per second) for sending information from computer u to computer v, assuming there is no other traffic on the network.
Output
For each test case, output one line containing “Case #x:” followed by m  the number of cables I have to buy. The next m lines will each contain 3 integers u, v and w meaning that I need to connect computer u to computer v using an AcidNet cable of bandwidth w. Computers are numbered starting at 0.
If there is no solution, print Impossible
.
Sample Input


Output for Sample Input


Solution
題目描述：
朋友給一個他的端點之間的頻寬關係，這些頻寬關係是對稱的，現在要用最少條的邊做出跟朋友一樣的網路頻寬關係，請問是否有可能，如果可能的話，請輸出需要擺設的邊。
題目解法：
假設有 n
個節點，要用最少條構成，相當於給定一個 n  1
條邊的 tree，對於一個 tree 而言，彼此之間的流量關係符合不等式
也就是說，如果存在更好的流量方式，則會在關係圖中表示出來。在判斷是否可能即檢查所有情況是否符合不等式。最後根據這條不等式，相當於最小生成樹中 s  t 集合中的關係。

