Problem F
Facebook Bot Issues

In the wake of Twitter’s acquisition by Elon Musk, the world is anxiously watching to see if the social network will stay alive, and many people are considering alternatives. Marta, for example, decided to go back to using Facebook.

As you may know, in Facebook relationships are bidirectional: two accounts are “friends” with each other, it’s not possible for only one account to be a friend of the other one while not viceversa.

After returning to Facebook, Marta noticed that this social network is also filled with bots just like Twitter. She started looking for suspicious patterns in the friends relationships, and she identified a very specific condition that almost always indicates the presence of bot behavior.

The shape that she identified as being bot-like is when there are two Facebook accounts $a$ and $b$, which are the “pivot” accounts, and then $K$ other accounts which are connected to the pivots via a friend relationship. It doesn’t matter what relationship these $K$ accounts have among themselves, or what relationship the two pivot accounts have among themselves.

Marta wants to know if this shape is present anywhere among his $N$ friends. Given the $M$ friendship relations of all her friends, identify whether the suspicious shape is present or not.

Input

The first line contains three integers: $N$, $M$ and $K$, respectively the number of friends, the number of relationships among these friends, and the number $K$ that identifies the shape that Marta is looking for.

Each of the next $M$ lines contains two integers $X_ i$ and $Y_ i$ which indicate that friend $X_ i$ and $Y_ i$ are connected via a friend relationship.

Output

You need to write a single line containing YES if the shape that Marta is looking for is present, and NO if it’s not.

Constraints

• $1 \le N \le 2000$.

• $0 \le M \le N(N-1)/2$.

• $1 \le K \le 10$.

• $1 \le X_ i, Y_ i \le N$.

• An account can’t be friend with themself.

• Each friend relationship is reported only once in the input data.

5 10 3
1 2
1 3
1 4
1 5
2 3
2 4
2 5
3 4
3 5
4 5

YES