頂点 $0$ 番から頂点 $v$ 番までの辺があるかというフラグと、
頂点 $v$ 番から頂点 $n-1$ 番までの辺があるかというフラグの両方を持っておき、
どちらもあるときには、頂点 $v$ を経由して辿ることができる。

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

int main(void) {
  int n, m; scanf("%d%d", &n, &m);
  vector<bool> route1(n, false),
               route2(n, false);
  for(int i=0; i<m; ++i) {
    int a, b; scanf("%d%d", &a, &b);
    --a, --b;
    if(a == 0)   { route1[b] = true; }
    if(b == n-1) { route2[a] = true; }
  }
  for(int v=0; v<n; ++v) {
    if(route1[v] && route2[v]) {
      puts("POSSIBLE");
      return 0;
    }
  }
  puts("IMPOSSIBLE");
  return 0;
}
      

---
$3$ 色の中からランダムに色を選んで各頂点に塗り、辿ったことのない色だけを辿って頂点 $0$ 番から頂点 $n-1$ 番に行けるかどうかを判定してもいい。Color coding.
答えがあるときに、一回やって答えがあると断定できる確率は $3!/3^{3} = 2/9$、$100$ 回やっても断定できない確率は $0.0000000012177$ パーセント。
そのくじを引いてしまったら相当運が悪い。

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
using u32 = unsigned int;

u32 uy = time(NULL);
u32 xorshift32() {
  uy ^= uy << 14;
  uy ^= uy >> 13;
  uy ^= uy << 15;
  return uy;
}

int main(void) {
  int n, m; scanf("%d%d", &n, &m);
  vector<vector<int>> G(n, vector<int>());
  for(int i=0; i<m; ++i) {
    int a, b; scanf("%d%d", &a, &b);
    --a, --b;
    G[a].push_back(b);
    G[b].push_back(a);
  }
  vector<int> color(n);
  for(int loop=0; loop<100; ++loop) {
    for(int i=0; i<n; ++i) {
      color[i] = xorshift32() % 3;
    }
    // dp[使った色][今いる場所] := 可否
    vector<vector<bool>> dp(8, vector<bool>(n, false));
    dp[1<<color[0]][0] = true;
    for(int u=0; u<n; ++u) {
      for(int mask=0; mask<8; ++mask) {
        if(!dp[mask][u]) { continue; }
        for(int v : G[u]) {
          if(mask >> color[v] & 1) { continue; }
          dp[mask|(1<<color[v])][v] = true;
        }
      }
    }
    if(dp[7][n-1]) {
      puts("POSSIBLE");
      return 0;
    }
  }
  puts("IMPOSSIBLE");
  return 0;
}
      

(ΦωΦ)＜つづく