The pta patching simple graph theory

Memoized search can avoid timeouts, and read questions well.

The picture below is taken from Sina Weibo of "British Joke Encyclopedia" - so no need to worry whether you encounter problems or not.

Bloggers call this kind of logical deduction "logically consistent", that all reasoning paths from a proposition lead to the same final proposition (just kidding, don'tThought this was a really logically self-consistent definition...).Now given a more complex logical reasoning diagram, this question asks you to check whether the reasoning from a given proposition to another is "logically self-consistent", and how many different reasoning paths exist.For example, in the figure above, from "Have you encountered a problem?" to "Then don't worry about it" is a "logically consistent" reasoning, with a total of 3 different reasoning paths.

input format:

The input first gives two positive integers N (1

The next M lines, each line gives the reasoning relationship between a pair of propositions, that is, the number of the two propositions S1 S2, indicating that it can be deduced from S1S1code>S2.The title guarantees that there is at most one inference relationship between any two propositions, and that any proposition cannot be self-evidence (that is, the proposition itself is derived from the proposition).

The last line gives the numbers of the two propositions to be tested A B.

Output format:

In one line first output how many different inference paths are there from A to B, then output Yes if the inference is "logical self-Contact", or No if not.

The title guarantees that the output data does not exceed 109.

Input Sample 1:

7 87 67 46 54 15 25 3twenty one3 17 1

Output Sample 1:

3 Yes

Input Sample 2:

7 87 67 46 54 15 25 36 13 17 1

Output Sample 2:

3 No

Code length limit

16 KB

Time limit

400 ms

Memory Limit

64MB

Code:

#includeusing namespace std;typedef long long ll;typedef double db;const int N=510;int a[N][N];int path[N];bool vis[N];int n,m;int dfs(int s){vis[s] = 1;if(path[s]){return path[s];}for(int i=1; i<=n;i++){if(a[s][i]){path[s]+=dfs(i);}}return path[s];}int main(){ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);cin>>n>>m;for(int i=1; i<=m; i++){int s1,s2;cin>>s1>>s2;a[s1][s2]=1;}int start,finish;cin>>start>>finish;path[finish]=1;int sum=dfs(start);cout<