fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. #define ll long long
  5. #define ld long double
  6. #define ull unsigned long long
  7.  
  8. // GCD function using long double. Recommend switching to integer types for precision.
  9. ll Gcd(ll a, ll b) {
  10.     if (b == 0) return a;
  11.     return Gcd(b, a % b);
  12. }
  13.  
  14. // Modular exponentiation
  15. ll fpower(ll n, ll e, ll m) {
  16.     if (e == 0) return 1;
  17.     if (e == 1) return n % m;
  18.     ll ret = 1;
  19.     if (e & 1) ret = n % m;
  20.     ll x = fpower(n, e / 2, m);
  21.     ret = ret * x % m * x % m;
  22.     return ret % m;
  23. }
  24.  
  25. // Sieve of Eratosthenes for smallest prime divisors
  26. vector<int> sel2(int n) {
  27.     vector<int> d(n + 1, -1);
  28.     for (int i = 2; i <= n; ++i) {
  29.         for (int j = i; j <= n; j += i) {
  30.             if (d[j] == -1) {
  31.                 d[j] = i;
  32.             }
  33.         }
  34.     }
  35.     return d;
  36. }
  37.  
  38. vector<int> prime_factors(int n) {
  39.     vector<int> factors;
  40.     for (int i = 2; i * i <= n; i++) {
  41.         int count = 0;
  42.         while (n % i == 0) {
  43.             n /= i;
  44.             count++;
  45.         }
  46.         if (count > 0) {
  47.             factors.push_back(i);
  48.         }
  49.     }
  50.     if (n > 1)
  51.         factors.push_back(n);
  52.  
  53.     return factors;
  54. }
  55.  
  56. // Standard sieve of Eratosthenes for primes
  57. vector<bool> sel(ll n) {
  58.     vector<bool> d(n + 1, true);
  59.     d[0] = false;
  60.     d[1] = false;
  61.     for (ll i = 2; i * i <= n; ++i) {
  62.         if (d[i]) {
  63.             for (ll j = i * i; j <= n; j += i) {
  64.                 d[j] = false;
  65.             }
  66.         }
  67.     }
  68.     return d;
  69. }
  70.  
  71. // Bit manipulation functions
  72. ll setbit(ll n, ll idx) {
  73.     return (n >> idx) & 1LL;
  74. }
  75. ll flip(ll n, ll idx) {
  76.     return (1LL << idx) ^ n;
  77. }
  78. ll set1(ll n, ll idx) {
  79.     return (1 << idx) | n;
  80. }
  81.  
  82. const int N = 2e5 + 6;
  83. ll n, m;
  84. int d=0;
  85. vector<int> h[N];
  86. vector<int> r2(N);
  87. vector<bool> vis(N);
  88. vector<int> par(N);
  89. int dfs(int node, int parent) {
  90.     int sum = 0;
  91.     for (int neighbor : h[node]) {
  92.         if (neighbor != parent) {
  93.             int subtree_size = dfs(neighbor, node);
  94.             sum += subtree_size;
  95.         }
  96.     }
  97.     r2[node] = sum + 1;
  98.     return r2[node];
  99. }
  100. void bfs(int start , int end){
  101.     queue<int>q;
  102.     q.emplace(start);
  103.     while (!q.empty()){
  104.         int node=q.front();
  105.         q.pop();
  106.         vis[node]= true;
  107.         for (int neighbor : h[node]) {
  108.             if (!vis[neighbor]) {
  109.                 par[neighbor]=node;
  110.                 q.emplace(neighbor);
  111.             }
  112.         }
  113.     }
  114. }
  115. int ask(int s){
  116.     cout<<s<<"\n";
  117.     cout.flush();
  118.     string c;
  119.     cin>>c;
  120.     if(c=="yes"){
  121.         return 1;
  122.     }else{
  123.         return 0;
  124.     }
  125. }
  126. void solve(){
  127.     cin>>n>>m;
  128.     for (int i = 0; i < m; ++i) {
  129.         int a,b;
  130.         cin>>a>>b;
  131.         h[a].push_back(b);
  132.         h[b].push_back(a);
  133.     }
  134.     bfs(1,n);
  135.  
  136.     if(!vis[n]){
  137.         cout<<"IMPOSSIBLE";
  138.         return;
  139.     }
  140.     int x=par[n];
  141.     vector<ll>tr;
  142.     tr.push_back(n);
  143.     while (x>1){
  144.         tr.push_back(x);
  145.         x=par[x];
  146.     }
  147.     cout<<tr.size()+1<<"\n";
  148.     cout<<1<<" ";
  149.     for (int i = tr.size()-1; i>=0; --i) {
  150.         cout<<tr[i]<<" ";
  151.     }
  152. }
  153. int main() {
  154.     ios_base::sync_with_stdio(false);
  155.     cin.tie(nullptr);
  156.     cout.tie(nullptr);
  157.     int t=1;
  158.     while (t--) {
  159.         solve();
  160.    }
  161. }
Success #stdin #stdout 0.01s 9360KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
IMPOSSIBLE
https://ideone.com/BrnBsG
language:
C++ (gcc 8.3)
created:
78 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!