Advertisement
Saleh127

CSES 1667

Oct 29th, 2020
59
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define ll long long
  4. #define test int t; cin>>t; for(int cs=1;cs<=t;cs++)
  5.  
  6. vector<ll>adj[100005];
  7. ll seen[100005];
  8. vector<ll>ans;
  9. ll n,m;
  10.  
  11. void bfs()
  12. {
  13. queue<ll>qu;
  14. qu.push(1);
  15. seen[1]=1;
  16. while(!qu.empty())
  17. {
  18. ll x = qu.front();
  19. qu.pop();
  20. for(auto i : adj[x])
  21. {
  22. if(!seen[i])
  23. {
  24. seen[i]=1;
  25. ans[i]=x;
  26. qu.push(i);
  27. }
  28. }
  29. }
  30. }
  31.  
  32. int main()
  33. {
  34. ios_base::sync_with_stdio(0);
  35. cin.tie(0);
  36. cout.tie(0);
  37.  
  38. ll i,k,a,b;
  39.  
  40. cin>>n>>m;
  41.  
  42.  
  43. ans.resize(n+1);
  44.  
  45. for(i = 0; i<=n;i++)
  46. {
  47. ans[i] = -1;
  48. }
  49. for(i=0; i<m; i++)
  50. {
  51. cin>>a>>b;
  52. adj[a].push_back(b);
  53. adj[b].push_back(a);
  54. }
  55. bfs();
  56.  
  57. if(ans[n]==-1)
  58. {
  59. cout<<"IMPOSSIBLE"<<endl;
  60. }
  61.  
  62. k=n;
  63. vector<ll>ss;
  64. while(k!= -1)
  65. {
  66. ss.push_back(k);
  67. k = ans[k];
  68. }
  69.  
  70. cout << ss.size() << endl;
  71. reverse(ss.begin(),ss.end());
  72. for(i=0;i<ss.size();i++)
  73. {
  74. if(i==0) cout<<ss[i];
  75. else cout<<" "<<ss[i];
  76. }
  77. cout<<endl;
  78. return 0;
  79. }
  80.  
Advertisement
RAW Paste Data Copied
Advertisement