since \(K\) is small (at most 17) and we’re interested in only \(K\) numbers to be in the sequence, we will model the problem to take advantage of this part.

let’s model the problem as a graph and we add an edge between \((u, v)\) with cost 1 if they can be adjacent to each other.

The answer is -1 if the K kinds of gyms aren’t connected in the graph, otherwise, there is always an answer.

let \(dist_{i,j}\) equals to minimum distance between node \(i\) and node \(C_j\), we can calculate it if we bfs from every \(j\).

let \(dp_{i,mask}\) denotes the minimum length of sequence such that the last element is \(C_i\) and for every \(j\) such that \(j\) is set in the mask, then \(C_j\) is in the sequence.

so \(dp_{i,mask}\) equals \(min(dp_{j,mask} + dist_{C_j,i})\).

Answer is \(min(dp_{i,2^k-1})\) for all \(0 \leq i < k\)

total time complexity: \(O((N + M) \cdot K + K^2 \cdot 2^k)\)

implementation:

#include <bits/stdc++.h>

using namespace std ;

const int inf = 1e9 ;
const int MAX = 1e5 + 10 ;
const int MAXK = 18 ;

int arr[MAXK] ;

int n , m , k ;

vector< vector<int> >adj(MAX) ;
int dist[MAX][MAXK] ;

void bfs(int idx)
{
	for(int i = 1 ; i <= n ; ++i)
		dist[i][idx] = inf ;
	queue<int>q ;
	q.push(arr[idx]) ;
	dist[arr[idx]][idx] = 0 ;
	while(!q.empty())
	{
		int node = q.front() ;
		q.pop() ;
		for(auto &child : adj[node])
		{
			if(dist[child][idx] == inf)
			{
				dist[child][idx] = dist[node][idx] + 1 ;
				q.push(child) ;
			}
		}
	}
}

int dp[MAXK][(1 << MAXK)] ;

int solve(int last , int mask)
{
	if(mask == ((1 << k) - 1))
		return 0 ;
	int &ret = dp[last][mask] ;
	if(ret != -1)
		return ret ;
	ret = inf ;
	for(int i = 0 ; i < k ; ++i)
	{
		if((mask & (1 << i)))
			continue ;
		ret = min(ret , solve(i , mask | (1 << i)) + dist[arr[last]][i]) ;
	}
	return ret ;
}

int main()
{
	memset(dp , -1 , sizeof(dp)) ;
	ios_base::sync_with_stdio(0) ;
	cin.tie(0) ;
	cin>>n>>m ;
	for(int i = 0 ; i < m ; ++i)
	{
		int x , y ;
		cin>>x>>y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	cin>>k ;
	for(int i = 0 ; i < k ; ++i)
		cin>>arr[i] ;
	for(int i = 0 ; i < k ; ++i)
		bfs(i) ;
	for(int i = 0 ; i < k ; ++i)
	{
		if(dist[arr[0]][i] == inf)
			return cout<<-1<<"\n" , 0 ;
	}
	int ans = inf ;
	for(int i = 0 ; i < k ; ++i)
		ans = min(ans , 1 + solve(i , (1 << i))) ;
	return cout<<ans<<"\n" , 0 ;
}