#P17815. [ONTAK 2023]SPO

[ONTAK 2023]SPO

题目描述

给定一个有 nn 个顶点、mm 条有向边的图。每个顶点至少有一条出边,允许自环和重边。

甲从顶点 aa 出发,每走过恰好 AA 条边就休息一次;乙从顶点 bb 出发,每走过恰好 BB 条边就休息一次。两人可以自行选择路线,可以重复经过顶点和边。

他们希望在同一顶点休息并相遇。两人到达该顶点前走过的边数不必相同,休息次数也不必相同。允许其中一人走过 00 条边,即留在起点。

判断是否能够相遇;如果能,输出任意一个可行顶点。

输入格式

第一行六个整数 n,m,a,b,A,Bn,m,a,b,A,B。接下来 mm 行,每行两个整数 ui,viu_i,v_i,表示有向边 ui→viu_i\to v_i。

输出格式

无解时输出 NIE;有解时输出一个可行的顶点编号。任意可行顶点均可,不要求它处在某个特定强连通分量中。

数据范围

2≤n≤10002\le n\le1000,2≤m≤100002\le m\le10000;1≤a,b,ui,vi≤n1\le a,b,u_i,v_i\le n,a≠ba\ne b;1≤A,B≤10181\le A,B\le10^{18}。

样例

5 5 4 5 3 2
1 2
2 3
3 1
4 1
5 1
3