Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include<bits/stdc++.h>
- using namespace std;
- typedef __int128 lll;
- typedef long long ll;
- typedef long double ld;
- ll inf = 1e9+1, mod = 1e9 + 7;
- const int N = 1e6;
- #define all(a) a.begin(),a.end()
- #define pb push_back
- #define get(a) for(int i = 0; i < (int)a.size(); ++i) cout << a[i]+1 << ' ';
- #define SOLVE int t; cin >> t; while(t--) solve();
- struct mosh
- {
- int first, second, third;
- };
- bool compare2(int a, int b){
- return a > b;
- }
- bool compare(mosh a, mosh b){
- if(a.first!= b.first) return a.first > b.first;
- else if(a.first == b.first && a.second!= b.second) return a.second < b.second;
- else return a.third < b.third;
- }
- struct point{
- ll first, type;
- };
- bool compare3(point a, point b){
- if(a.type == b.type) return a.first < b.first;
- else return a.type > b.type;
- }
- int gcd(int a , int b)
- {
- if(b==0) return a;
- a%=b;
- return gcd(b,a);
- }
- vector<int>g[N];
- int pr[N];
- void solve(){
- int n, m;
- cin >> n >> m;
- vector<int>dist(n, -1);
- for(int i = 0; i < m; ++i){
- int a, b;
- cin >> a >> b;
- --a;
- --b;
- g[a].pb(b);
- }
- int s, t;
- cin >> s >> t;
- cout << s << '\n';
- --s;
- --t;
- queue<int>q;
- q.push(s);
- dist[s] = 0;
- while(!q.empty()){
- int v = q.front();
- q.pop();
- for(int to : g[v]){
- if(dist[to] == -1){
- dist[to] = dist[v] + 1;
- q.push(to);
- pr[to] = v;
- }
- }
- }
- int j = t;
- vector<int>ans;
- while(j){
- ans.pb(j);
- j = pr[j];
- }
- cout << dist[t] << '\n';
- cout << s << ' ' << '\n';
- reverse(all(ans));
- get(ans);
- }
- int main() {
- #ifdef anime
- freopen("input1.txt", "r", stdin);
- freopen("output1.txt", "w", stdout);
- #endif
- srand(time(nullptr));
- ios_base::sync_with_stdio(false);
- cin.tie(nullptr);
- cout.tie(nullptr);
- solve();
- }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement
