Snakeless path

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

const int N = 1e5;
int R[N];
unordered_set<ll> V;
set<int> S;

int main() {
  int n, m;
  cin >> n >> m;
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    V.insert((a-1)|(ll(b-1)<<32));
  }
  for (int i = 1; i < n; ++i) {
    S.insert(i);
  }
  vector<int> q;
  vector<int> A;
  q.push_back(0);
  while (!q.empty()) {
    int i = q.back(); q.pop_back();
    for (int j : S) {
      if (i == j) continue;
      if (V.count(min(i,j)|(ll(max(i,j))<<32))) continue;
      q.push_back(j);
      A.push_back(j);
      assert(R[j] == 0);
      R[j] = i+1;
    }
    for (int j : A) S.erase(j);
    A.clear();
  }
  if (R[n-1] == 0) {
    cout << "0\n";
    return 0;
  }
  vector<int> A2;
  A2.push_back(n);
  while (R[A2.back()-1] != 0) {
    A2.push_back(R[A2.back()-1]);
  }
  reverse(A2.begin(),A2.end());
  cout << A2.size() << "\n";
  for (int p : A2) {
    cout << p << ' ';
  }
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED

Test 15

Verdict: ACCEPTED

Test 16

Verdict: ACCEPTED

Test 17

Verdict: ACCEPTED

Test 18

Verdict: ACCEPTED

Test 19

Verdict: ACCEPTED

Test 20

Verdict: ACCEPTED

Test 21

Verdict: ACCEPTED

Test 22

Verdict: ACCEPTED

Test 23

Verdict: ACCEPTED

Test 24

Verdict: ACCEPTED

Test 25

Verdict: ACCEPTED

Test 26

Verdict: ACCEPTED

Test 27

Verdict: ACCEPTED

Test 28

Verdict: ACCEPTED

Test 29

Verdict: ACCEPTED

Test 30

Verdict: ACCEPTED

Test 31

Verdict: ACCEPTED

Test 32

Verdict: ACCEPTED

Test 33

Verdict: ACCEPTED

Test 34

Verdict: ACCEPTED

Test 35

Verdict: ACCEPTED

Test 36

Verdict: ACCEPTED

Test 37

Verdict: ACCEPTED

Test 38

Verdict: ACCEPTED

Test 39

Verdict: ACCEPTED

Test 40

Verdict: ACCEPTED

Test 41

Verdict: ACCEPTED

Test 42

Verdict: ACCEPTED

Test 43

Verdict: ACCEPTED

Test 44

Verdict: ACCEPTED

Test 45

Verdict: ACCEPTED

Test 46

Verdict: ACCEPTED

Test 47

Verdict: ACCEPTED

Test 48

Verdict: ACCEPTED

Test 49

Verdict: ACCEPTED

Test 50

Verdict: ACCEPTED

Test 51

Verdict: ACCEPTED

Test 52

Verdict: ACCEPTED

Test 53

Verdict: ACCEPTED

Test 54

Verdict: ACCEPTED

Test 55

Verdict: ACCEPTED

Test 56

Verdict: ACCEPTED

Test 57

Verdict: ACCEPTED

Test 58

Verdict: ACCEPTED

Test 59

Verdict: ACCEPTED

Test 60

Verdict: ACCEPTED

Test 61

Verdict: ACCEPTED

Test 62

Verdict: ACCEPTED

Test 63

Verdict: ACCEPTED

Test 64

Verdict: ACCEPTED

Test 65

Verdict: ACCEPTED

Test 66

Verdict: ACCEPTED

Test 67

Verdict: ACCEPTED

Test 68

Verdict: ACCEPTED

Test 69

Verdict: ACCEPTED

Test 70

Verdict: ACCEPTED

Test 71

Verdict: ACCEPTED

Test 72

Verdict: ACCEPTED

Test 73

Verdict: ACCEPTED

Test 74

Verdict: ACCEPTED

Test 75

Verdict: ACCEPTED

Test 76

Verdict: ACCEPTED

Test 77

Verdict: ACCEPTED

Test 78

Verdict: ACCEPTED

Test 79

Verdict: ACCEPTED

Test 80

Verdict: ACCEPTED

Test 81

Verdict: ACCEPTED

Test 82

Verdict: ACCEPTED

Test 83

Verdict: ACCEPTED

Test 84

Verdict: ACCEPTED

Test 85

Verdict: ACCEPTED

Test 86

Verdict: ACCEPTED

Test 87

Verdict: ACCEPTED

Test 88

Verdict: ACCEPTED

Test 89

Verdict: ACCEPTED