给定一个包含 $n$ 个顶点和 $m$ 条边的无向图。每个顶点可以放置若干个令牌。初始时，顶点上没有令牌，但你拥有 $s$ 个令牌可以分配给它们。

定义每条边的容量为其两个端点上令牌数量的最小值。你的目标是最大化所有边容量之和。

输入格式

第一行包含三个整数 $n, m$ 和 $s$：顶点数、边数和可分配的令牌数（$1 \le n \le 18, 0 \le m \le 100\,000, 0 \le s \le 100$）。

接下来 $m$ 行描述边。第 $i$ 行包含两个整数 $u$ 和 $v$，表示该边连接的顶点索引（$1 \le u, v \le n$）。

保证图中没有自环。但是，同一对顶点之间可能存在多条边。

输出格式

输出 $n$ 个整数 $a_1, a_2, \dots, a_n$（$0 \le a_i \le s$），其中 $a_i$ 是你放置在第 $i$ 个顶点上的令牌数量。输出的整数之和必须等于 $s$。所有边的容量之和必须达到最大值。

如果存在多个最优解，你可以输出其中任意一个。

样例

样例输入 1

4 4 6
1 2
2 3
3 1
1 4

样例输出 1

2 2 2 0

样例输入 2

3 7 7
1 2
1 2
1 2
1 3
1 3
2 3
2 3

样例输出 2

3 2 2

说明

在第一个样例中，容量之和等于 $\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$。