← 返回题目
题库练习 素数路径
← 上一题 下一题 →

A71402 | 素数路径

来源编程题
时间限制1s
内存限制512MB
通过 / 提交0/0

题目描述

在广阔的大陆上有 n 个城市（编号为 1 ~ n），城市之间修建了 m 条双向的道路，且任意两个城市之间最多只有 1 条路。

请编程求：从 x 号城市出发，如果要求相邻两个城市编号的和是素数，且走过的城市不能重复的访问，那么在其可以访问的路线中，哪条路线经过的城市数量最多，输出最多能经过几个城市？（计算经过城市的数量包含起起点和终点）

输入格式

第 1 行，有 2 个整数 n 和 m。（1≤n≤10,1≤m≤(n-1)×n/2）

接下来 m 行，每行有 2 个整数 x 和 y，表示两个城市之间有一条双向道路。（1≤x,y≤n，x \neq y，两个城市之间至多只有一条双向道路）

最后一行有一个整数 x ，表示要求从 x 号城市出发（1≤x≤n）。

输出格式

输出一个整数，表示按题意要求访问相邻的城市，最多能经过几个城市，如果从出发点开始，除了出发点之外，无法访问任何满足题意的城市，请输出 0 。

输入输出样例

输入 #1
5 7
1 2
1 3
2 3
3 4
2 5
4 5
3 5
2
输出 #1
3
C++ 编辑器
输入
输出