1
10 2 20
8 5 2 4 10 3 9 7 1 6
5 10
3 17
6 31
3 46
10 42
7 19
9 36
7 3
3 13
8 32
10 25
9 34
10 34
6 33
3 9
2 17
4 5
10 44
9 15
5 40
 1
47 1 47
40 45 19 10 44 33 47 12 2 46 16 23 3 14 21 28 31 42 22 18 35 38 24 25 36 32 4 34 5 20 37 39 6 9 1 7 29 8 17 27 30 11 13 41 15 43 26
39 25
41 24
32 30
10 6
30 13
24 35
41 17
31 31
9 44
21 8
43 23
8 5
29 13
8 4
47 20
22 10
37 27
17 39
43 23
14 42
46 19
43 24
30 31
24 35
31 13
31 32
20 9
3 2
20 9
14 7
7 3
21 36
32 30
47 19
11 43
6 2
31 31
26 12
47 20
2 1
40 24
16 40
45 21
36 28
36 28
17 38
30 31
 1
1 1 4
1
1 1
1 2
1 3
1 4
 1
10 1 1
10 4 6 5 7 9 8 1 3 2
6 10

3
2
7
10
6
7
7
7
5
1
6
6
1
9
4
4
4
1
1
3
 27
27
37
16
20
24
11
20
46
35
11
2
34
47
26
24
7
28
11
3
26
13
37
24
37
37
22
10
22
14
47
38
37
43
23
33
20
4
26
19
30
21
43
1
1
42
37
 1
-1
-1
-1
 9

#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 10;
int n, m;
vector<int> G[N];
void read() {
  cin >> n >> m;
  for (int i = 1; i <= n; i++) G[i].clear();
  for (int i = 1, u, v; i <= m; i++) {
    cin >> u >> v;
    G[u].emplace_back(v);
    G[v].emplace_back(u);
  }
}
vector<int> ans;
int vis[N], d[N], mark[N];
bool check() {
  for (int i = 1; i <= n; i++) mark[i] = vis[i] = d[i] = 0;
  ans.clear();
  vis[1] = d[1] = 1;
  queue<int> q;
  q.push(1);
  while (!q.empty()) {
    int u = q.front();
    q.pop();
    if (d[u]) {
      if (mark[u]) {
        d[u] = 0;
        q.push(u);
        continue;
      }
      ans.emplace_back(u);
      for (int v : G[u]) mark[v] = 1;
    }
    for (int v : G[u])
      if (!vis[v]) {
        vis[v] = 1;
        d[v] = d[u] ^ 1;
        q.push(v);
      }
  }
  for (int i = 1; i <= n; i++)
    if (!vis[i]) return false;
  return true;
}
void process() {
  if (check()) {
    cout << "YES\n" << ans.size() << "\n";
    for (int x : ans) cout << x << " ";
    cout << "\n";
    return;
  }
  cout << "NO\n";
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int t;
  cin >> t;
  while (t--) {
    read();
    process();
  }
  return 0;
}
