Description

Background：

载着荣耀的流光在星云上启程，不知终落谁手。

Description：

星云由N颗星组成，呈环状分布(按照顺时针方向标号顺序为1,2,3,...,N,1,2,3...)，流光可以有两种流动方式：

    一、沿顺时针由一颗星滑向它的下一颗星。

    二、我们定义“焱”为一种传送机制，即若两个星球之间燃烧着“焱”，则顺时针序靠后的星球，可以通过此机制传送回顺时针序靠前的那个星球。

某一天星云被破坏了，只剩下了最后一抹荣耀流光被两股神秘力量角逐。而破坏带来了两个限制：

    一、某颗行星P被设定为流光禁区（即永远无法被选择为流光的落脚点）。

二、一旦一颗星被流光划过，那么就再也不能被经过了。

现在两种神秘力量轮流引导流光的流动，先手在第一次操作时为确定流光的起始位置，问谁可以拿到最后一次的掌控权来获得胜利？

另外学者们发现，“焱”具有特殊的性质：

如果把每个“焱”视为零点为其两个星球的类似圆弧的轨迹，那么两条轨迹之间不会相交或外切，但是内切和包含以及相离都是合法的。

Input

第一行三个整数n，m，p表示星云上n个点按标号顺时针环形排列，有m个“焱”，行星p为流光禁区。

接下来有m行，每行两个整数u，v，表示u与v之间存在一个“焱”。

Output

Sample Input

Sample Output

Hint

Source