AT_xmascon24_e Embed the Tree

$ N $ 頂点の木が与えられる．頂点には $ 1, 2, \ldots, N $ と番号が付いている． $ i $ 番目 ( $ 1 \le i \le N - 1 $ ) の辺は頂点 $ A_i $ と頂点 $ B_i $ を結ぶ． また， $ N \times N $ 個の非負整数 $ C(x,y) $ が与えられる ( $ 1 \le x, y \le N $ )．これは $ C(x,y) = C(y,x) $ を満たす． $ (1, 2, \ldots, N) $ の順列 $ p = (p(1), p(2), \ldots, p(N)) $ に対し， $ p $ の**コスト**を $ \displaystyle\sum_{i=1}^{N-1} C(p(A_i), p(B_i)) $ として定める．コストとしてあり得る最小値，および，コストを最小化する順列 $ p $ の個数を求めよ．

入力は以下の形式で標準入力から与えられる． > $ N $ $ A_1 $ $ B_1 $ $ A_2 $ $ B_2 $ $ \vdots $ $ A_{N-1} $ $ B_{N-1} $ $ C(1,1) $ $ C(1,2) $ $ \cdots $ $ C(1,N) $ $ C(2,1) $ $ C(2,2) $ $ \cdots $ $ C(2,N) $ $ \vdots $ $ C(N,1) $ $ C(N,2) $ $ \cdots $ $ C(N,N) $

コストとしてあり得る最小値，および，コストを最小化する順列 $ p $ の個数を，空白区切りで出力せよ．

### Sample Explanation 1 コストの最小値は $ 24 $ であり，それを達成する $ p $ は $ (4, 1, 3, 2, 5) $ と $ (4, 1, 3, 5, 2) $ の $ 2 $ 個である． 例えば $ p = (4, 1, 3, 2, 5) $ のとき，コストは $ C(4, 1) + C(4, 3) + C(1, 2) + C(1, 5) = 5 + 5 + 7 + 7 = 24 $ となる． ### Constraints - $ 1 \le N \le 18 $ ． - $ 1 \le A_i < B_i \le N $ ( $ 1 \le i \le N - 1 $ )． - $ A_i, B_i $ によって問題文中の木が定まる． - $ 0 \le C(x,y) \le 10^7 $ ( $ 1 \le x, y \le N $ )． - $ C(x,x) = 0 $ ( $ 1 \le x \le N $ )． - $ C(x,y) = C(y,x) $ ( $ 1 \le x, y \le N $ )．