Submission #68157951

---

Source Code Expand

#include <bits/stdc++.h>
#define SZ(x) ((int)(x).size())
#define ALL(x) begin(x), end(x)
#define REP(i, n) for (int i = 0; i < int(n); i++)
#define REP1(i, a, b) for (int i = (a); i <= int(b); i++)

#if __has_include("shik/dump.h")
#include "shik/dump.h"
#else
#define dump(...) 0
#endif

using namespace std;

const int N = 1010;

int n, m, x, y;
vector<int> e[N];
void input() {
  cin >> n >> m >> x >> y;
  for (int i = 1; i <= n; i++) e[i].clear();
  for (int i = 0; i < m; i++) {
    int u, v;
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
}

vector<int> path;
bool vis[N];
bool dfs(int u) {
  vis[u] = true;
  path.push_back(u);
  if (u == y) {
    return true;
  }
  for (int v : e[u]) {
    if (vis[v]) continue;
    if (dfs(v)) return true;
  }
  path.pop_back();
  return false;
}

void solve() {
  for (int i = 1; i <= n; i++) {
    sort(ALL(e[i]));
    vis[i] = false;
  }
  path.clear();
  dfs(x);
  for (int i = 0; i < SZ(path); i++) {
    if (i) cout << " ";
    cout << path[i];
  }
  cout << "\n";
}

int main() {
  ios::sync_with_stdio(false);
  cin.tie(nullptr);
  int num_cases = 0;
  cin >> num_cases;
  REP1(i, 1, num_cases) {
    input();
    solve();
  }
}

Submission Info

Judge Result