← 返回 pinterest 的题目列表Find Shortest Path Between Products
类型：online_judge
In Pinterest’s shopping scenario, you have multiple pins (can be treated as products) with relationships as follows:
P1 = [a_11, a_12, ... , a_1h1] ... Pn = [a_n1, a_n2, ..., a_nhn]
Note a_ij is a product.
Design an algorithm to determine if there is a connection between products A and B, and find the shortest path between them. It is a graph problem. After building the graph, use BFS instead of Dijkstra's algorithm to find the shortest path.
Input
First line: number of products n and number of connections m.
Next m lines: each line contains two product IDs indicating a direct connection between them.
Last line contains two product IDs representing products A and B to inquire.
Output
If a connection exists, output "YES x" where x is the shortest path length.
If no connection exists, output "NO".
Example
Input:
3 2
1 2
2 3
1 3
Output:
YES 2
Constraints
2 <= n <= 1000
1 <= m <= 5000
Each product ID is an integer ranging from 1 to n.
Example
Input
3 2
1 2
2 3
1 3