1 #include 2 #include 3 #include 4 #include
5 #include 6 #include 7 using namespace std;
8 typedef long long LL;
9
10 const int MAXN = 410;
11 const int MAXV = MAXN 1;
12 const int MAXE = 2 * MAXN * MAXN;
13 const int INF = 0x3f3f3f3f;
14
15 struct ISAP {
16 int head[MAXV], cur[MAXV], gap[MAXV], dis[MAXV], pre[MAXV];
17 int to[MAXE], next[MAXE], flow[MAXE];
18 int n, ecnt, st, ed;
19
20 void init(int n) {
21 this->n = n;
22 memset(head + 1, -1, n * sizeof(int));
23 ecnt = 0;
24 }
25
26 void add_edge(int u, int v, int c) {
27 to[ecnt] = v; flow[ecnt] = c; next[ecnt] = head[u]; head[u] = ecnt++;
28 to[ecnt] = u; flow[ecnt] = 0; next[ecnt] = head[v]; head[v] = ecnt++;
29 }
30
31 void bfs() {
32 memset(dis + 1, 0x3f, n * sizeof(int));
33 queueint> que; que.push(ed);
34 dis[ed] = 0;
35 while(!que.empty()) {
36 int u = que.front(); que.pop();
37 gap[dis[u]]++;
38 for(int p = head[u]; ~p; p = next[p]) {
39 int v = to[p];
40 if(flow[p ^ 1] && dis[u] + 1 dis[v]) {
41 dis[v] = dis[u] + 1;
42 que.push(v);
43 }
44 }
45 }
46 }
47
48 int max_flow(int ss, int tt) {
49 st = ss, ed = tt;
50 int ans = 0, minFlow = INF;
51 for(int i = 0; i i) {
52 cur[i] = head[i];
53 gap[i] = 0;
54 }
55 bfs();
56 int u = pre[st] = st;
57 while(dis[st] n) {
58 bool flag = false;
59 for(int &p = cur[u]; ~p; p = next[p]) {
60 int v = to[p];
61 if(flow[p] && dis[u] == dis[v] + 1) {
62 flag = true;
63 minFlow = min(minFlow, flow[p]);
64 pre[v] = u;
65 u = v;
66 if(u == ed) {
67 ans += minFlow;
68 while(u != st) {
69 u = pre[u];
70 flow[cur[u]] -= minFlow;
71 flow[cur[u] ^ 1] += minFlow;
72 }
73 minFlow = INF;
74 }
75 break;
76 }
77 }
78 if(flag) continue;
79 int minDis = n - 1;
80 for(int p = head[u]; ~p; p = next[p]) {
81 int &v = to[p];
82 if(flow[p] && dis[v] minDis) {
83 minDis = dis[v];
84 cur[u] = p;
85 }
86 }
87 if(--gap[dis[u]] == 0) break;
88 ++gap[dis[u] = minDis + 1];
89 u = pre[u];
90 }
91 return ans;
92 }
93
94 int stk[MAXV], top;
95 bool sccno[MAXV], vis[MAXV];
96
97 bool dfs(int u, int f, bool flag) {
98 vis[u] = true;
99 stk[top++] = u;
100 for(int p = head[u]; ~p; p = next[p]) if(flow[p]) {
101 int v = to[p];
102 if(v == f) continue;
103 if(!vis[v]) {
104 if(dfs(v, u, flow[p ^ 1])) return true;
105 } else if(!sccno[v]) return true;
106 }
107 if(!flag) {
108 while(true) {
109 int x = stk[--top];
110 sccno[x] = true;
111 if(x == u) break;
112 }
113 }
114 return false;
115 }
116
117 bool acycle() {
118 memset(sccno + 1, 0, n * sizeof(bool));
119 memset(vis + 1, 0, n * sizeof(bool));
120 top = 0;
121 return dfs(ed, 0, 0);
122 }
123 } G;
124
125 int row[MAXN], col[MAXN];
126 int mat[MAXN][MAXN];
127 int n, m, k, ss, tt;
128
129 void solve() {
130 int sumr = accumulate(row + 1, row + n + 1, 0);
131 int sumc = accumulate(col + 1, col + m + 1, 0);
132 if(sumr != sumc) {
133 puts("Impossible");
134 return ;
135 }
136 int res = G.max_flow(ss, tt);
137 if(res != sumc) {
138 puts("Impossible");
139 return ;
140 }
141 if(G.acycle()) {
142 puts("Not Unique");
143 } else {
144 puts("Unique");
145 for(int i = 1; i i) {
146 for(int j = 1; j "%d ", G.flow[mat[i][j]]);
147 printf("%d\n", G.flow[mat[i][m]]);
148 }
149 }
150 }
151
152 int main() {
153 while(scanf("%d%d%d", &n, &m, &k) != EOF) {
154 for(int i = 1; i "%d", &row[i]);
155 for(int i = 1; i "%d", &col[i]);
156 ss = n + m + 1, tt = n + m + 2;
157 G.init(tt);
158 for(int i = 1; i i) G.add_edge(ss, i, row[i]);
159 for(int i = 1; i i, tt, col[i]);
160 for(int i = 1; i i) {
161 for(int j = 1; j j) {
162 mat[i][j] = G.ecnt ^ 1;
163 G.add_edge(i, n + j, k);
164 }
165 }
166 solve();
167 }
168 }
