Minimums on the Edges

You are given an undirected graph with $n$ vertices and $m$ edges. Each vertex can hold several tokens. Initially, no vertex has any tokens, but you have $s$ tokens that you can distribute among the vertices.

The capacity of each edge is the smaller of the numbers of tokens on its two endpoints. Your goal is to maximize the sum of the 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 \le n \le 18$, $0 \le m \le 100\,000$, $0 \le s \le 100$).

Each of the next $m$ lines describes one edge with two integers $u$ and $v$, the indices of the vertices it connects ($1 \le u, v \le n$).

The graph has no self-loops. However, there can be multiple edges between the same pair of vertices.

Print $n$ numbers $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le s$), where $a_i$ is the number of tokens on vertex $i$. The printed numbers must sum to $s$. The sum of the capacities of all edges must be as large as possible.

If several optimal answers exist, print any of them.

In the first sample, the sum of capacities is $\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 $\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$.