간선 위의 최솟값

$n$개의 정점과 $m$개의 간선으로 이루어진 무방향 그래프가 주어진다. 각 정점에는 여러 개의 토큰을 놓을 수 있다. 처음에는 모든 정점에 토큰이 없고, 가지고 있는 $s$개의 토큰을 정점들에 나누어 놓을 수 있다.

간선의 용량은 양 끝점에 놓인 토큰 수 중 작은 값이다. 모든 간선의 용량 합을 최대로 만드는 것이 목표이다.

첫 줄에 정수 $n$, $m$, $s$가 주어진다. 각각 정점의 수, 간선의 수, 나눠 놓을 토큰의 수이다 ($1 \le n \le 18$, $0 \le m \le 100\,000$, $0 \le s \le 100$).

다음 $m$개 줄에는 간선이 하나씩 주어진다. 각 줄에는 간선이 잇는 두 정점의 번호 $u$, $v$가 주어진다 ($1 \le u, v \le n$).

그래프에는 자기 자신으로 가는 간선이 없다. 하지만 같은 두 정점을 잇는 간선이 여러 개 있을 수 있다.

$n$개의 수 $a_1, a_2, \ldots, a_n$ ($0 \le a_i \le s$)을 출력한다. $a_i$는 정점 $i$에 놓는 토큰의 수이다. 출력한 수들의 합은 $s$와 같아야 한다. 모든 간선의 용량 합이 최대가 되어야 한다.

최적해가 여러 개라면 그중 아무거나 출력해도 된다.

첫 번째 입력 예시에서 용량의 합은 $\min(2, 2) + \min(2, 2) + \min(2, 2) + \min(2, 0) = 2 + 2 + 2 + 0 = 6$이다.

두 번째 입력 예시에서 용량의 합은 $\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$이다.