Migrated from Lutece 1958 学霸周选课

All parts of this problem, including description, images, samples, data and checker, might be broken. If you find bugs in this problem, please contact the admins.

Description


众所周知周大爷不仅编程了得，专业课成绩更是名列前茅，恰巧又到了选课的季节，神秘的zin作为周大爷的好朋（基）友，给了周大爷一份课表，这个课 表和一般的课表有些不同，它是一个有向无环图，图中每个节点表示一门课程，如果课程A有一条通向课程B的有向边，那么意味着，如果选了课程A，就能选课程B ，对于没有前驱的课程可以直接选择。

周大爷看了课表后，发现自己非常想学课程$k$,但是周大爷又不想花太多精力去学别的课程，现在请你帮助周大爷计算为了选上课程$k$最少一共要选多少门课程（$k$包含在内）。

Input

一个正整数$n$（$1\le n\le 200000$）,$k$ ($1\le k\le n$) ，$m$（$1\le m\le \min(1000000 , \frac{n(n-1)}{2})$） 表示图中有$m$条边.接下来$m$行，每一行输入两个整数$a$，$b$（$1\le a,b\le n$）表示如果选了课程$a$就能选择课程$b$。

Output

周大爷最少要选多少门课程

Samples

3 2 1
1 2

2

Note

样例不是test1

Resources

2018 UESTC ACM Training for Graph Theory