Suppose that the given graph is a rooted tree rooted at an arbitrary vertex \(r\). We will construct a good path with respect to \(S = s_1s_2\ldots s_N\), that is, for all vertex \(v\), “the parity of number of occurrences of \(v\) in \(A\)” and “the parity of \(s_v\)” are the same. If the given graph isn’t a tree, we can take an arbitrary spanning tree so that it is boiled down to the case of tree.

For every vertex \(v = 1, 2, \ldots, N\), we recursively define a sequence \(A_v\) as follows.

• If \(v\) does not have a child, then let \(A_v := (v)\), that is, \(A_v\) is a sequence of length \(1\) only consisting of \(v\).
• If \(A_v\) has children \(c_1, c_2, \ldots, c_k\), then let \(A_v := (v) + A_{c_1} + B_{c_1} + (v) + A_{c_2} + B_{c_2} + (v) + \cdots + (v) + A_{c_k} + B_{c_k} + (v)\).

Here, \(+\) denotes a concatenation of sequences, and sequence \(B_{c_i}\) is defined to be

• \(B_{c_i} := ()\) if “the parity of the number of occurrences of \(c_i\) in \(A_{c_i}\)” and “the parity of \(s_{c_i}\)” are equal, and
• \(B_{c_i} := (v, c_i)\) otherwise.

Then, for every vertex \(v = 1, 2, \ldots, N\), it can be proved by induction that \(A_v\) satisfies the following four statements.

1. \(A_v\) is a path.
2. \(A_v\) starts and ends with \(v\).
3. The length of \(A_v\) is at most \(4n-3\), where \(n\) is the number of ancestors of \(v\) (including \(v\) itself).
4. For every ancestor \(d\) of \(v\), except for \(v\) itself, “the parity of the number of occurrences of \(d\) in \(A_v\)” and “the parity of \(s_d\)” are equal.

Therefore, the sequence \(A_r\) corresponding to root \(r\) is a path of length at most \(4N-3\), ending with \(r\), and for every vertex \(v\) except for \(r\), “the parity of the number of occurrences of \(v\) in \(A_r\)” and “the parity of \(s_v\)” are equal.

Hence, the following sequence

• \(A_r\), if “the parity of the number of occurrences of \(r\) in \(A_r\)” and “the parity of \(s_r\)” are equal too; or
• \(A_r + (u, r, u)\), for an arbitrary vertex \(u\) adjacent to \(r\), if they are not equal;

is a good path with respect to \(S\) of length at most \(4N\). By printing this, you will be accepted for this problem.

The following is a sample code in C++ language.

#include <iostream>
#include <vector>
using namespace std;

int n, m;
vector<int> G[100005];
char s[100005];
bool used[100005];
vector<int> ans;

void dfs(int v)
{
  used[v] = true;
  ans.push_back(v), s[v] ^= 1;
  for(auto u : G[v]){
    if(used[u]) continue;
    dfs(u);
    ans.push_back(v), s[v] ^= 1;
    if(s[u] == 1){
      ans.push_back(u), s[u] ^= 1;
      ans.push_back(v), s[v] ^= 1;
    }
  }
}

int main(void)
{
  cin >> n >> m;
  int u, v;
  for(int i = 1; i <= m; i++){
    cin >> u >> v;
    G[u].push_back(v);
    G[v].push_back(u);
  }
  for(int i = 1; i <= n; i++) cin >> s[i], s[i] -= '0';

  dfs(1);
  if(s[1] == 1){
    ans.push_back(G[1][0]);
    ans.push_back(1);
    ans.push_back(G[1][0]);
  }
  
  cout << ans.size() << endl;
  for(auto x : ans) cout << x << " ";
  cout << endl;

  return 0;
}