ЗОШ 0-1 bfs OK

#include <iostream>
#include <cmath>
#include <vector>
#include <queue>
#include <deque>
#include <algorithm>
#include <string>
#include <stack>
#include <set>
#include <map>
#define pii pair <int,int>
using namespace std;
using ll = long long;
using ld = long double;
using db = double;
void cv(vector <int> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}

void cvl(vector <ll> &v){
    for (auto x: v) cout<<x<<' ';
    cout<<"\n";
}


void cvv(vector <vector <int> > &v){
    for (auto x: v) cv(x);
    cout<<"\n";
}

struct ed{
    int fr, to, w;
};

vector <vector <ed>> G;
int n,m;

vector <int> d;

deque  <int> Q;

vector <int> pr;

const int inf = 2e9;

bool ch = 1;


void bfs(int s){
    d.resize(n, inf);
    pr.resize(n, -100);
    d[s] = 0;
    Q.push_back(s);
    while (!Q.empty()){
        int v = Q.front();
        Q.pop_front();
        for (auto e: G[v]){
            if (d[v] + e.w < d[e.to]){
                d[e.to] = d[v] + e.w;
                pr[e.to] = v;
                if  (e.w == 1){
                    Q.push_back(e.to);
                }
                else{
                    Q.push_front(e.to);
                }
            }
        }
    }
}

void shG(){
    for (int  i = 0; i < n;++i){
            cout<<i+1<<"\n";
        for (auto e: G[i]){
            cout<<e.to+1<<' '<<e.w<<"\n";
        }
        cout<<"\n";
    }
}

void shd(){
    cout<<"dst\n";
    for (int i=0;i<n;++i){
        cout<<i+1<<' '<<d[i]<<"\n";
    }
    cout<<"\n";
}

void shpr(){
    cout<<"pr\n";
    for (int i =0;i<n;++i){
        cout<<i+1<<' '<<pr[i]+1<<"\n";
    }
    cout<<"\n";
}

int main()
{
    ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin>>n>>m;
	G.resize(n);
	vector <int> whose(n);
	for (int i=0;i<n;++i){
        cin>>whose[i];
	}

	for (int i =0;i<m;++i){
        int a,b, w;
        cin>>a>>b;
        a--; b--;
        if (whose[a] == whose[b]){
            w = 0;
        }
        else w = 1;
        ed any = {a, b, w};
        G[a].push_back(any);
        any = {b, a, w};
        G[b].push_back(any);
	}
	//shG();
	bfs(0);
	if (d[n-1] == inf){
        cout<<"impossible\n";
        exit(0);
	}
	//cout<<d[n-1];
	//shd();
	//shpr();
	vector <int> ans = {n};
	int v = n-1;
	while (pr[v] > 0){
        ans.push_back(pr[v] + 1);
        v = pr[v];
	}
	ans.push_back(1);
	cout<<d[n-1]<<' '<<ans.size()<<"\n";
	reverse(ans.begin(), ans.end());
	cv(ans);
	//кек
}
/*
7 8
1 1 1 1 2 2 1
1 2
2 5
2 3
5 4
4 3
4 7
1 6
6 7

*/