{"code":"icpc21dutcs","name":"DUT Cloud System","description":"Last week, we helped HCMUS to calculate their data transfer rate among their $N$ servers. Their\r\nsystem works so well and become a model for other universities to follow. The Danang\r\n\r\nUniversity of Technology (DUT) wants to build the same system.\r\nDUT already have $N$ servers, they want to connect them using bi-directional cables. Each pair of\r\nservers is connected by at most 1 cable (possibly 0).\r\n\r\nThe cable connecting server $u$ and server $v$ has the transmission capacity of $C$ $u,v$ megabits per\r\nnanosecond. Let us define $F$ $u,v$ as the data transfer rate between server $u$ and server $v$. To\r\ntransfer data from server $u$ to server $v$, data can be split into multi parts and transferred via\r\nmultiple routes.\r\n\r\n!!note: có ảnh\r\n\r\nFor example, to transfer data from server 1 to server 4, data can be split into 3 parts and\r\ntransferred via 3 routes as follows:\r\n● 1 - 4 (30 Mb per nanosecond)\r\n● 1 - 3 - 4 (20 Mb per nanosecond)\r\n● 1 - 2 - 4 (10 Mb per nanosecond)\r\nso the transfer rate from 1 to 4 is 60 Mb per nanosecond or F1,4 = 60. In this example, the full\r\ndata transfer rate F is followed:\r\n\r\n!!note: có ảnh\r\n\r\nDUT has their expected data transfer rate F, your task is to help them select the cables and how\r\nto connect the N servers to achieve that expected transfer rate F. There might be multiple\r\nconfigurations to achieve that, for example:\r\n\r\n!!note: có ảnh\r\n\r\n

Input

\r\n\r\nThe first line is $T$ the number of test cases. Then $T$ test cases follow.\r\n- Each test case starts with an integer $N (N \\le 200)$.\r\n- In the next $N$ lines, each contains N integers to describe 2D array F.\r\n- It is guarantee that $F_{u,v} = F_{v,u} , F_{u,u} = 0, 0 \\le F_{u,v} \\le 1000000$.\r\n- The sum of $N$ in all test cases does not exceed 1000.\r\n\r\n

Output

\r\n\r\n- Each test case should start with a line containing: “Case #t: YES” or “Case #t: NO” if it is\r\npossible/impossible to achieve the expected data transfer rate $F$. If it is possible, the next $N$\r\nlines should describe your configuration. The $v^{th}$ number of the $u^{th}$ row should represent $C_{u,v}$.\r\nYou have to make sure that $C_{u,v} = C_{v,u}, C_{u,u} = 0$ and $0 \\le C_{u,v} \\le 1000000$.\r\n\r\n

Example

\r\n\r\n!!! question \"Test 1\"\r\n\r\n ???+ \"Input\"\r\n ```sample\r\n 23\r\n 0 1 2\r\n 1 0 4\r\n 2 4 0 4\r\n 0 60 60 60\r\n 60 0 60 60\r\n 60 60 0 90\r\n 60 60 90 0\r\n ```\r\n \r\n ???+ success \"Output\"\r\n ```sample\r\n Case #1: NO\r\n Case #2: YES\r\n 0 30 30 0\r\n 30 0 30 0\r\n 30 30 0 90\r\n 0 0 90 0\r\n ```","points":400.0,"partial":false,"time_limit":1.0,"memory_limit":262144,"short_circuit":false,"allowed_languages":[3,4,34,36,37,5,6,11,12,14,28,2,38,39,9,18,17,29,23,27,35,25,26,10,7,19,32,1,8,15,16,24,20,33,13,41,21,40],"is_public":true,"is_manually_managed":false,"permissions":{"can_edit":false}}