在一次班级联欢活动中,大家正在玩击鼓传花的游戏。
班里共有若干位同学,每位同学都有一个唯一的名字。 击鼓开始后,花会在同学之间不断传递。
活动开始前,老师制定了 N 条固定的传花规则:
第 i 条规则规定:
当名字为 S_i 的同学拿到花时,下一次一定会把花传给名字为 T_i 的同学。
所有规则同时生效,且满足:
花在游戏开始时,可以交到任意一位同学手中。
如果击鼓游戏一直不叫停,那么花将会按照上述规则不断传递下去。 一旦花 无法继续传递,游戏就会结束,最后拿到花的同学需要表演节目。
请你判断: 是否存在某种情况,使得花可以一直传递下去,游戏永远不会结束?
第 1 行输入一个整数 N,表示有 N 条传递规则。
接下来 N 行,每行输入两个字符串 S_i 和 T_i,表示第 i 条规则。
如果存在一种传递过程,使得花可以一直传下去,输出 Yes,否则输出 No。
2 b m m d
Yes
4 alpha beta beta gamma gamma delta delta epsilon
Yes
4 alpha beta beta gamma gamma alpha delta epsilon
No
花传递的顺序为:b → m → d。
无论花从谁开始,最终都会传到 d,之后无法继续传递,游戏结束。
对于所有的测评数据,满足 1 \le N \le 10^5,S_i, T_i 为长度不超过 8 的小写字母字符串,所有 S_i 两两不同,所有 T_i 两两不同。