# Walk In a Graph

[Practice] CENV005 Problem - CodeChef
[Codennovate] CodeChef: Practical coding for everyone

Author: [Abhishek Patnigere] stingray8041 | CodeChef User Profile for Abhishek Patnigere | CodeChef
Editorialist: [Akshat Goyal] beast787 | CodeChef User Profile for Akshat Goyal | CodeChef

DIFFICULTY: Hard
# PREREQUISITES: Graphs,Math

Solution To The Problem

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define pb push_back
#define ff first
#define ss second
#define pii pair<int,int>
#define pll pair<ll,ll>
#define mod 1000000007
#define rep(i,n) for(int i=0; i<n; i++)
#define repa(i,start,end) for(int i=start; i<=end; i++)
#define repd(i,start,end) for(int i=start; i>=end; i–)
#define all(x) x.begin(),x.end()
#define debug(x) cout << “(” << #x << ": " << x << “)” << endl;
#define maxn 1000005

int udist[maxn], vdist[maxn];

void bfs(int root, int n, int distance[]) {
vector visited(n,false);
visited[root]=true;
distance[root]=0;
queue q;
q.push(root);

``````while(!q.empty()) {
int node = q.front();
q.pop();

if(!visited[u]) {
visited[u] = true;
distance[u] = distance[node]+1;
q.push(u);
}
}
}
``````

}

void solve() {
int n,m,u,v;
cin >> n >> m >> u >> v;

``````rep(i,m) {
int x,y;
cin >> x >> y;
}

if(u==v) {
cout << "possible\n";
cout << 0 << endl;
cout << u << endl;
return;
}

rep(i,n) {
udist[i]=1e8;
vdist[i]=1e8;
}
else {
udist[i]=0;
vdist[i]=0;
}
}

bfs(u,n,udist);
bfs(v,n,vdist);

int path_length=1e8;
bool flag=0;

map<int, vector<int>> ans; //distance to node map

for(int i=0; i<n; i++) {
if(udist[i]!=1e8 && vdist[i]!=1e8) {
if(udist[i]==vdist[i]) {
flag=1;
path_length = min(path_length, udist[i]);
ans[udist[i]].pb(i);
}

else if(udist[i]>vdist[i]) {
int req = udist[i];

if( (udist[i]-vdist[i])%2 == 0) {
flag=1;
path_length = min(path_length, req);
ans[req].pb(i);
continue;
}

int parity = vdist[i]%2;
//search if path length of req from node v to i
if(vdist[x] < req) {
if(vdist[x]%2 == parity) {
flag=1;
path_length = min(path_length, req);
ans[req].pb(i);
break;
}
}
}
}

else {
int req = vdist[i];

if( (vdist[i]-udist[i])%2 == 0) {
flag=1;
path_length = min(path_length, req);
ans[req].pb(i);
continue;
}

int parity = udist[i]%2;
//search if path length of req from node u to i
if(udist[x] < req) {
if(udist[x]%2 == parity) {
flag=1;
path_length = min(path_length, req);
ans[req].pb(i);
break;
}
}
}
}
}
}

if(flag) {
cout << "possible" << endl;
cout << path_length << endl;
for(auto x: ans[path_length]) {
cout << x << " ";
}
cout << endl;
}

else
cout << "impossible" << endl;
``````

}

int main() {
ios_base::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
solve();
}