Submission #1868275

---

Source Code Expand

#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <exception>
#include <fstream>
#include <functional>
#include <iomanip>
#include <ios>
#include <iosfwd>
#include <iostream>
#include <istream>
#include <iterator>
#include <limits>
#include <list>
#include <locale>
#include <map>
#include <memory>
#include <new>
#include <numeric>
#include <ostream>
#include <queue>
#include <set>
#include <sstream>
#include <stack>
#include <stdexcept>
#include <streambuf>
#include <string>
#include <typeinfo>
#include <utility>
#include <valarray>
#include <vector>
#if __cplusplus >= 201103L
#include <array>
#include <atomic>
#include <chrono>
#include <condition_variable>
#include <forward_list>
#include <future>
#include <initializer_list>
#include <mutex>
#include <random>
#include <ratio>
#include <regex>
#include <scoped_allocator>
#include <system_error>
#include <thread>
#include <tuple>
#include <typeindex>
#include <type_traits>
#include <unordered_map>
#include <unordered_set>
#endif
#define int long long
using namespace std;
const long long maxn = 1000100, mod = 1e9 + 7, maxa = 3e6 + 100, maxb = 23, base = 737, base2 = 3079, mod2 = 242121643;
const long long inf = 2e18 + 13;
long long max(long long x, long long y){return (x > y ? x : y);}
long long min(long long x, long long y){return (x < y ? x : y);}

long long h[maxn];
bool visited[maxn];
vector <int> v[maxn];

void bfs(int x)
{
    queue <int> q;
    q.push(x);
    visited[x] = 1;
    while(q.size())
    {
        x = q.front();
        q.pop();
        for(auto u : v[x])
        {
            if(!visited[u])
            {
                visited[u] = 1;
                h[u] = h[x] + 1;
                q.push(u);
            }
        }
    }
}

int32_t main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long n, m;
    cin >> n >> m;
    for(int i = 0; i < m; i++)
    {
        int a, b;
        cin >> a >> b;
        a--; b--;
        v[a].push_back(b);
        v[b].push_back(a);
    }
    bfs(0);
    cout << (h[n - 1] == 2 ? "POSSIBLE" : "IMPOSSIBLE") << endl;  
    return 0;
}

Submission Info

Judge Result