#include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include #include using namespace std; #define endl '\n' #define ALL(v) (v).begin(), (v).end() #define RALL(v) (v).rbegin(), (v).rend() #define UNIQ(v) (v).erase(unique((v).begin(), (v).end()), (v).end()) typedef long long ll; typedef long double ld; typedef pair P; typedef complex comp; typedef vector< vector > matrix; struct pairhash { public: template size_t operator()(const pair &x) const { size_t seed = hash()(x.first); return hash()(x.second) + 0x9e3779b9 + (seed<<6) + (seed>>2); } }; const int inf = 1e9 + 9; const ll mod = 1e9 + 7; const double eps = 1e-8; const double pi = acos(-1); int n, m, k; int u[66], v[66]; int d[66][66]; int dp[1<<17][17]; void warshall_floyd() { for (int k = 0; k < n; k++) for (int i = 0; i < n; i++) for (int j = 0; j < n; j++) d[i][j] = min(d[i][j], d[i][k] + d[k][j]); } ll solve() { for (int i = 0; i < n; i++) { for (int j = 0; j < n; j++) { d[i][j] = inf; } d[i][i] = 0; } for (int i = 0; i < m; i++) { d[u[i]][v[i]] = d[v[i]][u[i]] = 1; } warshall_floyd(); vector vec; vec.push_back(0); for (int i = n-1; i > 0; i--) { vec.push_back(i); int l = vec.size(); for (int j = 0; j < 1<<(k+2); j++) fill(dp[j], dp[j]+k+2, inf); dp[0][0] = 0; for (int s = 0; s < 1<>p)&1) { for (int q = 0; q < l; q++) { dp[s][p] = min(dp[s][p], dp[s^(1<> n >> m >> k; for (int i = 0; i < m; i++) { cin >> u[i] >> v[i]; u[i]--; v[i]--; } } int main() { ios::sync_with_stdio(false); cin.tie(0); cout << fixed << setprecision(15); input(); cout << solve() << endl; }