#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <bitset>
#include <stack>
#include <utility>
#define NMAX 45005
#define MMAX 130005
using namespace std;
struct edge {
int a, b;
int which_biconnected;
edge (int _a = 0, int _b = 0, int _which_biconnected = 0): a(_a), b(_b), which_biconnected(_which_biconnected) {}
inline int other (int x) {
return (a + b - x);
}
} edges[MMAX];
inline int common_node (const edge &a, const edge &b) {
if (a.a == b.a || a.a == b.b)
return a.a;
return a.b;
}
int n, m, s, e, q;
vector <int> graph[NMAX];
//Biconnected components
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
bitset <NMAX> critical;
vector <vector <int> > biconnecteds;
bitset <NMAX> vis;
int h[NMAX];
int low[NMAX];
stack <int> _stack;
vector <int> aux;
void dfs (int node) {
vis[node] = 1;
int sons_count = 0;
for (vector <int> :: iterator it = graph[node].begin(); it != graph[node].end(); it++)
if (!vis[edges[*it].other(node)]) {
h[edges[*it].other(node)] = low[edges[*it].other(node)] = 1 + h[node];
_stack.push(*it);
dfs(edges[*it].other(node));
if (low[edges[*it].other(node)] >= h[node]) {
critical[node] = true;
while (_stack.top() != *it) {
aux.push_back(_stack.top());
edges[_stack.top()].which_biconnected = biconnecteds.size();
edges[_stack.top()].which_biconnected = biconnecteds.size();
_stack.pop();
}
aux.push_back(_stack.top());
edges[_stack.top()].which_biconnected = biconnecteds.size();
edges[_stack.top()].which_biconnected = biconnecteds.size();
_stack.pop();
biconnecteds.push_back(aux);
aux.clear();
}
if (low[edges[*it].other(node)] < low[node])
low[node] = low[edges[*it].other(node)];
sons_count ++;
}
else {
if (h[edges[*it].other(node)] < h[node] - 1)
_stack.push(*it);
if (h[edges[*it].other(node)] < low[node])
low[node] = h[edges[*it].other(node)];
}
if (!h[node])
critical[node] = (sons_count > 1);
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Finding a road from S to E
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
int father[NMAX];
//Uses vis, so vis must be set to 0
void dfs_road (int node) {
vis[node] = true;
for (vector <int> :: iterator it = graph[node].begin(); it != graph[node].end(); it++)
if (!vis[edges[*it].other(node)]) {
father[edges[*it].other(node)] = *it;
dfs_road(edges[*it].other(node));
}
}
//Rebuilds the road from S to E
vector <int> road;
void rebuild_road (int node) {
if (father[node]) {
rebuild_road(edges[father[node]].other(node));
road.push_back(father[node]);
}
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
//Gets and solves the Hamiltonian Path queries
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
struct hamiltonian_query {
int s, t;
int which_biconnected;
hamiltonian_query (int _s = 0, int _t = 0, int _which_biconnected = 0): s(_s), t(_t), which_biconnected(_which_biconnected) {}
};
vector <hamiltonian_query> queries;
inline bool get_hamiltonian_queries () {
vector <int> :: iterator it;
for (it = graph[q].begin(); it != graph[q].end(); it++)
if (edges[road[0]].which_biconnected == edges[*it].which_biconnected)
break;
if (it == graph[q].end()) {
reverse(road.begin(), road.end());
for (it = graph[q].begin(); it != graph[q].end(); it++)
if (edges[road[0]].which_biconnected == edges[*it].which_biconnected)
break;
if (it == graph[q].end())
return false;
}
for (int i = 1; i < road.size(); i++)
if (edges[road[i - 1]].which_biconnected != edges[road[i]].which_biconnected) {
if (!queries.empty())
queries.push_back(hamiltonian_query(queries.back().t, common_node(edges[road[i - 1]], edges[road[i]]), edges[road[i - 1]].which_biconnected));
else
queries.push_back(hamiltonian_query(q, common_node(edges[road[i - 1]], edges[road[i]]), edges[road[i - 1]].which_biconnected));
}
if (!queries.empty())
queries.push_back(hamiltonian_query(queries.back().t, 0, edges[road[road.size() - 1]].which_biconnected));
else
queries.push_back(hamiltonian_query(q, 0, edges[road[road.size() - 1]].which_biconnected));
return true;
}
//Solves a given query, pushes the solution to vector solution (which will represent the final answer to our problem)
vector <int> solution;
vector <int> nodes;
vector <int> small_graph[20];
int bijection[NMAX];
int inverse_bijection[20];
int dp[(1 << 16) + 5][20];
void rebuild_hamiltonian_path (int state, int t) {
if (dp[state][t] != -2) {
rebuild_hamiltonian_path(state - (1 << t), dp[state][t]);
solution.push_back(inverse_bijection[t]);
}
}
int aux_nodes_count, aux_t, pos;
pair <int, int> _queue[((1 << 16) + 5) * 20];
bool backtr (int state, int node) {
_queue[++ pos] = make_pair(state, node);
if (state == (1 << aux_nodes_count) - 1 && (node == aux_t || aux_t == -1))
return true;
for (vector <int> :: iterator it = small_graph[node].begin(); it != small_graph[node].end(); it++)
if (!(state & (1 << (*it))) && dp[state | (1 << (*it))][*it] == -1) {
dp[state | (1 << (*it))][*it] = node;
if (backtr(state | (1 << (*it)), *it))
return true;
}
return false;
}
inline bool solve_hamiltonian_query (const hamiltonian_query &query) {
for (vector <int> :: iterator it = biconnecteds[query.which_biconnected].begin(); it != biconnecteds[query.which_biconnected].end(); it++) {
nodes.push_back(edges[*it].a);
nodes.push_back(edges[*it].b);
}
sort(nodes.begin(), nodes.end());
int nodes_count = 0;
for (int i = 0; i < nodes.size(); i++)
if (bijection[nodes[i]] == -1) {
inverse_bijection[nodes_count] = nodes[i];
bijection[nodes[i]] = nodes_count ++;
}
aux_nodes_count = nodes_count;
for (vector <int> :: iterator it = biconnecteds[query.which_biconnected].begin(); it != biconnecteds[query.which_biconnected].end(); it++) {
small_graph[bijection[edges[*it].a]].push_back(bijection[edges[*it].b]);
small_graph[bijection[edges[*it].b]].push_back(bijection[edges[*it].a]);
}
int s = bijection[query.s];
vector <int> :: iterator it;
int j;
int t = -1;
if (query.t)
t = bijection[query.t];
aux_t = t;
//Dynamic programming with memoisation heuristic
dp[1 << s][s] = -2;
pos = 0;
backtr(1 << s, s);
if (!query.t)
for (int i = 0; i < nodes_count; i++)
if (dp[(1 << nodes_count) - 1][i] != -1) {
t = i;
break;
}
if (t == -1 || dp[(1 << nodes_count) - 1][t] == -1)
return false;
rebuild_hamiltonian_path((1 << nodes_count) - 1, t);
for (int i = 0; i < nodes_count; i++)
small_graph[i].clear();
for (int i = 0; i < nodes.size(); i++)
bijection[nodes[i]] = -1;
nodes.clear();
for (int i = 1; i <= pos; i++)
dp[_queue[i].first][_queue[i].second] = -1;
return true;
}
inline bool solve_hamiltonian_queries () {
for (int i = 0; i < queries.size(); i++)
if (!solve_hamiltonian_query(queries[i]))
return false;
return true;
}
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
/////////////////////////////////////////////////////////////////////////////////////////////////////////////////////
ifstream cin("santa.in");
inline void read_graph () {
cin >> n >> m;
for (int i = 1; i <= m; i++) {
cin >> edges[i].a >> edges[i].b;
graph[edges[i].a].push_back(i);
graph[edges[i].b].push_back(i);
}
}
inline bool solve () {
for (int i = 1; i <= n; i++)
if (!vis[i])
dfs(i);
vis &= 0;
dfs_road(s);
rebuild_road(e);
if (!get_hamiltonian_queries())
return false;
memset(bijection, -1, sizeof(bijection));
solution.push_back(q);
memset(dp, -1, sizeof(dp));
return solve_hamiltonian_queries();
}
ofstream cout("santa.out");
inline void print_solution () {
cout << solution.size() << '\n';
cout << solution.front();
for (int i = 1; i < solution.size(); i++)
cout << ' ' << solution[i];
cout << '\n';
}
int main()
{
read_graph();
cin >> s >> e >> q;
//Edge case
if (s == e) {
if (s == q) {
cout << "1\n";
cout << q << '\n';
}
else
cout << "No chance\n";
return 0;
}
if (solve())
print_solution();
else
cout << "No chance\n";
cin.close();
cout.close();
return 0;
}