#P17815. [ONTAK 2023]SPO
[ONTAK 2023]SPO
题目描述
给定一个有 个顶点、 条有向边的图。每个顶点至少有一条出边,允许自环和重边。
甲从顶点 出发,每走过恰好 条边就休息一次;乙从顶点 出发,每走过恰好 条边就休息一次。两人可以自行选择路线,可以重复经过顶点和边。
他们希望在同一顶点休息并相遇。两人到达该顶点前走过的边数不必相同,休息次数也不必相同。允许其中一人走过 条边,即留在起点。
判断是否能够相遇;如果能,输出任意一个可行顶点。
输入格式
第一行六个整数 。接下来 行,每行两个整数 ,表示有向边 。
输出格式
无解时输出 NIE;有解时输出一个可行的顶点编号。任意可行顶点均可,不要求它处在某个特定强连通分量中。
数据范围
,;,;。
样例
5 5 4 5 3 2
1 2
2 3
3 1
4 1
5 1
3