Hide

Problem D
Gym Leader's Territory

You are a gym leader, and you’d like to conquer the territory of a certain rival gym leader. However, gym leaders sometimes make mutual alliances with each other to become stronger! When you challenge a gym leader, your Pokemon are only strong enough to defeat them if there is at most one other gym leader allied to them. You may attack as many gym leaders as you want (in any order), and whenever you defeat a gym leader, you take over their territory and terminate all alliances they may have had with other gym leaders.

There are $n$ other gym leaders (not including you), numbered from leader $1$ to leader $n$. Your rival is gym leader $k$. Given a list of $m$ mutual alliances between pairs of the other gym leaders, determine if it is possible to conquer the territory of your rival. Output “YES” if possible, and “NO” otherwise.

Input

The first line of input contains three space-separated integers $n$, $k$, and $m$: the number of other gym leaders, the rival gym leader, and the total number of alliances, respectively ($1 \leq n \leq 10^5$, $1 \leq k \leq n$, $0 \leq m \leq 10^{6}$).

The next $m$ lines of input each contain two space-separated integers $m_1$ and $m_2$, representing that there is an alliance between gym leader $m_1$ and gym leader $m_2$ ($1 \leq m_1, m_2 \leq n$, $m_1 \neq m_2$). It is guaranteed that the input will not contain multiple alliances between the same pair of gym leaders.

Output

Output one line containing a single string: “YES” if it is possible to conquer gym leader $k$, “NO” otherwise.

Sample Input 1 Sample Output 1
4 4 3
1 2
4 2
3 4
YES
Sample Input 2 Sample Output 2
5 4 5
1 2
4 2
3 4
1 5
2 5
YES
Sample Input 3 Sample Output 3
4 4 4
1 2
4 2
3 4
1 4
NO

Please log in to submit a solution to this problem

Log in