CodeForces 967F. Aztec Catacombs（思维建树图）

F. Aztec Catacombs

time limit per test

2 seconds

memory limit per test

256 megabytes

input

standard input

output

standard output

Indiana Jones found ancient Aztec catacombs containing a golden idol. The catacombs consists of nn caves. Each pair of caves is connected with a two-way corridor that can be opened or closed. The entrance to the catacombs is in the cave 11, the idol and the exit are in the cave nn.

When Indiana goes from a cave xx to a cave yy using an open corridor, all corridors connected to the cave xx change their state: all open corridors become closed, all closed corridors become open. Indiana wants to go from cave 11 to cave nn going through as small number of corridors as possible. Help him find the optimal path, or determine that it is impossible to get out of catacombs.

Input

The first line contains two integers nn and mm (2≤n≤3⋅1052≤n≤3⋅105, 0≤m≤3⋅1050≤m≤3⋅105) — the number of caves and the number of open corridors at the initial moment.

The next mm lines describe the open corridors. The ii-th of these lines contains two integers uiui and vivi (1≤ui,vi≤n1≤ui,vi≤n, ui≠viui≠vi) — the caves connected by the ii-th open corridor. It is guaranteed that each unordered pair of caves is presented at most once.

Output

If there is a path to exit, in the first line print a single integer kk — the minimum number of corridors Indians should pass through (1≤k≤1061≤k≤106). In the second line print k+1k+1 integers x0,…,xkx0,…,xk — the number of caves in the order Indiana should visit them. The sequence x0,…,xkx0,…,xk should satisfy the following:

x0=1x0=1, xk=nxk=n;
for each ii from 11 to kk the corridor from xi−1xi−1 to xixi should be open at the moment Indiana walks along this corridor.

If there is no path, print a single integer −1−1.

We can show that if there is a path, there is a path consisting of no more than 106106 corridors.

Examples

input

Copy

output

Copy

2
1 3 4

input

Copy

4 2
1 2
2 3

output

Copy

4
1 2 3 1 4

从1点到n点，起初有一些边，当你从a走到b时，a的所有的边关闭，所有不相连的边开启，问从1到n最快的步骤并输出；

这道题其实主要是思路题，我们把跟1直接连接的当作第一层，把跟1不连接但是跟第一层直接连接的当做第二层，由此可以画出如树一般的图。

假设1不通过已有的路直接到达n

而此时，当有至少两层的情况下，我们可以从1走到第一层再走到第二层，此时，因为初始状态下第二层与1不连接，所以当1状态反转的时候（1->2）第二层会有跟1相连接的通道，这样就可以回到1，这种情况是走4次。

另一方面，假如一共就只有一层，这样的话，我们就看对于每个与1相连接的那些点（一定要与1相连接才行），是否存在相对于那些点的第二层存在，如果有的话就按照第一种情况再走一遍就好了，这种情况是走5次。

1通过已有的路直接到达n

这样的情况下，看看从1到n的距离是否小于4次，如果是的话直接输出，如果不是的话，就按照不通过已有路径直接走到的情况下输出就好了。

#include<bits/stdc++.h>
using namespace std;
#define inf 0x3f3f3f3f
int n, m;
vector<int>G[300005];
int pre[300005];
int d[300005];
int maxn;
void dfs(){
	for (int s = 1; s <= n; s++) {
		d[s] = inf;
	}
	memset(pre, 0, sizeof(pre));
	maxn = 0;
	queue<int>q;
	q.push(1);
	d[1] = 0;
	pre[1] = 0;
	while (!q.empty()){
		int t = q.front();
		q.pop();
		maxn = max(maxn, d[t]);
		int sz = G[t].size();
		for (int s = 0; s < sz; s++) 
			if (d[G[t][s]] > d[t] + 1) {
				d[G[t][s]] = d[t] + 1;
				pre[G[t][s]] = t;
				q.push(G[t][s]);
			}
	}
}
int ***_bfs(int x) {
	for (int s = 0; s <= n; s++) {
		d[s] = inf;
	}
	queue<int>q;
	q.push(x);
	pre[x] = 0;
	int ans = 0;
	d[x] = 0;
	while (!q.empty()) {
		int t = q.front();
		q.pop();
		if (d[t] == 2) {
			ans = t;
		}
		int sz = G[t].size();
		for (int s = 0; s < sz; s++)
		{
			if (d[G[t][s]] > d[t] + 1 && G[t][s] != 1) {
				d[G[t][s]] = d[t] + 1;
				pre[G[t][s]] = t;
				q.push(G[t][s]);
			}
		}
	}
	return ans;
}
int main() 
{
	while (scanf("%d%d", &n, &m) != EOF) {
		for (int s = 0; s < m; s++) {
			int a, b;
			scanf("%d%d", &a, &b);
			G[a].push_back(b);
			G[b].push_back(a);
		}
		dfs();
		if (n == 30 && m == 103) {
		}
		if (d[n]<4) {
			stack<int>q;
			printf("%d\n", d[n]);
			while (n) {
				q.push(n);
				n = pre[n];
			}
			printf("%d", q.top());
			q.pop();
			while (!q.empty()) {
				printf(" %d", q.top());
				q.pop();
			}
			printf("\n");
		}
		else{
			if (maxn < 2)
			{
				int spot = 0, t;
				int sz = G[1].size();
				for (int s = 0; s < sz; s++)
				{
					spot = ***_bfs(G[1][s]);
					if (spot) {
						t = G[1][s]; break;
					}
				}
				if (spot) {
					printf("5\n");
					stack<int>q;
					q.push(n);  q.push(t);
					while (spot) {
						q.push(spot);
						spot = pre[spot];
					}q.push(1);
					printf("%d", q.top());
					q.pop();
					while (!q.empty()) {
						printf(" %d", q.top());
						q.pop();
					}
					printf("\n");
				}
				else
					printf("-1\n");
			}
			else {
				printf("4\n");
				stack<int>q;
				int t;
				for (int s = 1; s <= n; s++) {
					if (d[s] == 2) {
						t = s; break;
					}
				} 
				q.push(n);  q.push(1);
				while (t) {
					q.push(t);
					t = pre[t];
				}
				printf("%d", q.top());
				q.pop();
				while (!q.empty()) {
					printf(" %d", q.top());
					q.pop();
				}
				printf("\n");
			}
		}
	}
}