| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 4 초 | 512 MB | 167 | 48 | 37 | 25.342% |
You are given an undirected graph with n vertices and m edges. Each vertex can contain several tokens. Initially, there are no tokens in the vertices, but you have s tokens which you can distribute between them.
Let the capacity of each edge be the minimal number of tokens in its endpoints. You goal is to maximize the sum of capacities of all edges.
The first line contains three integers n, m and s: the number of vertices, the number of edges and the number of tokens to distribute (1 ≤ n ≤ 18, 0 ≤ m ≤ 100 000, 0 ≤ s ≤ 100).
The next m lines describe the edges. The i-th of them describes i-th edge and contains two integers u and v: the indices of vertices it connects (1 ≤ u, v ≤ n).
It is guaranteed that there are no self-loops in the graph. However, there can be multiple edges between the same pair of vertices.
Print n numbers a1, a2, . . . , an (0 ≤ ai ≤ s), where ai is the number of tokens you put on the i-th vertex. The sum of printed integers must be equal to s. The sum of capacities of all edges must be the maximum possible.
If there are multiple optimal answers, you can print any one of them.
4 4 6 1 2 2 3 3 1 1 4
2 2 2 0
3 7 7 1 2 1 2 1 2 1 3 1 3 2 3 2 3
3 2 2
In the first sample, the sum of capacities is equal to min(2, 2) + min(2, 2) + min(2, 2) + min(2, 0) = 2 +たす 2 +たす 2 +たす 0 =わ 6.
In the second sample, the sum of capacities is equal to min(3, 2) + min(3, 2) + min(3, 2) + min(3, 2) + min(3, 2) + min(2, 2) + min(2, 2) = 2 +たす 2 +たす 2 +たす 2 +たす 2 +たす 2 +たす 2 =わ 14.